veloce confronto tra stringhe in C

Question

momento ho questo tipo di ciclo

while(1) 
{ 
    generate_string(&buffer); 

    for(int i = 0; i < filelines; i++) 
    { 
     if(strcmp(buffer,line[i]) == 0) 
     { 
      /* do something */ 
     } 
    } 
} 

Ho un file con pochi milioni di stringhe (che si spera dovrebbe essere dimezzato a volte presto), il numero di tutte queste stringhe è memorizzato in righe di file

riga [i] è fondamentalmente dove viene memorizzata la stringa stessa.

Attualmente, a causa del confronto di questi milioni di stringhe, funzione generate_string (buffer &); viene eseguito circa 42 volte al secondo. Esiste un modo più rapido per eseguire il confronto tra stringhe in C?

Answer 1

strcmp di solito è ottimizzato per tutti i fornitori. Tuttavia, se non sei soddisfatto di questo si può provare:

• Lookup Burst Tries
• Utilizzare un albero suffisso per il confronto di stringhe veloce - vedi l'articolo this
• A seconda delle dimensioni di stringhe nell'applicazione puoi scrivere un comparatore di stringhe personalizzato. Per esempio: GNU libc usato per avere questa ottimizzazione per i piccoli archi, dove hanno provato le stringhe di dimensioni inferiori a cinque byte come numeri interi. MS cl ha anche alcune ottimizzazioni per stringhe di piccole dimensioni (fare una ricerca).

Ma ancora più importante assicurarsi che strcmp è il vostro reale collo di bottiglia.

Answer 2

Non so che c'è un modo più veloce di chiamare strcmp di fare confronti tra stringhe, ma si può forse evitare chiamando strcmp così tanto. Utilizzare una tabella hash per memorizzare le stringhe e quindi si può verificare se la stringa in buffer è nella tabella hash. Se l'indice di un hit è importante quando "fai qualcosa", la tabella può mappare le stringhe agli indici.

Answer 3

Si può provare qualcosa di 'buon mercato', come lo screening sulla base del primo carattere. Se i primi caratteri non corrispondono, le stringhe non possono essere uguali. Se corrispondono, quindi chiama strcmp per confrontare l'intera stringa. Potresti voler considerare un algoritmo migliore se è appropriato per la tua situazione; gli esempi consistono nell'ordinare il file/le linee e fare una ricerca binaria, usando una tabella hash o tecniche simili per le tabelle di stringhe.

Answer 4

si può essere in grado di cavarsela con un confronto binario in questo caso perché il programma non fa effettivamente sorta, ma a confronto per l'uguaglianza.

si può anche migliorare la velocità di confronto qui determinando le lunghezze di anticipo (di cui, naturalmente, variano abbastanza). quando la lunghezza non corrisponde, do something non si verificherà.

naturalmente, hashing qui sarebbe un'altra considerazione a seconda di quante volte si legge il valore di hash.

Answer 5

