Schneller String Vergleich in C

strcmp wird normalerweise von allen Anbietern optimiert. Wenn Sie jedoch nicht zufrieden sind, können Sie versuchen:

• Nachschlagen Burst Tries
• Verwenden Sie einen Suffixbaum für einen schnellen String-Vergleich - siehe diesen Artikel
• Abhängig von der Größe der Zeichenfolgen in Ihrer Anwendung können Sie einen benutzerdefinierten Zeichenfolgenvergleicher schreiben. ZB: GNU libc hatte diese Optimierung für kleine Strings, wo sie Strings kleiner als fünf Bytes als ganze Zahlen getestet haben. MS cl hat auch einige Optimierungen für kleine Strings (schau es nach).

Stellen Sie aber sicher, dass strcmp Ihr echter Engpass ist.

Ich kann Ihnen versichern, die Funktion strcmp ist ABSOLUT NICHT der Engpass . In der Regel ist strcmp gut optimiert und kann je nach Architektur 32- oder 64-Bit-Vergleiche für Strings mit mehr als 4/8 Byte durchführen. Sowohl newlib als auch GNU libc tun dies. Aber selbst wenn Sie jedes Byte in beiden Strings 20 Mal betrachten würden, ist es nicht so wichtig wie das Algo & amp; Datenstruktur Entscheidungen hier gemacht.

Der wahre Flaschenhals ist der Suchalgorithmus O (N) . Ein einzelner O (N log N) -Pass an der Datei könnte verwendet werden, um eine geeignete Datenstruktur (ob es eine normale BST, ein Trie oder nur ein einfaches sortiertes Array ist) für O (log N) -Lookups durchzuführen.

Bear mit mir hier - viel Mathematik folgt. Aber ich denke, dies ist eine gute Gelegenheit zu veranschaulichen, warum die Wahl des Algorithmus & amp; Datenstruktur ist manchmal FAR wichtiger als Methode des Zeichenfolgenvergleichs. Steve berührt das, aber ich wollte es etwas tiefer erklären.

Mit N = 1e6, log (1e6, 2) = 19.9, so runden Sie bis zu 20 Vergleiche an einer idealen Datenstruktur ab.

Momentan führen Sie eine Worst-Case-Suche nach O (N) oder 1e6-Operationen durch.

Nehmen wir an, Sie bauen einfach einen rot-schwarzen Baum mit der Einfügungszeit O (log N) und fügen N Elemente ein, das ist O (N log N) Zeit, um den Baum zu erstellen. Das sind also 1e6 x 20 oder 20e6 Operationen, die notwendig sind, um deinen Baum zu bauen.

In Ihrem aktuellen Ansatz ist der Aufbau der Datenstruktur O (N) oder 1e6-Operationen, aber Ihre Suchzeit im schlimmsten Fall ist auch O (N). Wenn Sie also die Datei lesen und nur 20 Suchvorgänge ausführen, sind Sie bei einem theoretisch schlimmsten Fall von 21 Millionen Operationen angelangt. Im Vergleich dazu ist Ihr schlimmster Fall mit einem rot-schwarzen Baum und 20 Suchvorgängen 20.000.400 Operationen oder 999.600 Operationen BESSER als die O (N) Suche in einem unsortierten Array. Bei 20 Suchvorgängen sind Sie also an der ersten Stelle, an der sich eine anspruchsvollere Datenstruktur wirklich auszahlt. Aber schau mal, was bei 1000 Suchanfragen passiert:

Unsortiertes Array = Initialisierung + 1000 x Suchzeit = O (N) + 1000 * O (N) = 1.000.000 + 2.000.000.000 = 2.001.000.000 Operationen.

Rot-Schwarz = Initialisierung + 1000 x Suchzeit = O (N log N) + 1000 * O (log N) = 20.000.000 + 20.000 = 20.020.000 Operationen.

2.001.000.000 / 20.020.000 ~ = 100x so viele Operationen für die O (N) Suche.

Bei 1e6 Suchen, das ist (1e6 + 1e6 * 1e6) / (20e6 + 1e6 * 20) = 25.000x so viele Operationen.

Nehmen Sie an, Ihr Computer kann die 40e6-Operationen ausführen, die für die Suche nach Log-N in einer Minute erforderlich sind. Es würde 25.000 Minuten oder 17 Tage dauern, die gleiche Arbeit mit Ihrem aktuellen Algorithmus zu machen. Oder eine andere Betrachtungsweise ist, dass der O (N) -Suchalgorithmus nur 39 Suchvorgänge in der Zeit bewältigen kann, in der der O (log N) -Algorithmus 1.000.000 ausführen kann. Und je mehr Suchen du machst, desto hässlicher wird es.

