Ho un determinato array di byte in C e devo abbinarlo a più array di byte e restituire true se c'è una corrispondenza.
Posso creare vari memcmp ma ritengo che sia molto inefficiente.
Conosci un modo migliore?
Ho un determinato array di byte in C e devo abbinarlo a più array di byte e restituire true se c'è una corrispondenza.
Posso creare vari memcmp ma ritengo che sia molto inefficiente.
Conosci un modo migliore?
È un DFA degenerato senza cicli. Per l'implementazione hai un int state e un int nextState[256] per ogni stato.
Per gli stati di corrispondenza, dovresti rendere il numero di stato negativo, quindi sai quando viene raggiunto.
In linea di principio una ricerca Trie è ciò che desideri, ma dovresti profilare i dati effettivi per scoprire quando ciò ha effettivamente un rendimento migliore (potrebbe essere sempre peggio a meno che non si riesca a trovare un layout cache-friendly).
Modifica basata sui commenti:
Stai abbinando uno stream o pacchetti discreti?
Se il primo e hai bisogno di gestire le partite che si estendono lungo il confine tra array di byte consecutivi, sicuramente vuoi il DFA di ratchet.
Se quest'ultimo, il tuo compromesso dipende da:
Caratteristiche hardware
Gli effetti cache che ho menzionato in origine sono molto dipendenti dalla piattaforma.
Se hai una cache veloce di dimensioni ragionevoli ( ie le tue sottostringhe si adattano a essa), allora la percentuale di memcmp potrebbe essere più veloce. Profilo. Puoi velocizzare questo ordinando le sottostringhe e utilizzando il valore di ritorno di memcmp per eseguire la ricerca binaria su di esse.
Soprattutto per un sistema embedded, se la cache è piccola o la penalità per mancare non è così grande, o le sottostringhe non si adattano comunque alla cache, quindi inseguire i nodi Trie va bene.
tl; dr - Trie è asintoticamente ottimale ma gli effetti di cache possono dominare. Misuralo!
Leggi altre domande sui tag c algorithms efficiency comparison pattern-matching