Se ottengo la domanda correttamente, è necessario verificare se una stringa è lungo tutte le righe lette finora. Proporrei di utilizzare un TRIE o anche meglio un Patricia tree dalle righe del file.In questo modo, invece di andare su tutte le linee, puoi controllare in modo lineare se la tua corda è presente (e con un po 'più di sforzo - dove).

Answer 6

Stai già compilando con l'ottimizzazione, giusto?

Se si dispone di una struttura dati Trie o hashtable situata nel luogo, pronta per l'uso, è necessario.

In caso contrario, una modifica abbastanza semplice che probabilmente accelera le cose è ordinare l'array line una volta, prima di iniziare a generare stringhe da cercare. Quindi eseguire la ricerca binaria per buffer nell'array ordinato. È facile perché le due funzioni di cui hai bisogno sono standard: qsort e bsearch.

Una ricerca binaria in una matrice ordinata deve fare solo il log confronti della stringa di righe (filelines), anziché di fileline. Quindi nel tuo caso si tratta di confronti di stringhe di 20 elementi per chiamata a generate_string anziché pochi milioni. Dalle cifre che hai fornito, penso che puoi ragionevolmente aspettarti che vada 20-25 volte più velocemente, anche se non prometto nulla.

Answer 7

Posso assicurarvi, la funzione strcmp NON è ASSOLUTAMENTE il collo di bottiglia. Tipicamente, strcmp è ben ottimizzato e può fare confronti a 32 o 64 bit per stringhe più lunghe di 4/8 byte a seconda dell'architettura. Sia newlib che GNU libc fanno questo. Ma anche se si guardano i byte di entrambe le stringhe per 20 volte, non importa quanto le scelte della struttura dati algo & fatte qui.

Il vero collo di bottiglia è l'algoritmo di ricerca O (N). È possibile utilizzare un singolo passaggio O (N log N) nel file alla struttura dati appropriata (che si tratti di un normale BST, di un trie o di un semplice array ordinato) per eseguire ricerche O (log N).

Orso con me qui - segue molta matematica. Ma penso che questa sia una buona opportunità per illustrare il motivo per cui la scelta della struttura dei dati dell'algoritmo & è a volte molto più importante del metodo di confronto delle stringhe. Steve tocca questo, ma volevo spiegarlo in modo un po 'più profondo.

Con N = 1e6, log (1e6, 2) = 19,9, quindi arrotondare fino a 20 confronti su una struttura dati ideale.

Attualmente si sta eseguendo una ricerca nel caso peggiore di operazioni O (N) o 1e6.

Quindi, diciamo che si costruisce un albero rosso-nero con O (log N) tempo di inserimento e si inseriscono N elementi, ovvero O (N log N) tempo per costruire l'albero. Quindi sono necessarie operazioni 1e6 x 20 o 20e6 per costruire il tuo albero.

Nel vostro attuale approccio, la costruzione della struttura dati è O (N), o operazioni 1e6, ma il tempo di ricerca nel caso peggiore è O (N). Quindi nel momento in cui leggi il file e fai solo 20 operazioni di ricerca, sei pronto per un caso teorico peggiore di 21.000.000 di operazioni. In confronto, il tuo caso peggiore con un albero rosso-nero e 20 ricerche è 20.000.400 operazioni, o 999.600 operazioni MEGLIO della ricerca O (N) su un array non ordinato. Quindi, in 20 ricerche, sei al primo punto in cui una struttura dati più sofisticata è davvero redditizia. Ma guarda cosa succede a 1000 ricerche:

Array non ordinato = inizializzazione + 1000 x tempo di ricerca = O (N) + 1000 * O (N) = 1.000.000 + 2.000.000.000 = 2.001.000.000 operazioni.

Rosso-nero = inizializzazione + 1000 x tempo di ricerca = O (N log N) + 1000 * O (log N) = 20.000.000 + 20.000 = 20.020.000 operazioni.

2,001,000,000/20,020,000 ~ = 100x tante operazioni per la ricerca O (N).

In 1e6 ricerche, è (1e6 + 1e6 * 1e6)/(20e6 + 1e6 * 20) = 25.000 volte il numero di operazioni.

Assumere che il computer sia in grado di gestire le "operazioni" 40e6 necessarie per eseguire le ricerche del registro N in 1 minuto. Ci vorrebbero 25.000 minuti o 17 GIORNI per fare lo stesso lavoro con il tuo attuale algoritmo. Oppure un altro modo di guardare è che l'algoritmo di ricerca O (N) può gestire solo 39 ricerche nel tempo in cui l'algoritmo O (log N) può fare 1.000.000. E più ricerche fai, più brutto diventa.

Vedere le risposte da Steve e dirkgently per diverse scelte migliori delle strutture di dati & algoritmi. La mia unica cautela aggiuntiva sarebbe che qsort() suggerito da Steve potrebbe avere una complessità nel caso peggiore di O (N * N), che è molto, molto peggio di O (N log N) che si ottiene con un heapsort o vari strutture ad albero

Answer 8

Optimization of Computer Programs in C

È possibile salvare un po 'di tempo controllando i primi caratteri delle stringhe in questione prima di fare la chiamata. Ovviamente, se i primi caratteri differiscono, non c'è motivo di chiamare strcmp per controllare il resto. A causa della distribuzione non uniforme delle lettere nei linguaggi naturali, il payoff non è 26: 1 ma più simile a 15: 1 per i dati maiuscoli.

#define QUICKIE_STRCMP(a, b) (*(a) != *(b) ? \ 
    (int) ((unsigned char) *(a) - \ 
     (unsigned char) *(b)) : \ 
    strcmp((a), (b))) 

Se il dizionario delle parole che si sta utilizzando sono ben definiti (il che significa che non ti dispiaccia forma valore di ritorno strcmp ma il 0 == uguale), per esempio, una serie di argomenti della riga di comando che inizia con lo stesso prefisso, ex: tcp-accept, tcp-reject di confrontare non il primo ma l'ennesimo char, in questo caso il 4o char, ad esempio:

#define QUICKIE_STRCMP(a, b, offset) \ 
      (*(a+offset) != *(b+offset))\ ? -1 : strcmp((a), (b)))