Fast String dentro de List Searching

Question

Utilizando Python 3, tengo una lista que contiene más de 100.000 cadenas (lista1), cada una de 300 caracteres como máximo. También tengo una lista de más de 9 millones de subcadenas (list2) -. Quiero contar el número de elementos de una subcadena en lista2 aparece en, por ejemplo,

list1 = ['cat', 'caa', 'doa', 'oat'] 
list2 = ['at', 'ca', 'do'] 

Quiero que la función retorne (asignada a lista2) :

[2, 2, 1] 

Normalmente, esto es muy simple y requiere muy poco. Sin embargo, debido al tamaño masivo de las listas, tengo problemas de eficiencia. Quiero encontrar la forma más rápida de devolver esa lista de contador.

He intentado listas de comprensiones, generadores, mapas, bucles de todo tipo y todavía tengo que encontrar una manera rápida de hacer esta tarea fácil. ¿Cuál es, teóricamente, la forma más rápida de completar este objetivo, de preferencia tomando los pasos O(len(list2)) muy rápidamente?

Answer 1

conjunto M = len(list1) y N = len(list2)

Para cada una de las N entradas en list2 que vas a tener que hacer comparaciones M en contra de las entradas en list1. Ese es el peor tiempo de ejecución de O(M x N). Si lo lleva más allá, tomemos cada entrada en list2 para que sea de longitud 1 y cada entrada en list1 tenga una longitud de 300, y luego obtenga un tiempo de ejecución de O(300M x N).

Si el rendimiento es realmente un problema, intente la programación dinámica. Aquí es un comienzo:

1) Ordenar list2 en orden ascendente de longitud de este modo:

['scorch', 'scorching', 'dump', 'dumpster', 'dumpsters'] 

2) clasificarlos en sublistas tal que cada entrada que precede es un subconjunto de la entrada de proceder de este modo:

[['scorch', 'scorching'] , ['dump', 'dumpster', 'dumpsters']] 

3) Ahora bien, si se compara contra list1 y 'scorch' no es allí, entonces usted no tiene que buscar 'scorching' tampoco. Del mismo modo, si 'dump' no está ahí, tampoco es 'dumpster' o 'dumpsters'

nota el caso peor tiempo de funcionamiento sigue siendo el mismo

Answer 2

No estoy seguro de cómo se puede evitar tener algún tipo de O (n ** 2) algoritmo. Aquí hay una implementación simple.

>>> def some_sort_of_count(list1, list2): 
>>>  return [sum(x in y for y in list1) for x in list2] 
>>> 
>>> list1 = ['cat', 'caa', 'doa', 'oat'] 
>>> list2 = ['at', 'ca', 'do'] 
>>> some_sort_of_count(list1, list2) 
[2, 2, 1] 

Answer 3

Creo que esta tarea puede ser resuelta en el tiempo lineal con una máquina Aho Corasick string matching. Consulte this respuesta para obtener información adicional (tal vez también obtenga ideas de las otras respuestas a esa pregunta; es casi la misma tarea y creo que Aho Corasick es la forma teórica más rápida de resolver esto).

Deberá modificar la máquina de coincidencia de cadenas de tal manera que, en lugar de devolver la coincidencia, aumente en uno el contador de cada subcadena coincidente. (Esto debería ser solo una modificación menor).