Ho un compito in cui devo cercare le sequenze in un file. Quando faccio un'applicazione di test, ho letto il file come stringa (File.ReadAllText) e ho usato string.IndexOf per cercare una sequenza. Quando ho provato ad implementare lo stesso algoritmo con i byte (leggendo il file come array di byte e cercando array di byte nell'array di byte), ho notato che cercare byte [] in byte [] è circa 3 volte più lento di cercare stringa in stringa . Ho fatto in modo di verificarlo a fondo, e esattamente lo stesso codice, uno che usa il byte [] e l'altro usando la stringa, richiede 3 volte tanto da eseguire - come, 16s per byte vs ~ 5s per string.Velocità di ricerca del byte [] in byte [] e stringa in stringa - perché quest'ultimo è più veloce?
Per la ricerca di matrici di byte, ho usato i modi descritti qui byte[] array pattern search. Per cercare le stringhe, ho usato la funzione IndexOf integrata della classe string. Ecco una delle implementazioni di IndexOf per byte [] Ho provato:
public int IndexOf(byte[] source, byte[] pattern, int startpos = 0)
{
int search_limit = source.Length - pattern.Length;
for (int i = startpos; i < search_limit; i++)
{
if (source[i] == pattern[0])
{
bool found = true;
for (int j = 1; j < pattern.Length; j++)
{
if (source[i + j] != pattern[j])
{
found = false;
break;
}
}
if (found)
return i;
}
}
return -1;
}
Fondamentalmente, alzando corrispondenza successiva sequenza di byte in byte matrice prende tre volte finchè alzando corrispondenza successiva sequenza di caratteri in stringa. La mia domanda è: PERCHÉ?
Qualcuno sa come .Net gestisce la ricerca di caratteri in stringa, che tipo di ottimizzazione esegue, quale algoritmo utilizza? C'è un algoritmo più veloce di quello che sto usando qui? Forse qualcuno ha un'idea di cosa sto facendo male qui in modo che ci voglia più tempo del dovuto? Non riesco davvero a capire come cercare stringa di stringa può essere 3 volte più veloce di byte [] in byte [] ...
AGGIORNAMENTO: Ho provato l'algoritmo non sicuro come suggerito. Era il seguente:
public static unsafe long IndexOfFast(byte[] Haystack, byte[] Needle, long startpos = 0)
{
long i = startpos;
fixed (byte* H = Haystack) fixed (byte* N = Needle)
{
for (byte* hNext = H + startpos, hEnd = H + Haystack.LongLength; hNext < hEnd; i++, hNext++)
{
bool Found = true;
for (byte* hInc = hNext, nInc = N, nEnd = N + Needle.LongLength; Found && nInc < nEnd; Found = *nInc == *hInc, nInc++, hInc++) ;
if (Found) return i;
}
return -1;
}
}
}
la cosa strana è che in realtà si è rivelato essere due volte più lento! L'ho cambiato per aggiungere il mio Tweak personali (controllo prima lettera prima di tentare di scorrere ago) e sembra che questa società:
public static unsafe long IndexOfFast(byte[] Haystack, byte[] Needle, long startpos = 0)
{
long i = startpos;
fixed (byte* H = Haystack) fixed (byte* N = Needle)
{
for (byte* hNext = H + startpos, hEnd = H + Haystack.LongLength; hNext < hEnd; i++, hNext++)
{
if (*hNext == *N)
{
bool Found = true;
for (byte* hInc = hNext+1, nInc = N+1, nEnd = N + Needle.LongLength; Found && nInc < nEnd; Found = *nInc == *hInc, nInc++, hInc++) ;
if (Found) return i;
}
}
return -1;
}
}
Ora, ci vuole lo stesso tempo di eseguire come quello sicuro. La mia domanda è ancora una volta - qualche idea perché? Non dovrebbe essere più veloce perché non è sicuro e funziona con i puntatori, rispetto alla sicurezza?
Implementare [questo algoritmo] (http://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm) per gli array di byte e testare nuovamente. – I4V
Bene, la maggior parte delle funzioni di confronto delle stringhe e 'IndexOf' si riducono a una chiamata CLR interna, in genere' InternalFindNLSStringEx' o 'InternalCompareString'. Probabilmente l'implementazione CLR nativa sarà più veloce. – vcsjones
OK, ora che hai una soluzione aritmetica puntatore se vuoi renderla ancora più veloce devi iniziare a pensare a quali operazioni macchina vengono effettivamente eseguite lì. Ad esempio: cos'è più veloce: spostare un byte da una parola a 32 bit quattro volte o creare quattro maschere, una con il byte in ciascuna delle quattro posizioni, considerare l'array di byte come una matrice di int e controllare ogni int per vedere se corrisponde a una qualsiasi delle tue maschere quando ANDed con la maschera? Quest'ultimo potrebbe essere un paio di cicli più veloce. Questo è il tipo di cose che le persone fanno quando ottimizzano questo algoritmo. –