Schnell string Vergleich in C

Momentan habe ich diese Art von Schleife

while(1)
{
    generate_string(&buffer);

    for(int i = 0; i < filelines; i++)
    {
        if(strcmp(buffer,line[i]) == 0)
        {
           /*  do something  */
        }
    }
}

Ich habe eine Datei mit ein paar Millionen Saiten(die hoffentlich sollte um die Hälfte gekürzt werden irgendwann bald) die Anzahl aller dieser Zeichenfolgen gespeichert in filelines

line[i] ist im Grunde, wo die Zeichenkette gespeichert ist.

Derzeit, aufgrund der Vergleich dieser million strings, Funktion generate_string(&buffer); ausgeführt wird, etwa 42 mal pro Sekunde.
Gibt es einen schnelleren Weg, zu tun, string Vergleich in C?

  • Wenn Sie Sortieren können Linien, sicher.
  • Wenn Sie hash, hash.
  • Nein, denn die eigentliche Frage hier ist nicht "wie das vergleichen von zwei strings", es ist "wie testen Sie eine Zeichenfolge für die Einkapselung in eine große Sammlung von strings".
  • Nur, wenn die Saiten Größen gleich sind, das kann man doch if((buffer[0] == line[0]) && (buffer[1] == Zeile[1]) && ...). Das ist schneller als Aufruf strcmp().
  • Ich lief ein Profil auf wakkerbot: es nutzt 200ms zu tun 2M-lookups in einer 500K Wörterbuch der bekannten Wörter. Einschließlich einer abschließenden strcmp() an die passende hashtable-Eintrag.
