Versione ottimizzata di strstr (la ricerca ha lunghezza costante)

Question

Il mio programma C aveva molte chiamate di funzioni strstr. La libreria standard strstr è già veloce ma nel mio caso la stringa di ricerca ha sempre una lunghezza di 5 caratteri. Ho sostituito con una versione speciale per guadagnare un po 'di velocità:

 
int strstr5(const char *cs, const char *ct) 
{ 
    while (cs[4]) { 

     if (cs[0] == ct[0] && cs[1] == ct[1] && cs[2] == ct[2] && cs[3] == ct[3] && cs[4] == ct[4]) 
      return 1; 

     cs++; 
    } 

    return 0; 
} 

La funzione restituisce un intero perché è abbastanza per sapere se ct si verifica in cs. La mia funzione è semplice e più veloce rispetto a strstr standard in questo caso particolare, ma mi interessa sapere se qualcuno ha dei miglioramenti prestazionali che potrebbero essere applicati. Anche piccoli miglioramenti sono ben accetti.

Sommario:

• cs ha lunghezza di> = 10, ma altrimenti può variare. La lunghezza è conosciuta prima (non usata nella mia funzione). Lunghezza del CS è di solito da 100 a 200.
• ct ha lunghezza di 5
• contenuti di stringhe può essere qualsiasi cosa

---

Edit: Grazie per tutte le risposte e commenti. Devo studiare e testare le idee per vedere cosa funziona meglio. Inizierò con l'idea di MAK sul suffisso trie.

Answer 1

Ci sono diversi veloci string search algorithms. Prova ad esaminare gli algoritmi Boyer-Moore (come suggerito da Greg Hewgill), Rabin-Karp e KMP.

Se è necessario cercare molti piccoli motivi nello stesso grande corpo di testo, è anche possibile provare a implementare uno suffix tree o uno suffix array. Ma questi sono in qualche modo più difficili da capire e implementare correttamente.

Ma attenzione, queste tecniche sono molto veloci, ma offrono solo un'accelerazione notevole se le stringhe coinvolte sono molto grandi. Potresti non notare un'accelerazione apprezzabile per le stringhe meno di dire una lunghezza di 1000 caratteri.

EDIT:

Se siete alla ricerca sullo stesso testo più e più volte (cioè il valore di cs è sempre/spesso le stesse chiamate in tutto), si otterrà un grande aumento di velocità utilizzando un trie suffisso (Fondamentalmente un trie di suffissi). Dato che il tuo testo è piccolo come 100 o 200 caratteri, puoi usare il più semplice metodo O (n^2) per costruire il trie e poi fare più ricerche veloci su di esso. Ogni ricerca richiederebbe solo 5 confronti invece dei soliti 5 * 200.

Edit 2:

Come menzionato dal commento di caffetteria, di C strstr algoritmo è implementazioni dipendente. glibc usa un algoritmo di tempo lineare che dovrebbe essere più o meno veloce nella pratica dei metodi che ho menzionato.Mentre il metodo dell'OP è asintoticamente più lento (O (N * m) invece di O (n)), è più veloce probabilmente a causa del fatto che sia n che m (le lunghezze del pattern e del testo) sono molto piccole e non deve fare nessuno dei lunghi preelaboramenti nella versione di glibc.

Answer 2

Il codice può accedere a cs oltre i limiti della sua assegnazione se cs è più corto di 4 caratteri.

Un'ottimizzazione comune per stringa di ricerca è quello di utilizzare l'algoritmo di Boyer-Moore in cui si inizia a guardare in cs dalla fine di quello che sarebbe ct. Vedi la pagina collegata per una descrizione completa dell'algoritmo.

Answer 3

La riduzione del numero di confronti aumenta la velocità della ricerca. Mantenere un int in esecuzione della stringa e confrontarlo con un int fisso per il termine di ricerca. Se corrisponde confronta l'ultimo carattere.

uint32_t term = ct[0] << 24 | ct[1] << 16 | ct[2] << 8 | ct[3]; 
uint32_t walk = cs[0] << 24 | cs[1] << 16 | cs[2] << 8 | cs[3]; 
int i = 0; 

