Wie kann ich die Leistung in einer Map-Suche mit dem Schlüsseltyp std :: string erhöhen?

Schalten Sie zuerst alle Profiling- und DEBUG-Schalter aus. Diese können STL immens verlangsamen.

Wenn das nicht der Fall ist, könnte ein Teil des Problems sein, dass Ihre Strings für die ersten 80-90% der Strings identisch sind. Das ist nicht unbedingt schlecht für map, aber für String-Vergleiche. Wenn dies der Fall ist, kann Ihre Suche viel länger dauern.

In diesem Code wird find () zum Beispiel wahrscheinlich zu einer Reihe von String-Vergleichen führen, aber jeder wird nach dem Vergleich des ersten Zeichens bis zu "david" zurückkehren, und dann werden die ersten drei Zeichen überprüft. Also höchstens 5 Zeichen pro Anruf überprüft werden.

Auf der anderen Seite wird find () im folgenden Code wahrscheinlich 135 Zeichen überprüfen:

Das liegt daran, dass die Zeichenfolgenvergleiche tiefer suchen müssen, um eine Übereinstimmung zu finden, da der Anfang jeder Zeichenfolge gleich ist.

Die Verwendung von size () in Ihrem Vergleich für Gleichheit hilft Ihnen hier nicht sehr, da Ihr Datensatz so klein ist. Eine std :: map wird so sortiert, dass ihre Elemente mit einer binären Suche durchsucht werden können. Jeder zu findende Aufruf sollte weniger als 5 Zeichenfolgenvergleiche für einen Fehltreffer und durchschnittlich 2 Vergleiche für einen Treffer ergeben. Aber es hängt von Ihren Daten ab. Wenn die meisten Pfadangaben unterschiedlich lang sind, kann eine Größenprüfung, wie sie Motti beschreibt, sehr hilfreich sein.

Wenn Sie über alternative Algorithmen nachdenken, sollten Sie berücksichtigen, wie viele "Treffer" Sie erhalten. Sind die meisten Ihrer find () -Aufrufe end () oder ein Treffer? Wenn die meisten Ihrer find () s return end () (misses) sind, dann suchen Sie jedes Mal die gesamte Map (2loggn string vergleicht).

Hash_map ist eine gute Idee; Es sollte Ihre Suchzeit in etwa die Hälfte für Treffer schneiden; mehr für Misses.

Ein benutzerdefinierter Algorithmus kann aufgrund der Art von Pfadzeichenfolgen aufgerufen werden, insbesondere wenn Ihr Datensatz eine gemeinsame Abstammung wie im obigen Code hat.

Eine andere Sache, die Sie beachten sollten, ist, wie Sie Ihre Suchbegriffe erhalten. Wenn Sie sie wiederverwenden, kann es hilfreich sein, sie in etwas zu kodieren, das einfacher zu vergleichen ist. Wenn Sie sie einmal verwenden und verwerfen, ist dieser Kodierungsschritt wahrscheinlich zu teuer.

Ich habe vor langer Zeit so etwas wie einen Huffman-Codebaum verwendet, um die Suche nach Zeichenketten zu optimieren. Ein solcher binärer Suchbaum könnte in manchen Fällen effizienter sein, ist aber für kleine Sets wie Ihres ziemlich teuer.

Sehen Sie sich schließlich alternative std :: map-Implementierungen an. Ich habe schlechte Dinge über einige der stl-Code-Leistung von VC gehört. Insbesondere die DEBUG-Bibliothek ist schlecht darin, Sie bei jedem Anruf zu überprüfen. StlPort war früher eine gute Alternative, aber ich habe es in ein paar Jahren noch nicht ausprobiert. Ich habe Boost auch immer geliebt.

Als Even sagte, der Operator, der in set verwendet wird, ist < nicht == .

Wenn Ihnen die Reihenfolge der Zeichenfolgen in Ihrem set egal ist, können Sie dem set einen benutzerdefinierten Vergleich übergeben, der besser funktioniert als der normale less-than .

Wenn zum Beispiel viele Ihrer Strings ähnliche Präfixe haben (aber in der Länge variieren), können Sie nach String-Länge sortieren (da string.length konstante Geschwindigkeit ist).

Wenn Sie dies tun, achten Sie auf einen häufigen Fehler:

Dieser Operator verwaltet keine strenge schwache Reihenfolge , Sie können zwei Strings haben, die jeweils kleiner sind als die anderen.