InformationsquelleAutor farmdve | 2012-05-23
  1. 11

    strcmp ist in der Regel optimiert, die von allen Herstellern. Allerdings, wenn Sie nicht zufrieden mit diesem können Sie versuchen:

    • Lookup Burst Versucht
    • Verwenden Sie einen suffix-Baum für die schnelle string-Vergleich -- siehe diese Artikel
    • Abhängig von der Größe der Zeichenketten in Ihrer Anwendung können Sie schreiben eine benutzerdefinierte string-Vergleicher. E. g: GNU libc verwendet werden, um diese Optimierung für kleine Streicher, wo Sie getestet strings, die kleiner als fünf bytes als Integer. MS cl hat auch einige Optimierungen für klein-strings (sehen Sie oben).

    Aber noch wichtiger ist sicherzustellen, dass strcmp ist Ihre real Engpass.

    • Ja, strcmp ist der Engpass. Entfernen der strcmp-Aufruf die Funktion ist exucted über tausend mal pro Sekunde, auch 1100 in einigen Fällen.
    • Ihre "finden Sie in diesem Artikel" - link nicht mehr links auf die Artikel, aber nur die prof ' s home page.
    InformationsquelleAutor dirkgently
  2. 5

    Ich kann Ihnen versichern, die Funktion strcmp ist ABSOLUT NICHT der Engpass. In der Regel, strcmp ist gut optimiert und kann 32-oder 64-bit-Vergleiche für Zeichenfolgen, die länger als 4/8 bytes abhängig von der Architektur. Beide newlib und die GNU libc, die dies tun. Aber auch wenn Sie einmal jedes byte in beiden Zeichenketten 20 mal, es spielt keine Rolle, so viel wie der algo & Datenstruktur Entscheidungen hier.

    Der wirkliche Flaschenhals ist die O(N) search-Algorithmus. Ein einzelnes O(N log N) pass auf die Datei, die verwendet werden könnte, um an entsprechende Daten-Struktur (ob es eine normale BST, a trie, oder nur ein einfaches sortiertes array) für das tun von O(log N) - lookups.

    Geduld mit mir, hier-eine Menge Mathematik folgt. Aber ich denke, das ist eine gute Gelegenheit, um zu verdeutlichen, warum die Wahl des Algorithmus & Datenstruktur, die sind manchmal viel wichtiger als die Methode der string-Vergleich. Steve berührt, aber ich wollte erklären, es in ein wenig mehr Tiefe.

    Mit N=1e6, log(1e6, 2) = 19.9, also Runden bis zu 20 Vergleiche für eine optimale Daten-Struktur.

    Momentan sind Sie dabei ein worst-case-Suche von O(N), oder 1e6 Operationen.

    So sagen Sie bauen ein rot-schwarz-Baum mit O(log N) einfügen, und einfügen von N Elementen ist O(N log N) Zeit für den Aufbau der Struktur. Das ist also 1e6 x 20 oder 20e6 Operationen, die nötig sind, um bauen Sie Ihren Baum.

    In Ihrem aktuellen Ansatz, der Aufbau der Datenstruktur ist O(N), oder 1e6 Operationen, aber Ihre worst-case Suchzeit O(N) als gut. Also von der Zeit Sie Lesen die Datei und führen Sie nur 20 Suchvorgänge werden, sind Sie bis zu einem theoretischen worst-case von 21,000,000 Operationen. Durch Vergleich, deine schlimmsten Fall mit einer rot-schwarz-Baum und 20 suchen ist 20,000,400 Operationen, oder 999,600 Operationen BESSER als die O(N) Suche in einer unsortierten array. Also bei 20 suchen, sind Sie auf den ersten Punkt, wo eine komplexere Datenstruktur, die sich wirklich lohnt. Aber schauen Sie, was passiert bei 1000 Suchanfragen:

    Unsortierten array = Initialisierung + 1000 x suchaufwand = O(N) + 1000 * O(N) = 1,000,000 + 2,000,000,000 = 2,001,000,000 Operationen.

    Rot-schwarz = Initialisierung + 1000 x suchaufwand = 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 Vorgänge, für die O(N) suchen.

    In 1e6 sucht, das ist (1e6 + 1e6 * 1e6) /(20e6 + 1e6 * 20 ) = 25,000 x so viele Operationen.

    Davon aus, dass Ihr computer verarbeiten kann, die 40e6 'Operationen', die es braucht, um die log-N-Recherchen in 1 minute. Es würde 25,000 Minuten, oder 17 TAGE, um die gleiche Arbeit mit Ihrem aktuellen Algorithmus. Oder ein anderer Weg es zu sehen ist, dass die O(N) search-Algorithmus kann nur behandeln, 39 sucht in der Zeit O(log N) - Algorithmus machen kann 1,000,000. Und je mehr Suchanfragen, die Sie tun, desto hässlicher wird es.

    Siehe Antworten von Steve und dirkgently für einige bessere alternativen von Datenstrukturen & algorithmen. Meine einzige zusätzliche Vorsicht wäre, dass qsort() vorgeschlagen von Steve könnte haben ein worst-case-Komplexität von O(N*N), das ist weit, weit schlimmer als die O(N log N) erhalten Sie mit heapsort oder verschiedene Baum-ähnlichen Strukturen.

    InformationsquelleAutor Brian McFarland
  3. 4

    Optimierung von EDV-Programmen in C

    Können Sie etwas Zeit sparen, wenn die Prüfung das erste Zeichen des strings in Frage, bevor Sie den Anruf. Offensichtlich, wenn Sie die ersten Zeichen unterscheiden, es gibt keinen Grund zu nennen strcmp zu überprüfen, den rest. Wegen der ungleichmässigen Verteilung der Buchstaben in natürlichen Sprachen, die Auszahlung ist nicht, 26:1, aber mehr wie 15:1 für groß-Daten.

    #define QUICKIE_STRCMP(a, b)  (*(a) != *(b) ? \  
  (int) ((unsigned char) *(a) - \
         (unsigned char) *(b)) : \
  strcmp((a), (b)))

    Wenn das Wörterbuch Der Wörter, die Sie verwenden sind gut definiert (Bedeutung Sie nicht Verstand Rückgabewert form strcmp aber 0==gleich), zum Beispiel, eine Reihe von Kommandozeilen-Argumente, die beginnt mit dem gleichen Präfix, Beispiel: tcp-akzeptieren, tcp-abzulehnen, als schreiben Sie das makro, und führen Sie einige Zeiger-Arithmetik zu vergleichen, nicht der 1. sondern derjenige, der N-TEN char, in diesem Fall, den 4. char, ex:

       #define QUICKIE_STRCMP(a, b, offset) \
            (*(a+offset) != *(b+offset))\ ? -1 : strcmp((a), (b)))
    • Ich bezweifle wirklich, dass das makro beim Vergleich der ersten Zeichen, die bessere Ergebnisse für moderne Compiler und Bibliotheken.
    InformationsquelleAutor user2402133
  4. 2

    Wenn ich Ihre Frage richtig, Sie brauchen, um zu überprüfen, ob ein string ist entlang alle Zeilen Lesen so weit. Ich würde vorschlagen mit einer MARINA oder noch besser eine Patricia Baum aus der Datei Linien. Diesen Weg zu gehen, anstatt den ganzen alle Zeilen, die Sie prüfen können Linear, wenn Ihre Zeichenfolge vorhanden ist(und mit ein wenig mehr Aufwand - wo).

    InformationsquelleAutor Ivaylo Strandjev
  5. 1

    Sind Sie bereits kompilieren mit Optimierung, richtig?

    Wenn Sie eine Trie-oder hashtable-Datenstruktur liegen rund um den Platz, bereit zu verwenden, dann sollten Sie.

    Andernfalls eine ziemlich einfache änderung, die wahrscheinlich die Dinge beschleunigen zu Sortieren, array line einmal, bevor Sie beginnen, generieren von Zeichenfolgen zu suchen. Dann binäre Suche für buffer im sortierten array. Es ist einfach, weil die beiden Funktionen, die Sie brauchen, sind standard - qsort und bsearch.

    Eine binäre Suche in einem sortierten array braucht nur zu tun, über log2(filelines) string-Vergleiche, anstatt über filelines. Also in deinem Fall 20-etwas string-Vergleiche pro Aufruf generate_string statt ein paar Millionen. Aus den zahlen, die Sie gegeben haben, denke ich, kann man vernünftigerweise erwarten, dass es gehen 20 bis 25 mal schneller, obwohl ich nichts Versprechen.

    • Die Funktion qsort() könnte eine quicksort-wie der name schon sagt, die hat O(N*N) worst-case-performance. Es sei denn ich war sicher, wie qsort() verhält sich auf der Ziel-Plattform, würde ich mit dem langsamer im Durchschnitt, aber sehr viel schneller auf worst-case-hepasort oder smoothsort.
    • Wenn Sie es vorziehen. Wie gesagt, der Vorteil von qsort ist, dass es standard. Wenn ich arbeiten zu erledigen habe, dann würde ich wahrscheinlich eher schreiben Sie eine Hashtabelle als ein heapsort, um ehrlich zu sein 🙂 Trotzdem, es ist nicht ganz klar, ob die start-up-Zeit überhaupt eine Rolle spielt, verglichen mit der Anzahl der strings pro Sekunde generiert, sobald wir loslegen. Wenn start-up-Zeit nicht wirklich wichtig ist, dann qsort umgesetzt als bubble-sort wäre absolut in Ordnung!
    • Eine bewährte sort-Algorithmus ist wahrscheinlich schwerer zu Schrauben, als eine Hash-Funktion, und eine schlechte Hash-Funktion bringt Sie wieder auf ein worst-case von O(N) Zeit bei der Suche.
    • djbhash ist gut genug für mich, aber es ist wahr, dass hashtables auch katastrophale worst-case-performance. Eine Analyse ist in Ordnung, ob die Liste der Zeichenfolgen in lines möglicherweise in böser Absicht konstruiert, als ein quicksort - und/oder hash-killer. Wenn Sie sind besorgt über diese Art der Sache, dann müssen Sie entscheiden, ob Sie schreiben Ihre eigenen algorithmen, oder einfach nur, um eine standard-Bibliothek, deren qsort resistent ist.
    InformationsquelleAutor Steve Jessop
  6. 0

    Ich weiß nicht, dass es einen schnelleren Weg als der Aufruf strcmp zu tun, der Vergleich von Strings, aber Sie können vielleicht vermeiden aufrufen strcmp so viel. Verwenden Sie eine hash-Tabelle zum speichern von strings und dann können Sie überprüfen, ob der string in buffer ist in der hash-Tabelle. Wenn der index ein Treffer ist wichtig, wenn Sie "etwas tun", die Tabelle kann die Zuordnung von strings zu Indizes.

    InformationsquelleAutor Ted Hopp
  7. 0

    Können Sie versuchen, etwas 'Billig', wie das screening basiert auf dem ersten char. Wenn die ersten chars nicht übereinstimmen, werden die Zeichenfolgen nicht gleich sein können. Wenn Sie übereinstimmen, dann rufen strcmp vergleichen, um den gesamten string. Sie möchten vielleicht überlegen, einen besseren Algorithmus, wenn für Ihre situation geeignet ist; ein Beispiel wäre die Sortierung der Datei/Zeilen und dabei eine binäre Suche, unter Verwendung einer hash-Tabelle oder ähnliche string-Tabelle-Techniken.

    InformationsquelleAutor Art Swri
  8. 0

    können Sie erhalten, indem Sie einen binären Vergleich in diesem Fall, da das Programm eigentlich nicht Art, aber vergleicht auf Gleichheit.

    können Sie auch verbessern Vergleich Geschwindigkeiten hier durch die Bestimmung der Längen im Voraus (vorausgesetzt natürlich Sie variieren genug). wenn die Länge nicht passt hier do something wird nicht passieren.

    natürlich, hashing, hier wäre noch eine überlegung, je nachdem, wie viele Male Sie Lesen den Hash-Wert.

    InformationsquelleAutor justin
Schreibe einen Kommentar