Fast String all'interno di Ricerca elenco

Question

Utilizzando Python 3, ho una lista contenente oltre 100.000 stringhe (lista1), ciascuna di lunghezza massima di 300 caratteri. Ho anche una lista di oltre 9 milioni di sottostringhe (list2) -. Voglio contare quanti elementi di una stringa in lista2 appare in Per esempio,

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

Voglio la funzione per tornare (mappato a list2) :

[2, 2, 1] 

Normalmente, questo è molto semplice e richiede pochissimo. Tuttavia, a causa delle enormi dimensioni degli elenchi, ho problemi di efficienza. Voglio trovare il modo più veloce per restituire quella lista contatore.

Ho provato list comprehensions, generatori, mappe, loop di tutti i tipi e non ho ancora trovato un modo veloce per fare questo compito facile. Qual è in teoria il modo più veloce per completare questo obiettivo, preferibilmente prendendo i passi O(len(list2)) molto rapidamente?

Answer 1

set M = len(list1) e N = len(list2)

Per ciascuna delle voci N in list2 si sta andando ad avere a che fare paragoni M contro le voci in list1. Questo è il peggior tempo di esecuzione di O(M x N). Se la prendi oltre, lascia che ogni voce in list2 sia di lunghezza 1 e ogni voce in list1 sia di lunghezza 300, quindi hai un tempo di esecuzione di O(300M x N).

Se le prestazioni sono davvero un problema, provare la programmazione dinamica. Qui è un inizio:

1) ordina list2 in ordine crescente di lunghezza in questo modo:

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

2) ordinarli in sottoliste tale che ogni voce precede è un sottoinsieme della voce procedimento modo:

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

3) Ora, se si confronta contro list1 e 'scorch' non è in là, allora non c'è bisogno di cercare 'scorching' sia. Allo stesso modo se 'dump' non è lì dentro, nessuno dei due è 'dumpster' o 'dumpsters'

nota il caso peggiore tempo di funzionamento è sempre lo stesso

Answer 2

Non so come si possa evitare di avere un qualche tipo di O (n ** 2) algoritmo. Ecco una semplice implementazione.

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

Credo questo compito può essere risolto in tempo lineare con una macchina Aho Corasick string matching. Vedere this risposta per ulteriori informazioni (forse si ottengono idee anche dalle altre risposte a quella domanda - è quasi lo stesso compito e penso che Aho Corasick sia il modo teoricamente più veloce per risolvere questo problema).

Dovrete modificare la macchina per la corrispondenza delle stringhe in modo tale che, invece di restituire la corrispondenza, aumenti di uno il contatore di ogni sottostringa corrispondente. (Questa dovrebbe essere solo una piccola modifica).