Folge der Logik und du wirst comp(a, b) == true und comp(b, a) == true sehen.

Die korrekte Implementierung ist:

Als Erstes versuchen Sie, eine hash_map zu verwenden, wenn das möglich ist - Sie haben recht, dass der Standard-String-Vergleich nicht erst nach Größe sucht (da er lexikographisch vergleicht), aber Ihren eigenen Map-Code zu schreiben ist etwas, was Sie wären besser ausweichend. Aus Ihrer Frage klingt es so, als müssten Sie nicht über Bereiche hinweg iterieren; In diesem Fall hat map nichts, was hash_map nicht hat.

Es hängt auch davon ab, welche Art von Schlüsseln Sie in Ihrer Karte haben. Sind sie typischerweise sehr lang? Auch was bedeutet "etwas langsam"? Wenn Sie den Code nicht profiliert haben, ist es durchaus möglich, dass es ein anderer Teil ist, der Zeit braucht.

Update: Hmm, der Flaschenhals in Ihrem Programm ist ein map :: find, aber die Map hat immer weniger als 15 Elemente. Das lässt mich vermuten, dass das Profil irgendwie irreführend war, denn ein Fund auf einer solchen Karte sollte überhaupt nicht langsam sein. In der Tat sollte ein map :: find so schnell sein, nur der Overhead der Profilerstellung könnte mehr sein als der Suchanruf selbst. Ich muss noch einmal fragen, bist du sicher, dass das wirklich der Flaschenhals in deinem Programm ist? Sie sagen, dass die Zeichenfolgen Pfade sind, aber Sie führen keine Betriebssystemaufrufe, Dateisystemzugriff und Festplattenzugriff in dieser Schleife durch? Irgendwelche von diesen sollten Größenordnungen langsamer als eine Karte sein :: finden Sie auf einer kleinen Karte. Wirklich jede Art, eine Zeichenfolge zu erhalten, sollte langsamer sein als die map :: find.

Sie können versuchen, einen sortierten Vektor zu verwenden ( hier ist ein Beispiel ), dies könnte sich herausstellen sei schneller (du musst es profilieren, um sicherzugehen < Natürlich.

Gründe zu glauben, dass es schneller geht:

1. Weniger Speicherzuweisungen und Deallocations (der Vektor wird auf die maximal verwendete Größe erweitert und dann den freigegebenen Speicher wiederverwenden).
2. Binäre Suche mit wahlfreiem Zugriff sollte schneller als die Baumdurchquerung sein (besonders wegen der Datenlokalität).

Gründe zu denken, dass es langsamer sein wird:

1. Bei Deletionen und Hinzufügungen werden Strings im Speicher verschoben, da string s swap effizient ist und die Größe des Datensatzes klein ist, ist dies möglicherweise kein Problem.

Der Komparator von std :: map ist nicht std :: equal_to ist std :: less, ich bin mir nicht sicher, was der beste Weg ist, um einen & lt; vergleiche so, dass es schneller wäre als der eingebaute.

Wenn es immer & lt; 15 elems, vielleicht könntest du neben std :: string auch einen key verwenden?

Motti hat eine gute Lösung. Allerdings bin ich mir ziemlich sicher, dass für Ihre & lt; 15 Elemente Eine Map ist nicht der richtige Weg, da ihr Overhead immer größer ist als der einer einfachen Lookup-Tabelle mit einem geeigneten Hash-Schema. In Ihrem Fall könnte es sogar ausreichen, nach Länge zu haseln, und wenn das immer noch Kollisionen verursacht, verwenden Sie eine lineare Suche durch alle Einträge der gleichen Länge.

Um festzustellen, ob ich Recht habe, ist natürlich eine Benchmark erforderlich, aber ich bin mir dessen Ergebnis sicher.

Sie könnten überlegen, einen Hash für eine Zeichenfolge vorzurechnen und diesen in Ihrer Map zu speichern. Dies bietet den Vorteil von Hash-Vergleichen anstelle von String-Vergleichen während der Suche in der std :: map-Struktur.

Dies hat den Vorteil, dass beim Konstruieren einmal ein Hash der Zeichenkette berechnet wird. Danach können Sie eine Vergleichsfunktion implementieren:

Da die Hashes jetzt auf HashedString construction berechnet werden, werden sie auf diese Weise in der std :: map gespeichert, und so kann der Vergleich sehr schnell (ein ganzzahliger Vergleich) in einem astronomisch hohen Prozentsatz der Zeit erfolgen und fällt zurück auf Standardzeichenfolge vergleicht, wenn die Hashwerte gleich sind.

Hier sind einige Dinge, die Sie beachten können:

0) Sind Sie sicher, dass hier der Performance-Engpass liegt? Wie die Ergebnisse von Quantify, Cachegrind, Gprof oder so ähnlich? Weil Suchvorgänge auf solch einer Smap-Map ziemlich schnell sein sollten ...