do { 
    if (term == walk && ct[4] == cs[4]) { return i; } // or return cs or 1 
    walk = (walk << 8) | cs[4]; 
    cs += 1; 
    i += 1; 
} while (cs[4]); // assumes original cs was longer than ct 
// return failure 

Aggiungere controlli per un breve cs.

Modifica:

Aggiunte le correzioni dai commenti. Grazie.

Questo potrebbe essere facilmente adottato per utilizzare valori a 64 bit. È possibile memorizzare cs [4] e ct [4] in variabili locali invece di assumere che il compilatore lo faccia per te. È possibile aggiungere 4 a cs e ct prima del ciclo e utilizzare cs [0] e ct [0] nel ciclo.

Answer 4

L'interfaccia di strstr impone alcuni vincoli che possono essere superati. Richiede stringhe con terminazione nulla e ogni concorrente che per primo fa un "strlen" del suo bersaglio perderà. Non ci vuole alcun argomento di "stato", quindi i costi di set-up non possono essere ammortizzati attraverso molte chiamate con (diciamo) lo stesso target o modello. Ci si aspetta che lavori su una vasta gamma di input, compresi target/pattern molto brevi e dati patologici (considerare la ricerca di "ABABAC" in una stringa di "ABABABABAB ... C"). anche libc ora dipende dalla piattaforma. Nel mondo x86-64, SSE2 ha sette anni e lo strlen e strchr di libc che utilizza SSE2 sono 6-8 volte più veloci degli algoritmi ingenui. Sulle piattaforme Intel che supportano SSE4.2, strstr utilizza l'istruzione PCMPESTRI. Ma puoi battere anche quello.

Boyer-Moore's (e Turbo B-M e Backward Oracle Matching, et al) hanno un tempo di installazione che li mette praticamente fuori gioco, senza contare il problema della stringa con terminazione nulla. Horspool è un B-M limitato che funziona bene nella pratica, ma non fa bene i casi limite. La cosa migliore che ho trovato in questo campo è BNDM ("Backward Nondeterministic Directed-Acyclic-Word-Graph Matching"), la cui implementazione è più piccola del suo nome :-)

Ecco alcuni frammenti di codice che potrebbero essere di interesse. Intelligent SSE2 beats naive SSE4.2 e gestisce il problema di terminazione null. A BNDM implementation mostra un modo per mantenere i costi di installazione. Se hai familiarità con Horspool, noterai la somiglianza, ad eccezione del fatto che BNDM utilizza le maschere di bit anziché gli skip-offset. Sto per pubblicare come risolvere il problema di null-terminator (in modo efficiente) per algoritmi di suffisso come Horspool e BNDM.

Un attributo comune di tutte le buone soluzioni è la suddivisione in algoritmi diversi per lunghezze di argomenti differenti. Un esempio di è Sanmayce "Railgun" function.

Answer 5

Non è possibile eseguire una buona implementazione su un computer x86 moderno.

I nuovi processori Intel hanno un'istruzione che richiede 16 byte della stringa che si sta esaminando, fino a 16 byte della stringa di ricerca e in una singola istruzione restituisce quale è la prima posizione di byte in cui potrebbe essere la stringa di ricerca (o se non ce n'è). Ad esempio se cerchi "Hello" nella stringa "abcdefghijklmnHexyz" la prima istruzione ti dirà che la stringa "Hello" potrebbe iniziare con offset 14 (perché leggendo 16 byte, il processore ha i byte H, e, sconosciuto quale potrebbe essere essere la posizione di "Ciao" .L'istruzione successiva che inizia all'offset 14 quindi dice che la stringa non è presente.E sì, sa di zero byte finali.

Questo è due istruzioni per trovare che una stringa di cinque caratteri non è presente in una stringa di 19 caratteri. Prova a batterlo con un codice caso speciale. (Ovviamente questo è costruito specificatamente per istruzioni strstr, strcmp e simili).