Wie steigere ich die Leistung in einer Karte-lookup-Schlüssel Typ std::string?

Erste, schalten Sie alle profiling-und DEBUG-Schalter. Diese verlangsamen kann, STL immens.

Wenn, dass ist es nicht, ein Teil des Problems kann sein, dass deine Saiten sind identisch mit denen für die ersten 80-90% des Strings. Das ist nicht schlecht für die Karte, unbedingt, aber es ist für string-Vergleiche. Wenn dies der Fall ist, ist Ihre Suche viel länger dauern kann.

Zum Beispiel in diesem code finden() wird wahrscheinlich Ergebnis in einem paar von Strings vergleicht, aber jede Rückkehr nach vergleichen der ersten Zeichen, bis "david", und dann die ersten drei Zeichen geprüft werden. Also höchstens 5 Zeichen geprüft werden, die pro Anruf.

map<string,int> names;
names["larry"] = 1;
names["david"] = 2;
names["juanita"] = 3;

map<string,int>::iterator iter = names.find("daniel");

Auf der anderen Seite, im folgenden code finden() wird wahrscheinlich prüfen Sie 135+ Zeichen:

map<string,int> names;
names["/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/wilma"] = 1;
names["/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/fred"] = 2;
names["/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/barney"] = 3;

map<string,int>::iterator iter = names.find("/usr/local/lib/fancy-pants/share/etc/doc/foobar/longpath/yadda/yadda/betty");

Das ist, weil die string-Vergleiche, suchen tiefer, um eine übereinstimmung zu finden, da der Anfang jeder string ist das gleiche.

Mit size() in Ihrem Vergleich auf Gleichheit wird nicht viel helfen hier, da Sie Ihre Daten-set ist so klein. Eine std::map ist gehalten sortiert, so können seine Elemente gesucht werden, die mit einer binären Suche. Jeder Aufruf zu finden, sollte weniger als 5 string-Vergleiche für eine miss und einen Durchschnitt von 2 Vergleiche für einen Treffer. Aber es hängt nicht von Ihren Daten. Wenn die meisten Ihrer Pfad-strings unterschiedliche Längen, dann eine Größe überprüfen, wie Motti beschreibt, könnte helfen, eine Menge.

Etwas zu berücksichtigen, wenn das denken von alternativen algorithmen ist, wie viele "hits", die Sie erhalten. Sind die meisten deiner find () - Aufrufe Rückkehr Ende() oder ein Treffer? Wenn die meisten Ihrer finden()s return end() (findet) dann suchst du die gesamte Karte jeder Zeit (2logn string vergleicht).

Hash_map ist eine gute Idee; Sie sollte schneiden Sie Ihre Zeit der Suche in etwa die Hälfte trifft, mehr für findet.

Einen benutzerdefinierten Algorithmus bezeichnet werden kann, weil die Natur des Pfad-strings, vor allem, wenn Sie Ihre Daten-set hat eine gemeinsame Abstammung, wie im obigen code.

Andere Sache zu prüfen ist, wie bekommen Sie Ihre Suchbegriffe. Wenn Sie wiederzuverwenden, kann es helfen, das zu codieren, Sie in etwas, das leichter zu vergleichen. Wenn Sie Sie einmal und werfen Sie Sie Weg, dann diese Codierung Schritt ist wahrscheinlich zu teuer.

Benutzte ich so etwas wie eine Huffman-Codierung Baum einmal (vor langer Zeit) zu optimieren Zeichenfolge sucht. Ein Binär-string-Suche-Baum kann effizienter sein, in einigen Fällen, aber es ist ziemlich teuer für die kleinen Mengen, so wie Euch.

Schließlich, sehen Sie in alternative zu std::map-Implementierungen. Ich habe gehört, schlechte Dinge über einige der VC-stl-code Leistung. Die DEBUG-Bibliothek in allem ist schlimm daran, überprüfen Sie bei jedem Anruf. StlPort verwendet werden, um eine gute alternative, aber ich habe nicht versucht es in ein paar Jahren. Ich habe es immer geliebt Boost zu.

Die erste Sache ist, zu versuchen, mit einer hash_map, wenn das möglich ist - Sie haben Recht, dass die standard-string-vergleichen nicht die erste Prüfung für die Größe (da es vergleicht lexikographisch), aber schreiben Sie Ihre eigenen anzeigen-code ist etwas, das Sie besser aufgehoben wären, zu vermeiden. Aus Ihrer Frage, es klingt wie Sie müssen nicht zu Durchlaufen reicht; in diesem Fall anzeigen, jedoch nichts hash_map nicht.

Es hängt auch davon ab, welche Art von Schlüssel Sie in Ihrer map. Sind Sie in der Regel sehr lange? Auch was bedeutet "ein wenig langsam" bedeuten? Wenn Sie nicht profiliert, der code, es ist durchaus möglich, dass es ein anderer Teil nimmt sich Zeit.

