Optimierung eines Suchalgorithmus in C

Question

Kann die Leistung dieses sequentiellen Suchalgorithmus (entnommen ausDie Praxis des Programmierens) mithilfe eines der nativen Dienstprogramme von C verbessert werden, z.Wenn ich die i-Variable auf eine Registervariable setze?

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

Ja, aber nur sehr geringfügig.Durch die Verwendung besserer Algorithmen (z. B. Sortieren der Liste und Durchführen einer binären Suche) kann eine viel größere Leistungsverbesserung erzielt werden.

Im Allgemeinen bringt Sie die Optimierung eines bestimmten Algorithmus nur bis zu einem gewissen Punkt.Die Wahl eines besseren Algorithmus (auch wenn dieser nicht vollständig optimiert ist) kann zu einer erheblichen Leistungsverbesserung (um Größenordnungen) führen.

Answer 2

Ich denke, es wird keinen großen Unterschied machen.Der Compiler wird es bereits in diese Richtung optimieren.

Außerdem hat die Variable i keine große Auswirkung, das Wort bleibt während der gesamten Funktion konstant und der Rest ist zu groß, um in ein beliebiges Register zu passen.Es kommt nur darauf an, wie groß der Cache ist und ob das gesamte Array dort hineinpasst.

String-Vergleiche sind rechenintensiv.

Können Sie vor der Suche vielleicht eine Art Hashing für das Array verwenden?

Answer 3

Es gibt eine bekannte Technik wie die Sentinal-Methode.Um die Sentinal-Methode verwenden zu können, müssen Sie die Länge von „array[]“ kennen.Sie können „array[i] != NULL“ beim Vergleich entfernen, indem Sie Sentinal verwenden.

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

Wenn Sie TPOP lesen, werden Sie als nächstes sehen, wie sie diese Suche mit unterschiedlichen Datenstrukturen und Algorithmen um ein Vielfaches beschleunigen.

Aber Sie können die Dinge etwas schneller machen, indem Sie Dinge wie ersetzen

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

mit

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

Wenn am Ende des Arrays ein bekannter Wert steht (z. B.NULL) können Sie den Schleifenzähler eliminieren:

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

Viel Glück, das ist ein tolles Buch!

Answer 5

Um diesen Code zu optimieren, wäre es am besten, die strcmp-Routine neu zu schreiben, da Sie nur auf Gleichheit prüfen und nicht das gesamte Wort auswerten müssen.

Ansonsten kann man nicht viel machen.Sie können nicht sortieren, da es so aussieht, als würden Sie nach Text innerhalb eines größeren Textes suchen.Auch die binäre Suche funktioniert nicht, da der Text wahrscheinlich nicht sortiert wird.

Mein 2p (C-Pseudocode):

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:Ihre for-Schleife wird niemals beendet!(++p ist eingerückt, liegt aber eigentlich nicht im for :-)

Außerdem hat das Umschalten zwischen Zeigern und Indizierung im Allgemeinen keine Auswirkungen auf die Leistung, ebenso wenig wie das Hinzufügen von Registerschlüsselwörtern (wie Mat bereits erwähnt hat) – der Compiler ist intelligent genug, diese Transformationen gegebenenfalls anzuwenden, und wenn Sie ihm genug über Ihren CPU-Arch erzählen , wird es diese besser bewältigen als manuelle Pseudo-Mikrooptimierungen.

Answer 7

Eine schnellere Möglichkeit, Zeichenfolgen abzugleichen, besteht darin, sie im Pascal-Stil zu speichern.Wenn Sie nicht mehr als 255 Zeichen pro Zeichenfolge benötigen, speichern Sie sie ungefähr so, mit der Anzahl im ersten Byte:

char s[] = "\x05Hello";

Dann können Sie Folgendes tun:

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;
    }
}

Und um wirklich schnell zu werden, fügen Sie Speicher-Prefetch-Hinweise für String-Anfang + 64, + 128 und den Anfang des nächsten Strings hinzu.Aber das ist einfach verrückt.:-)

Answer 8

Eine weitere schnelle Möglichkeit besteht darin, Ihren Compiler dazu zu bringen, ein für SSE2 optimiertes Memcmp zu verwenden.Verwenden Sie Char-Arrays mit fester Länge und richten Sie sie so aus, dass die Zeichenfolge mit einer 64-Byte-Ausrichtung beginnt.Dann glaube ich, dass Sie die guten memcmp-Funktionen erhalten können, wenn Sie const char match[64] anstelle von const char *match in die Funktion übergeben oder strncpy match in ein 64.128.256 Byte-Array.

Wenn man etwas genauer darüber nachdenkt, könnten diese SSE2-Match-Funktionen Teil von Paketen wie den Beschleunigerbibliotheken von Intel und AMD sein.Schau sie dir an.

Answer 9

Realistisch gesehen führt die Festlegung von I als Registervariable zu nichts, was der Compiler nicht bereits tun würde.

Wenn Sie bereit sind, im Vorfeld etwas Zeit in die Vorverarbeitung des Referenzarrays zu investieren, sollten Sie „The World's Fastest Scrabble Program“ googeln und das implementieren.Spoiler:Es handelt sich um eine DAG, die für die Charaktersuche optimiert ist.

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;
}