Ottimizzazione di un algoritmo di ricerca in C

Question

Possono le prestazioni di questo algoritmo di ricerca sequenziale (tratto da La Pratica della Programmazione) essere migliorata utilizzando una qualsiasi delle C nativo di utilità, ad esempiose ho impostato la variabile da un registro variabile ?

int lookup(char *word, char*array[])
{
    int i

    for (i = 0; array[i] != NULL; i++)
        if (strcmp(word, array[i]) == 0)
            return i;

    return -1;
}

Answer 1

Sì, ma solo leggermente.Una molto più grande miglioramento delle prestazioni può essere ottenuto utilizzando le migliori algoritmi (ad esempio mantenere la lista ordinata e facendo una ricerca binaria).

In generale l'ottimizzazione di un dato algoritmo solo si ottiene finora.La scelta di un algoritmo migliore (anche se non è completamente ottimizzato), possono dare un notevole (ordine di grandezza) il miglioramento delle prestazioni.

Answer 2

Penso, non farà molta differenza.Il compilatore ottimizza in quella direzione.

Inoltre, la variabile i non è molto d'impatto, parola rimane costante per tutta la funzione e il resto è troppo grande per adattarsi a qualsiasi registro.È solo una questione di come la dimensione della cache è e se l'intera matrice, potrebbe rientrare in là.

I confronti tra stringhe piuttosto costoso computazionalmente.

Si può forse utilizzare un qualche tipo di hash per la matrice prima di effettuare la ricerca?

Answer 3

Non c'è tecnica ben nota come sentinal metodo.Per utilizzare sentinal metodo, è necessario conoscere la lunghezza di "array[]".È possibile rimuovere "array[i] != NULL" confronto utilizzando sentinal.

int lookup(char *word, char*array[], int array_len)
{
    int i = 0;
    array[array_len] = word;
    for (;; ++i)
        if (strcmp(word, array[i]) == 0) 
            break;
    array[array_len] = NULL;
    return (i != array_len) ? i : -1;
}

Answer 4

Se stai leggendo TPOP, vi verrà poi vedere come fanno di questa ricerca, che molte volte più veloce con diverse strutture di dati e algoritmi.

Ma si può rendere le cose un po ' più veloce, sostituendo le cose come

for (i = 0; i < n; ++i)
    foo(a[i]);

con

char **p = a;
for (i = 0; i < n; ++i)
    foo(*p);
    ++p;

Se c'è un valore noto alla fine dell'array (ad es.NULL), è possibile eliminare il contatore di ciclo:

for (p = a; *p != NULL; ++p)
    foo(*p)

Buona fortuna, che è un ottimo libro!

Answer 5

Per ottimizzare il codice che la cosa migliore sarebbe quella di riscrivere la strcmp di routine, dal momento che si sta solo il controllo per l'uguaglianza e la non necessità di valutare l'intera parola.

Diverso da quello che si può fare molto altro.Non è possibile classificare come appare siete alla ricerca per il testo all'interno di un testo più ampio.Binario di ricerca non funziona dato che il testo è improbabile per essere ordinati.

Il mio 2p (C-psuedocode):

wrd_end = wrd_ptr + wrd_len;
arr_end = arr_ptr - wrd_len;
while (arr_ptr < arr_end)
{
    wrd_beg = wrd_ptr; arr_beg = arr_ptr;
    while (wrd_ptr == arr_ptr)
    {
        wrd_ptr++; arr_ptr++;
        if (wrd_ptr == wrd_en)
            return wrd_beg;
    }
    wrd_ptr++;
}

Answer 6

Mark Harrison:Il ciclo for non terminerà mai!(++p è rientrato, ma non è in realtà all'interno del per :-)

Inoltre, il passaggio tra puntatori e l'indicizzazione in genere non hanno alcun effetto sulle prestazioni, né sarà l'aggiunta di registrare parole chiave (come mat già menziona), il compilatore è abbastanza intelligente per applicare queste trasformazioni, se del caso, e se ti dico che abbastanza la tua cpu arco, si farà un lavoro migliore di questi che manuale psuedo-micro-ottimizzazioni.

Answer 7

Un modo più veloce per la corrispondenza di stringhe potrebbe essere quella di memorizzare loro Pascal stile.Se non avete bisogno di più di 255 caratteri per la stringa, negozio di circa come questo, con il conte nel primo byte:

char s[] = "\x05Hello";

Allora si può fare:

for(i=0; i<len; ++i) {
    s_len = strings[i][0];
    if(
        s_len == match_len
        && strings[i][s_len] == match[s_len-1]
        && 0 == memcmp(strings[i]+1, match, s_len-1)
    ) {
        return 1;
    }
}

E per ottenere davvero veloce, aggiungere memoria prefetch suggerimenti per la stringa di avvio + 64, + 128 e l'inizio della stringa successiva.Ma questo è solo pazzo.:-)

Answer 8

Un altro modo veloce per farlo è quello di ottenere il vostro compilatore di utilizzare un set di istruzioni SSE2 ottimizzato memcmp.Fisso-lunghezza char array e allineare in modo che la stringa inizia a 64-byte di allineamento.Quindi credo che si può ottenere il bene memcmp funzioni se si passa const char match[64] invece di const char *corrispondenza in funzione, o strncpy partita in un 64,128,256,qualunque sia la matrice di byte.

Pensare un po ' di più su questo, questi SSE2 funzioni match potrebbe essere parte di pacchetti come Intel e AMD acceleratore librerie.Check them out.

Answer 9

Realisticamente, l'impostazione mi da un registro variabile non fare nulla che il compilatore non fa già.

Se siete disposti a trascorrere qualche ora di anticipo pre-elaborazione di riferimento array, si consiglia di google "più Veloce Del Mondo Scrabble Programma" e implementare.Spoiler:si tratta di un DAG ottimizzato per le ricerche di carattere.

Answer 10

/* there is no more quick  */
int lookup(char *word, char*array[])
{
    int i;
    for(i=0; *(array++) != NULL;i++)
        if (strcmp(word, *array) == 0)
            return i;
    return -1;
}