1) Sie können den Funktor überschreiben, mit dem die Schlüssel in std :: map & lt; & gt; verglichen werden. Dafür gibt es einen zweiten Template-Parameter. Ich bezweifle jedoch, dass Sie viel besser als Operator & lt; jedoch tun können.

2) Ändern sich die Inhalte der Karte stark? Wenn nicht, und angesichts der sehr kleinen Größe Ihrer Karte, könnte die Verwendung einer sortierten Vektor- und Binärsuche bessere Ergebnisse liefern (zum Beispiel, weil Sie den Speicherort besser ausnutzen können.

3) Sind die Elemente zur Kompilierzeit bekannt? Sie können eine perfekte Hash-Funktion verwenden, um die Suchzeiten zu verbessern, wenn dies der Fall ist. Suche nach gperf im Web.

4) Haben Sie viele Nachschlagewerke, die nichts finden? Wenn dies der Fall ist, kann ein Vergleich mit dem ersten und letzten Element in der Sammlung viele Ungereimtheiten schneller beseitigen als eine vollständige Suche jedes Mal.

Diese wurden bereits vorgeschlagen, aber genauer:

5) Da Sie so wenige Zeichenfolgen haben, könnten Sie vielleicht einen anderen Schlüssel verwenden. Zum Beispiel, sind Ihre Schlüssel alle gleich groß? Können Sie eine Klasse verwenden, die ein Zeichenfeld fester Länge enthält? Können Sie Ihre Strings in Zahlen oder in eine Datenstruktur mit nur Zahlen umwandeln?

Abhängig von den Anwendungsfällen gibt es einige andere Techniken, die Sie verwenden können. Zum Beispiel hatten wir eine Anwendung, die mit über einer Million verschiedener Dateipfade Schritt halten musste. Das Problem mit dem gab es Tausende von Objekten, die kleine Karten dieser Dateipfade behalten mussten.

Da das Hinzufügen neuer Dateipfade zum Datensatz eine seltene Operation war, wurde nach dem Hinzufügen eines Pfades zum System eine Master-Map gesucht. Wenn der Pfad nicht gefunden wurde, wurde er hinzugefügt und eine neue sequenzierte Ganzzahl (beginnend mit 1) zurückgegeben. Wenn der Pfad bereits vorhanden war, wurde die zuvor zugewiesene Ganzzahl zurückgegeben. Dann wurde jede von jedem Objekt gepflegte Karte von einer stringbasierten Karte in eine ganzzahlige Karte umgewandelt. Dies hat nicht nur die Leistung erheblich verbessert, sondern auch die Speicherauslastung verringert, da nicht so viele doppelte Kopien der Zeichenfolgen vorhanden waren.

Sicher, das ist eine sehr spezifische Optimierung. Wenn es jedoch um Leistungsverbesserungen geht, müssen Sie oft maßgeschneiderte Lösungen für spezifische Probleme finden.

Und ich hasse Zeichenfolgen :) Nicht sind sie langsam zu vergleichen, aber sie können wirklich Ihre CPU-Caches auf Hochleistungs-Software trash.

Versuchen Sie std :: tr1 :: unordered_map (in der Kopfzeile gefunden & lt; tr1 / unordered_map & gt;). Dies ist eine Hash-Map, und obwohl sie keine sortierte Reihenfolge von Elementen verwaltet, ist sie wahrscheinlich viel schneller als eine reguläre Map.

Wenn Ihr Compiler TR1 nicht unterstützt, erhalten Sie eine neuere Version. MSVC und gcc unterstützen TR1, und ich glaube, dass auch die neuesten Versionen der meisten anderen Compiler unterstützt werden. Leider wurden viele der Referenzseiten der Bibliothek nicht aktualisiert, so dass TR1 eine weitgehend unbekannte Technologie bleibt.

Ich hoffe, C ++ 0x ist nicht der gleiche Weg.

