La manera más eficiente para una búsqueda/búsqueda en una lista enorme (python)

Question

- Acabo de analizar un archivo grande y creé una lista que contiene 42,000 cadenas/palabras. Quiero consultar [en contra de 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 dicha búsqueda?

Un primer enfoque consiste en ordenar la lista (list.sort()) y luego sólo tiene que utilizar

>> if word in list: print 'word' 

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

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

Answer 1

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

Si no desea la sobrecarga de memoria de un conjunto, conserve una lista ordenada y búsquela 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) 

Answer 2

Un punto acerca de los conjuntos frente a las listas que no hayan sido considerados: en "analizar un archivo grande" uno esperaría que manejar duplicar palabras/cadenas. No has mencionado esto en absoluto.

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

Answer 3

Si prevé búsquedas complejas más adelante, y por complejo quiero decir no triviales, le recomiendo que lo almacene en sqlite3.

Answer 4

uso de este programa parece que predice con mayor crecimiento son las establecidas, segunda, tercera lista con bi_contains:

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