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

search performance

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. Entonces 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 simplemente usar

>> 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.

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

Answer 1

No crees una list , crea un set . Realiza búsquedas en tiempo constante.

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

Si anticipas búsquedas complejas más adelante, y por complejo quiero decir que no son triviales, te recomiendo que lo almacenes en sqlite3 .

Answer 3

Un punto sobre conjuntos versus listas que no se ha tenido en cuenta: en "análisis de un archivo grande" uno esperaría necesitar 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 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 4

Usando este programa parece que los dictados son los ayunos, los segundos, la lista con los bi_contains terceros:

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