Estoy buscando coincidencias en un archivo de texto grande, pero lo encuentro demasiado lento. Esta es la estructura del archivo:

word1   5752
word2   96332
word3   137

Estoy tratando de hacer coincidir el texto en la primera columna, y quiero extraer el valor en la segunda columna. Las columnas están separadas por \ t y hay aproximadamente 10 millones de líneas. El archivo se busca muchas veces con diferentes palabras. ¿Qué método de búsqueda tiene la mejor eficiencia de tiempo?

EDITAR: El archivo tiene 129 Mb y se buscará miles de veces al menos. EDIT2: El archivo está ordenado alfabéticamente y las palabras pueden aparecer varias veces solo si tienen letras mayúsculas diferentes, por ejemplo: Word WORD word WOrd serán entradas diferentes.

0
querti 17 feb. 2017 a las 17:41

4 respuestas

La mejor respuesta
with open('myfile.dat','r') as src:
    mapping = dict((line.strip().split('\t') for line in src if line))

Dependiendo del tamaño del archivo y la memoria, esto podría ser una solución. Si tiene que realizar este tipo de algoritmo de búsqueda más de una vez durante la ejecución de su programa.

2
voidpointercast 17 feb. 2017 a las 15:00

Si almacena sus datos en una tabla hash (una estructura de diccionario de Python), sería muy rápido hacer esta operación. Su 'Clave' es el nombre, cada Clave tiene un 'Valor', el número. Este código que se muestra a continuación utiliza el hash para una recuperación de datos más rápida:

yourDict = {'name0':number0,'name1':number1,...,'nameN':numberN}
if 'checkName' in yourDict:
    #It exists!
    theNumber = yourDict['checkName']
else:
    #It doesn't exist :/

* Nota: si usa:

if 'checkName' in yourDict.keys():

En realidad estás creando una lista de claves y luego buscándolas. Esta operación no utiliza la tabla hash (mucho más lenta).

Esto es un poco sobre cómo funcionan las estructuras de datos de HandTable: https://www.youtube.com/watch?v=MfhjkfocRR0

Esta es una respuesta que muestra que un diccionario en Python actúa como una tabla hash: ¿Es un diccionario de Python un ejemplo de una tabla hash?

2
Community 23 may. 2017 a las 12:25

¿Es esto para una tarea o para trabajo / proyecto? No sé cómo se siente la gente acerca de volver a implementar algoritmos centrales, pero ¿qué tan grande es su archivo de texto?

Un enfoque alternativo con Pandas para facilitar el uso y la optimización subyacente:

In [61]: df = pd.read_csv(r'C:\temp\data.txt', header=None, sep='  ')

In [62]: df
Out[62]:
       0      1
0  word1   5752
1  word2  96332
2  word3    137

In [63]: df[df[0] == 'word2']
Out[63]:
       0      1
1  word2  96332

In [64]: df[df[0] == 'word2'][1]
Out[64]:
1    96332
Name: 1, dtype: int64

2 preguntas para ti:

1) ¿Se puede guardar esto en la memoria en lugar de volver a cargarlo cada vez? (¿Tal vez con un TTL de como una hora?)

2) ¿Está ordenado su archivo? Creo que Binary Search necesita tener datos ordenados primero. ¿Cuál sería el impacto en el rendimiento para ordenar cada vez que tenga que leer los datos?

1
Kelvin 17 feb. 2017 a las 15:04

Primero ordenaría el archivo alfabéticamente y luego realizaría una búsqueda logarítmica (https://en.wikipedia.org/ wiki / Binary_search_algorithm). Tienes un buen ejemplo de cómo hacerlo con Python aquí: http://programarcadegames.com/index.php?chapter=searching&lang= es # section_16.5

0
Numlet 17 feb. 2017 a las 14:50