La forma más eficiente de buscar / buscar en una lista enorme (python)

– Acabo de analizar un archivo grande y creé una lista que contiene 42.000 cadenas / palabras. Quiero consultar [contra esta lista] para verificar si una palabra / cadena dada le pertenece. Así que mi pregunta es:

¿Cuál es la forma más eficiente para tal búsqueda?

Un primer enfoque es ordenar la lista ( list.sort() ) y luego usar

 >> if word in list: print 'word' 

que es realmente trivial y estoy seguro de que hay una mejor manera de hacerlo. Mi objective es aplicar una búsqueda rápida que encuentre si una cadena dada está en esta lista o no. Si tienes alguna idea de otra estructura de datos, son bienvenidos. Sin embargo, quiero evitar por ahora estructuras de datos más sofisticadas como Tries, etc. Me interesa escuchar ideas (o trucos) sobre búsquedas rápidas o cualquier otro método de biblioteca de Python que pueda realizar la búsqueda más rápido que el simple.

Y también quiero saber el índice del elemento de búsqueda.

No cree una list , cree un set . Hace búsquedas en tiempo constante.

Si no desea la sobrecarga de memoria de un conjunto, mantenga una lista ordenada y busque en ella con el módulo bisect .

 from bisect import bisect_left def bi_contains(lst, item): """ efficient `item in lst` for sorted lists """ # if item is larger than the last its not in the list, but the bisect would # find `len(lst)` as the index to insert, so check that first. Else, if the # item is in the list then it has to be at index bisect_left(lst, item) return (item <= lst[-1]) and (lst[bisect_left(lst, item)] == item) 

Usando este progtwig, parece que los dictados son los ayunos, segundo, lista con bi_contains tercero:

 from datetime import datetime def ReadWordList(): """ Loop through each line in english.txt and add it to the list in uppercase. Returns: Returns array with all the words in english.txt. """ l_words = [] with open(r'c:\english.txt', 'r') as f_in: for line in f_in: line = line.strip().upper() l_words.append(line) return l_words # Loop through each line in english.txt and add it to the l_words list in uppercase. l_words = ReadWordList() l_words = {key: None for key in l_words} #l_words = set(l_words) #l_words = tuple(l_words) t1 = datetime.now() for i in range(10000): #w = 'ZEBRA' in l_words w = bi_contains(l_words, 'ZEBRA') t2 = datetime.now() print('After: ' + str(t2 - t1)) # list = 41.025293 seconds # dict = 0.001488 seconds # set = 0.001499 seconds # tuple = 38.975805 seconds # list with bi_contains = 0.014000 seconds 

Un punto sobre conjuntos versus listas que no se ha considerado: al “analizar un archivo grande” uno esperaría tener que manejar palabras / cadenas duplicadas . No has mencionado esto en absoluto.

Obviamente, agregar nuevas palabras a un conjunto elimina los duplicados sobre la marcha, sin costo adicional de tiempo de CPU o su tiempo de reflexión. Si lo intentas con una lista, termina O (N ** 2). Si agrega todo a una lista y elimina los duplicados al final, la forma más inteligente de hacerlo es … rodar el tambor … use un juego, y la ventaja (pequeña) de memoria de una lista probablemente se verá superada por el duplicados

Si anticipa búsquedas complejas más adelante, y por complejo quiero decir no trivial, le recomiendo que lo guarde en sqlite3 .