Optimieren eines Suchalgorithmus in C

Ja, aber nur sehr geringfügig. Eine viel größere Leistungsverbesserung kann durch die Verwendung besserer Algorithmen erreicht werden (zum Beispiel die Sortierung der Liste und eine binäre Suche).

Die Optimierung eines bestimmten Algorithmus bringt Sie im Allgemeinen nur soweit. Die Wahl eines besseren Algorithmus (auch wenn dieser nicht vollständig optimiert ist) kann zu einer erheblichen Leistungssteigerung führen.

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

Außerdem hat die Variable i keinen großen Einfluss, das Wort bleibt während der gesamten Funktion konstant und der Rest ist zu groß, um in ein beliebiges Register zu passen. Es ist nur eine Frage, wie groß der Cache ist und ob das ganze Array dort hineinpassen könnte.

String-Vergleiche sind ziemlich rechenintensiv.

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

Es gibt eine bekannte Technik als Sentinal-Methode. Um die Sentinal-Methode zu verwenden, müssen Sie die Länge von "array []" kennen. Sie können "array [i]! = NULL" entfernen, indem Sie sentinal vergleichen.

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

Aber Sie können Dinge ein wenig schneller machen, indem Sie Dinge wie

mit

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

Viel Glück, das ist ein großartiges Buch!

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 anderes machen. Sie können nicht so sortieren, wie es aussieht, wenn Sie nach Text in einem größeren Text suchen. Die binäre Suche funktioniert auch nicht, da der Text wahrscheinlich nicht sortiert wird.

Mein 2p (C-psuedocode):

Mark Harrison: Deine for-Schleife wird niemals enden! (++ p ist eingerückt, ist aber nicht wirklich innerhalb der for: -)

Auch der Wechsel zwischen Zeigern und der Indexierung hat im Allgemeinen keinen Einfluss auf die Performance und das Hinzufügen von Register-Schlüsselwörtern (wie bereits erwähnt) - der Compiler ist schlau genug, um diese Transformationen gegebenenfalls anzuwenden, und wenn Sie genug darüber erzählen Ihr CPU-Bogen, wird es eine bessere Arbeit von diesen als manuelle puedo-micro-Optimierungen tun.

Ein schnellerer Weg, Strings zu finden, wäre, sie im Pascal-Stil zu speichern. Wenn Sie nicht mehr als 255 Zeichen pro String benötigen, speichern Sie sie ungefähr so, wobei der Zähler im ersten Byte steht:

Dann können Sie tun:

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

Ein anderer schneller Weg ist es, Ihren Compiler dazu zu bringen, ein SSE2-optimiertes memcmp zu verwenden. Verwenden Sie Char-Arrays mit fester Länge und richten Sie sie so aus, dass der String bei 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 * in die Funktion übergeben oder strncpy in ein 64,128,256 Byte-Array einordnen.

Wenn Sie darüber nachdenken, könnten diese SSE2-Matchfunktionen Teil von Paketen wie den Accelerator-Bibliotheken von Intel und AMD sein. Schau sie dir an.

Realistisch gesehen wird die Einstellung von I als Registervariable nichts tun, was der Compiler nicht schon tun würde.

Wenn Sie bereit sind, eine gewisse Zeit damit zu verbringen, das Referenz-Array vorab zu bearbeiten, sollten Sie "Das schnellste Scrabble-Programm der Welt" googlen und das implementieren. Spoiler: Es ist eine DAG, die für Charakter-Lookups optimiert ist.