BEARBEITEN: Beachten Sie, dass die Standard-Hashing-Methode für tr1 :: unordered_map tr1 :: hash ist, was wahrscheinlich auf die Arbeit an einem UDT spezialisiert sein muss.

Wo lange gemeinsame Teilzeichenfolgen vorhanden sind, könnte ein Trie eine bessere Datenstruktur als eine Map oder eine Hash-Map sein. Ich sagte "könnte", obwohl - eine hash_map den Schlüssel nur einmal pro Suche durchläuft, sollte also ziemlich schnell sein. Ich werde es nicht weiter diskutieren, da andere es bereits haben.

Sie könnten auch einen Splay-Tree in Erwägung ziehen, wenn einige Schlüssel häufiger nachgeschlagen werden als andere, aber dies macht natürlich die Worst-Case-Suche schlimmer als eine ausgeglichene Struktur, und Lookups sind mutierende Operationen, die für Sie von Bedeutung sein können verwende z eine Leser-Schreiber-Sperre.

Wenn Sie mehr über die Leistung von Nachschlagevorgängen als über Änderungen nachdenken, können Sie besser mit einem AVL-Baum arbeiten als mit Rot-Schwarz, was nach Ansicht von STL-Implementierungen für Map allgemein gilt. Ein AVL-Baum ist in der Regel besser ausbalanciert und erfordert im Durchschnitt weniger Vergleiche pro Suche, aber der Unterschied ist gering.

Das Finden einer Implementierung von diesen, mit denen Sie zufrieden sind, könnte ein Problem sein. Eine Suche auf der Boost-Hauptseite legt nahe, dass sie eine Splay- und AVL-Struktur haben, aber keinen Trie.

Sie haben in einem Kommentar erwähnt, dass Sie nie eine Suche haben, die nichts findet. Sie könnten also theoretisch den letzten Vergleich überspringen, der in einem Baum von 15 & lt; 2 ^ 4 Elemente könnten Ihnen eine Beschleunigung von 20-25% geben, ohne etwas anderes zu tun. In der Tat, vielleicht mehr als das, da gleiche Saiten am langsamsten zu vergleichen sind. Ob es sich lohnt, einen eigenen Container nur für diese Optimierung zu schreiben, ist eine andere Frage.

Sie können auch Referenzorte in Betracht ziehen - ich weiß nicht, ob Sie die gelegentlichen Seitenfehler vermeiden könnten, indem Sie die Schlüssel und die Knoten aus einem kleinen Haufen heraus zuweisen. Wenn Sie nur etwa 15 Einträge gleichzeitig benötigen, können Sie bei einem Dateinamen-Limit von unter 256 Bytes sicherstellen, dass alles, was während einer Suche aufgerufen wird, in eine einzige 4-KB-Seite passt (abgesehen von dem Schlüssel, der natürlich gesucht wird). Es kann sein, dass der Vergleich der Strings im Vergleich zu ein paar Seitenladungen unbedeutend ist. Wenn dies jedoch Ihr Engpass ist, müssen eine enorme Anzahl von Nachschlagevorgängen durchgeführt werden, also würde ich annehmen, dass alles in der Nähe der CPU liegt. Überprüft vielleicht, vielleicht.

Noch ein Gedanke: Wenn Sie pessimistisches Locking für eine Struktur verwenden, bei der es viele Konflikte gibt (Sie haben in einem Kommentar gesagt, dass das Programm massiv multi-threaded ist), unabhängig davon, was der Profiler Ihnen sagt (welchen Code die CPU-Zyklen haben) Sie könnten mehr kosten, als Sie denken, indem Sie effektiv auf 1 Kern beschränkt werden. Versuchen Sie eine Leser-Schreiber-Sperre?

hash_map ist kein Standard, versuchen Sie es mit unordered_map in tr1 (das in Boost verfügbar ist, wenn es in Ihrer Werkzeugkette nicht bereits vorhanden ist).

Bei kleinen Stringzahlen ist es besser, vector zu verwenden, da map normalerweise als Baum implementiert ist.

Warum verwenden Sie nicht stattdessen eine Hashtabelle? boost :: unordered_map könnte tun. Oder Sie können Ihre eigene Lösung ausrollen und den crc einer Zeichenfolge statt der Zeichenfolge selbst speichern. Oder noch besser, setzen Sie #defines für die Strings und verwenden Sie diese für die Suche, z. B.