Siehe Antworten von Steve und schelmisch für mehrere bessere Möglichkeiten der Datenstrukturen & amp; Algorithmen. Meine einzige zusätzliche Warnung wäre, dass qsort() von Steve vorgeschlagen wurde eine Worst-Case-Komplexität von O (N * N) hat, die weit, weit, schlechter ist als die O (N log N) Sie erhalten mit einem Heapsort oder verschiedenen baumartigen Strukturen.

Optimierung von Computerprogrammen in C

  

Sie können etwas Zeit sparen, indem Sie die ersten Zeichen der fraglichen Zeichenfolgen überprüfen, bevor Sie den Anruf tätigen. Wenn sich die ersten Zeichen unterscheiden, gibt es natürlich keinen Grund, strcmp aufzurufen, um den Rest zu überprüfen. Wegen der ungleichmäßigen Verteilung von Buchstaben in natürlichen Sprachen ist die Auszahlung nicht 26: 1, sondern eher 15: 1 für Großbuchstaben.

Wenn das Wörterbuch der Wörter, die Sie verwenden, wohldefiniert sind (dh, Sie haben nichts dagegen, Rückgabe Wert Formular Strcmp aber 0 == gleich), zum Beispiel eine Reihe von Befehlszeilenargumente, die mit dem gleichen Präfix beginnt, ex: tcp-accept, tcp-reject, dann können Sie das Makro neu schreiben und eine Zeigerarithmetik ausführen, um nicht das erste, sondern das N-te Zeichen zu vergleichen, in diesem Fall das 4. Zeichen, zB:

Wenn ich Ihre Frage richtig beantworte, müssen Sie prüfen, ob eine Zeichenkette entlang aller bisher gelesenen Zeilen vorhanden ist. Ich würde vorschlagen, eine TRIE oder noch besser einen Patricia-Baum aus den Dateizeilen zu verwenden. Auf diese Weise können Sie, anstatt alle Zeilen durchzugehen, linear prüfen, ob Ihre Zeichenfolge vorhanden ist (und mit etwas mehr Aufwand - wo).

Sie kompilieren bereits mit der Optimierung, oder?

Wenn Sie eine trie oder hashtable Datenstruktur haben, die um den Ort herumliegt, sofort einsatzbereit, dann sollten Sie.

Wenn dies nicht gelingt, ist es eine ziemlich einfache Änderung, die wahrscheinlich die Dinge beschleunigen wird, das Array line einmal zu sortieren, bevor Sie mit dem Erzeugen von Strings beginnen, nach denen gesucht werden soll. Dann binäre Suche nach buffer im sortierten Array. Es ist einfach, weil die zwei Funktionen, die Sie benötigen, Standard sind - qsort und bsearch .

Eine binäre Suche in einem sortierten Array muss nur über Protokoll ₂ (filelines) Zeichenfolgenvergleiche statt über Dateizeilen erfolgen Also in deinem Fall sind das 20-sachen String-Vergleiche pro Aufruf von generate_string statt ein paar Millionen. Von den Zahlen, die Sie gegeben haben, können Sie vernünftigerweise erwarten, dass es 20-25 Mal schneller geht, obwohl ich nichts verspreche.

Ich weiß nicht, dass es einen schnelleren Weg gibt, als strcmp aufzurufen, um Zeichenkettenvergleiche durchzuführen, aber Sie können vermeiden so oft strcmp aufzurufen. Verwenden Sie eine Hashtabelle, um Ihre Zeichenfolgen zu speichern, und Sie können dann überprüfen, ob die Zeichenfolge in buffer in der Hashtabelle enthalten ist. Wenn der Index eines Treffers wichtig ist, wenn Sie "etwas tun", kann die Tabelle Zeichenfolgen Indizes zuordnen.

Sie können etwas "billiges" versuchen, wie das Screening anhand des ersten Chars. Wenn die ersten Zeichen nicht übereinstimmen, können die Zeichenfolgen nicht identisch sein. Wenn sie übereinstimmen, rufen Sie strcmp auf, um die gesamte Zeichenfolge zu vergleichen. Vielleicht möchten Sie einen besseren Algorithmus in Erwägung ziehen, wenn dies für Ihre Situation angemessen ist; Beispiele wären das Sortieren der Datei / Zeilen und das Durchführen einer binären Suche unter Verwendung einer Hash-Tabelle oder ähnlicher Zeichenketten-Tabellen-Techniken.

Sie können in diesem Fall mit einem binären Vergleich zurechtkommen, weil Ihr Programm nicht sortiert, sondern nach Gleichheit vergleicht.

Sie können hier auch die Vergleichsgeschwindigkeiten verbessern, indem Sie die Längen im Voraus bestimmen (vorausgesetzt, sie variieren natürlich genug). Wenn die Länge hier nicht übereinstimmt, wird do something nicht vorkommen.

natürlich, hashing hier wäre eine andere Überlegung abhängig davon, wie oft Sie den Hash-Wert lesen.