Come si può parallelizzare una ricerca regolare di una stringa lunga?

Question

Sto testando l'output di una simulazione per vedere se entra in un ciclo ad un certo punto, quindi ho bisogno di sapere se l'output si ripete. Ad esempio, potrebbero esserci 400 cifre, seguite da un ciclo di 400000 cifre. L'output consiste solo di cifre da 0-9. Ho la seguente funzione di espressione regolare che sto usando per abbinare ripetizioni in una sola lunga serie:

def repetitions(s): 
    r = re.compile(r"(.+?)\1+") 
    for match in r.finditer(s): 
     if len(match.group(1)) > 1 and len(match.group(0))/len(match.group(1)) > 4: 
      yield (match.group(1), len(match.group(0))/len(match.group(1))) 

Questa funzione funziona fantasticamente, ma ci vuole troppo tempo. Il mio test più recente è stato di 4 milioni di cifre e sono state necessarie 4,5 ore di ricerca. Non ha trovato ripetizioni, quindi ora ho bisogno di aumentare lo spazio di ricerca. Il codice riguarda solo se stesso con sottosequenze che si ripetono più di 4 volte perché sto considerando 5 ripetizioni per dare un set che può essere controllato manualmente: la simulazione genererà sottosequenze che si ripeteranno centinaia di volte. Sono in esecuzione su una macchina a quattro core e le cifre da controllare vengono generate in tempo reale. Come posso aumentare la velocità della ricerca?

Answer 1

In base alle informazioni fornite da nhahtdh in una delle altre risposte, alcune cose sono venute alla luce.

In primo luogo, il problema che si sta ponendo si chiama trovare "ripetizioni in tandem" o "quadrati".

secondo luogo, l'algoritmo data in http://csiflabs.cs.ucdavis.edu/~gusfield/lineartime.pdf trova z ripetizioni in tandem in O (n registro n + z) tempo ed è "ottimale", nel senso che non vi può essere che molte risposte . Potresti essere in grado di utilizzare parallelizzare le ricerche in tandem, ma per prima cosa dovrei cronometrare con il semplice approccio e dividere per 4 per vedere se è nell'intervallo di velocità che ti aspetti.

Inoltre, al fine di utilizzare questo approccio si sta andando ad avere bisogno O (n) spazio per memorizzare questo albero suffisso. Pertanto, se si dispone dell'ordine di 400.000 cifre, sarà necessario un ordine di 400.000 ore per la compilazione e 400.000 byte per memorizzare questo albero di suffisso.

Io non sono totalmente ciò che si intende cercando in "tempo reale", di solito lo considero un limite irrisorio per quanto tempo un'operazione può richiedere. Se è così, allora non succederà qui. Questo algoritmo deve leggere nell'intera stringa di input ed elaborare che prima dello inizi a ottenere risultati. In questo senso, è ciò che viene chiamato "off-line" algorithm,.

http://web.cs.ucdavis.edu/~gusfield/strmat.html ha codice C che è possibile scaricare. (Nel file tar strmat.tar.gz cercare repeats_tandem.c e repeats_tandem.h).

Alla luce di quanto sopra, se quell'algoritmo non è sufficientemente veloce o efficiente in termini di spazio, cercherò modi per cambiare o restringere il problema. Forse hai solo bisogno di un numero fisso di risposte (ad esempio fino a 5)? Se i cicli sono il risultato dell'esecuzione di istruzioni in un programma, dato che i linguaggi di programmazione (diversi dall'assembler) non hanno istruzioni "goto" arbitrarie, è possibile che ciò possa limitare i tipi di cicli che possono verificarsi e in qualche modo utilizzare di quella struttura potrebbe offrire un modo per velocizzare le cose.

Answer 2

sono sicuro che ci sia spazio per l'ottimizzazione, ma provate questo algoritmo su stringhe più corte per vedere come si confronta con la vostra soluzione attuale:

def partial_repeat(string): 
    l = len(string) 
    for i in range(2, l//2+1): 
     s = string[0:i] 
     multi = l//i-1 
     factor = l//(i-1) 
     ls = len(s) 
     if s*(multi) == string[:ls*(multi)] and len(string)-len(string[:ls*factor]) <= ls and s*2 in string: 
      return s 

 

>>> test_string 
'abc1231231231231' 
>>> results = {x for x in (partial_repeat(test_string[i:]) for i in range(len(test_string))) if x} 
>>> sorted(sorted(results, key=test_string.index), key=test_string.count, reverse=True)[0] 
'123' 

In questa stringa di prova, non è chiaro se i caratteri iniziali non ripetuti siano 'abc' o 'abc1', quindi la stringa ripetuta potrebbe essere '123' o '231'. Il precedente ordina ogni sottostringa trovata dalla sua prima apparizione nella stringa di test, ordina di nuovo (sorted() è un ordinamento stabile) per la frequenza più alta e prende il risultato migliore.

Con loop standard e min() anziché comprehensions e sorted():

>>> g = {partial_repeat(test_string[i:]) for i in range(len(test_string))} 
>>> results = set() 
>>> for x in g: 
...  if x and (not results or test_string.count(x) >= min(map(test_string.count, results))): 
...   results.add(x) 
... 
>>> min(results, key=test_string.index) 
'123' 

ho testato queste soluzioni con la stringa di prova 'abc123123a' applica (n for n in range(100, 10101, 500) per ottenere alcuni dati di temporizzazione. Ho inserito questi dati in Excel e utilizzato la sua funzione FORECAST() per stimare il tempo di elaborazione di una stringa di 4 milioni di caratteri a 430 secondi o circa sette minuti.

Answer 3

Quando un algoritmo è troppo lento, cambiare algoritmi.

Se siete alla ricerca di ripetere le stringhe, si potrebbe considerare l'utilizzo di uno schema di albero di suffissi: https://en.wikipedia.org/wiki/Suffix_tree

Questo troverà sottostringhe comuni per voi in tempo lineare. EDIT: @nhahtdh inb un commento qui sotto ha fatto riferimento a un documento che ti dice come selezionare tutte le ripetizioni in tandem z molto rapidamente. Se qualcuno upvotes la mia risposta, @nhahtdh dovrebbe logicamente ottenere un po 'del credito.

Non l'ho provato, ma immagino che potresti essere in grado di parallelizzare la costruzione dell'albero del suffisso stesso.