Update: Hmm, den Engpass in Ihrem Programm ist eine map::find, aber die Karte hat immer weniger als 15 Elementen. Dies lässt mich vermuten, dass das Profil war irgendwie irreführend, da eine finden auf einer Karte das kleine sollte nicht langsam sein, überhaupt. In der Tat, eine map::find sollte so schnell, nur der Aufwand zu Profilieren, könnte mehr als die finden sich selbst aufrufen. Ich muss wieder Fragen, sind Sie sicher, dass dies wirklich der Engpass in Ihrem Programm? Sie sagen, die Saiten sind Pfade, aber Sie nicht tun, jede Art von Betriebssystem-Aufrufe, Datei-system-Zugang, Zugriff auf die Festplatte in dieser Schleife? Jeder von denen sollte Größenordnungen langsamer als eine map::find auf eine kleine Karte. Wirklich jeder Weg, um eine Zeichenfolge sollte langsamer als die map::find.

std::map Komparator ist nicht std::equal_to, es ist std::less, ich bin mir nicht sicher, was der beste Weg, um Kurzschluss eine < vergleichen, so dass es schneller als die eingebauten in einem.

Wenn es immer < 15 elems, vielleicht könnten Sie ein-Taste neben std::string?

Könnten Sie die pre-computing ein hash für den string und speichern das in Ihren anzeigen. Dabei ergibt sich der Vorteil der hash vergleicht statt der Zeichenfolge vergleicht, die während der Suche durch das std::map Baum.

class HashedString
{
  unsigned m_hash;
  std::string m_string;

public:
  HashedString(const std::string& str)
    : m_hash(HashString(str))
    , m_string(str)
  {};
  //... copy constructor and etc...

  unsigned GetHash() const {return m_hash;}
  const std::string& GetString() const {return m_string;}
};

Dies hat die Vorteile von computing-ein hash-Wert der Zeichenfolge einmal auf dem Bau. Nach dieser, könnten Sie implementieren eine Vergleich-Funktion:

struct comp
{
  bool operator()(const HashedString& lhs, const HashedString& rhs)
  {
    if(lhs.GetHash() < rhs.GetHash()) return true;
    if(lhs.GetHash() > rhs.GetHash()) return false;
    return lhs.GetString() < rhs.GetString();
  }
};

Seit hashes sind nun berechnet HashedString Bau, in dem Sie gespeichert sind, die Art und Weise, in der std::map, und so das vergleichen kann sehr schnell passieren (eine Ganzzahl vergleichen) in einen astronomisch hohen Prozentsatz der Zeit, fallen zurück auf standard-string vergleicht, wenn die hashes gleich sind.

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

0) Bist du sicher, dass dies ist, wo der performance-Flaschenhals ist? Wie die Ergebnisse zu Quantifizieren, Cachegrind, gprof oder sowas? Da Suchvorgänge auf solche smap Karte sollte ziemlich schnell...

1) Sie können das überschreiben der Funktor vergleichen Sie die Schlüssel in std::map<> gibt es einen zweiten template-parameter, das zu tun. Ich bezweifle, dass Sie tun können, viel besser als operator<, aber.

2) Werden die Inhalte der Karte viel verändern? Wenn nicht, und angesichts der sehr kleinen Größe der Karte, die vielleicht ein sortiert vector und binärer Suche, könnte zu besseren Resultaten führen (zum Beispiel, weil Sie nutzen können Speicher Ort besser.

3) Sind die Elemente, die zur Kompilierzeit bekannt? Sie kann eine perfekte hash-Funktion zu verbessern lookup-Zeiten, wenn das der Fall ist. Suche für gperf auf das web.

4) haben Sie eine Menge von lookups, dass scheitern nichts zu finden? Wenn ja, vielleicht zu vergleichen mit der ersten und letzten Elemente in der Sammlung zu beseitigen viele Abweichungen schneller als eine vollständige Suche jedes mal.

Diese wurden schon vorgeschlagen, aber in mehr detail:

5) Da Sie so wenige Saiten, vielleicht könnten Sie einen anderen Schlüssel verwenden. Zum Beispiel, deine keys alle die gleiche Größe? Sie können verwenden Sie eine Klasse, die eine Feste Länge-array von Zeichen? Können Sie konvertieren Sie Ihre strings in zahlen oder Daten, Struktur mit nur zahlen?

Versuchen, std::tr1::unordered_map (gefunden in der header <tr1/unordered_map>). Dies ist eine hash-map, und während es doesn ' T erhalten eine sortierte Reihenfolge der Elemente, wird wahrscheinlich weit schneller als eine reguläre Karte.

Wenn Ihr compiler nicht unterstützt, TR1, erhalten eine neuere version. MSVC und gcc unterstützen beide TR1, und ich glaube, dass die neuesten Versionen der meisten anderen Compilern auch unterstützen. Leider, eine Menge der Bibliothek Referenz-Websites noch nicht aktualisiert wurde, so TR1 bleibt eine weitgehend unbekannte Stück Technik.

Ich hoffe, dass C++0x ist nicht die gleiche Weise.

EDIT: Beachten Sie, dass die Standard-hashing-Methode für tr1::unordered_map ist tr1::hash, die spezialisiert werden, um die Arbeit auf eine UDT, wahrscheinlich.

hash_map ist nicht standard, versuchen Sie es mit unordered_map erhältlich in tr1 (welcher in steigern, wenn Sie Ihre tool-Kette nicht bereits haben).

Einer kleinen Anzahl von Zeichenfolgen, die Sie vielleicht besser mit vector als map wird normalerweise implementiert, wie ein Baum.