Forma más eficiente de encontrar si una lista grande contiene una cadena específica (Python)

Question

Tengo un archivo que contiene aproximadamente todas las palabras en inglés (~ 60k palabras, ~ 500k caracteres). Quiero probar si una determinada palabra que recibo como entrada es "en inglés" (es decir, si esta palabra exacta está en la lista).

¿Cuál sería la forma más eficiente de hacer esto en Python?

La solución trivial es cargar el archivo en una lista y verificar si la palabra está en esa lista. La lista se puede ordenar, lo que creo que reducirá la complejidad a O (logn). Sin embargo, no estoy seguro de cómo Python implementa la búsqueda a través de listas, y si hay una penalización de rendimiento si una lista tan grande está en la memoria. ¿Puedo "abusar" del hecho de que puedo ponerle un límite a la longitud de las palabras? (por ejemplo, decir que el más largo tiene 15 caracteres de longitud).

Tenga en cuenta que ejecuto la aplicación en una máquina con mucha memoria, por lo que me importa menos el consumo de memoria que la velocidad y la utilización de la CPU.

Gracias

Answer 1

El python Set es lo que debe intentar.

Un objeto de conjunto es una colección desordenada de distintos objetos hashable. Los usos comunes incluyen la prueba de membresía , eliminar duplicados de una secuencia y calcular operaciones matemáticas como intersección, unión, diferencia y diferencia simétrica.

Answer 2

Básicamente, se está probando si un miembro se encuentra en un conjunto o no, ¿verdad?

Si es así, y porque dijiste que tienes mucha memoria, ¿por qué no simplemente cargar todas las palabras como claves en Memcache, y luego para cada palabra, simplemente verifica si está presente en Memcache o no?

O use esa estructura de datos utilizada por bash para autocompletar los nombres de los comandos; esto es rápido y muy eficiente en la memoria (no recuerdo el nombre).

Answer 3

A Trie estructura se adaptaría a sus propósitos. Sin duda, hay implementaciones de Python disponibles ...

Answer 4

Si el consumo de memoria no es un problema y las palabras no cambian, la forma más rápida de hacerlo es poner todo en un hash y buscar de esa manera. En Python, este es el Set. Tendrás búsqueda constante.

Answer 5

500k character no es una gran lista. si los elementos de su lista son únicos y necesita realizar esta búsqueda varias veces, utilice set, lo que reduciría la complejidad a O(1) en el mejor de los casos.

Answer 6

Muestra de código Python:

L = ['foo', 'bar', 'baz'] # Your list 
s = set(L) # Converted to Set 

print 'foo' in s # True 
print 'blah' in s # False 

Answer 7

Dos cosas:

El Python conjunto mutable 'tipo tiene un método de 'añadir'(s.add (elemento)), por lo que podría ir a la derecha de leyendo (una línea) desde su archivo grande directamente en un conjunto sin usar una lista como una estructura de datos intermedia.

Python le permite 'saltear' una estructura de datos, por lo que podría guardar su gran conjunto en un archivo y guardar el tiempo de reiniciar el conjunto.

En segundo lugar, he estado buscando una lista de todas las palabras de una sola sílaba en inglés para mi propia diversión, pero las que he encontrado mencionadas parecen ser de propiedad exclusiva. Si no es intrusivo, ¿podría preguntar si otros pueden obtener su lista de palabras en inglés?

Answer 8

La conversión de la lista a un conjunto solo será útil si ejecuta repetidamente este tipo de consulta en comparación con los datos, al igual que ordenando la lista y realizando una búsqueda binaria. Si sólo vas a tirar de datos fuera de la lista una vez, un viejo y simple búsqueda lineal es la mejor opción:

if 'foo' in some_list: 
    do_something() 

De lo contrario, lo mejor es utilizar un conjunto como se ha mencionado o un binario buscar. Cuál elegir debería depender en gran medida de qué tan grande es la información y cuánta memoria puede ahorrar. Me dijeron que las listas realmente grandes tienden a beneficiarse más del hash, aunque la cantidad de memoria que se utiliza puede ser prohibitivamente cara.

Finalmente, una tercera opción es que usted puede importar los datos en una base de datos sqlite y leer directamente de ellos. Sqlite es muy rápido y puede ahorrarte la molestia de cargar toda la lista del archivo. Python tiene un muy buen built-in sqlite library.

Answer 9

Otros le han dado la forma en memoria usando set(), y esta generalmente será la manera más rápida, y no debería gravar su memoria para un conjunto de datos de 60k palabras (unos pocos MiB como máximo). Debería poder construir su conjunto con:

f=open('words.txt') 
s = set(word.strip() for word in f) 

Sin embargo, requiere cierto tiempo para cargar el conjunto en la memoria. Si está revisando muchas palabras, no hay problema, el tiempo de búsqueda lo compensará con creces. Sin embargo, si solo va a consultar una palabra por ejecución de comando (por ejemplo, esta es una aplicación de línea de comandos como "checkenglish [word]") el tiempo de inicio será más largo de lo que le hubiera tomado solo para buscar a través de la línea de archivo nombre del autor.

Si esta es su situación, o si tiene un conjunto de datos mucho mayor, usar un formato en disco puede ser mejor. La forma más simple sería usar el módulo dbm. Crear una base de datos a partir de una lista de palabras con:

import dbm 
f=open('wordlist.txt') 
db = dbm.open('words.db','c') 
for word in f: 
    db[word] = '1' 
f.close() 
db.close() 

A continuación, el programa puede comprobar membresía con:

db = dbm.open('words.db','r') 
if db.has_key(word): 
    print "%s is english" % word 
else: 
    print "%s is not english" % word 

Esto será más lento que una búsqueda conjunto, ya que no habrá acceso al disco, pero será más rápido que la búsqueda, tiene poca memoria y no tiene un tiempo de inicialización significativo.

También hay otras alternativas, como el uso de una base de datos SQL (por ejemplo, sqlite).