Ich habe einige Datenstrukturen:
all_unordered_m ist ein großer Vektor, der alle benötigten Strings enthält (alle unterschiedlich) ordered_m ist ein kleiner Vektor, der die Indizes einer Teilmenge der Strings (alle unterschiedlich) im vorherigen Vektor position_m bildet die Indizes der Objekte vom ersten Vektor auf ihre Position in der zweiten ab. Die Methode string_after(index, reverse) gibt die Zeichenfolge zurück, auf die request_m nach all_unordered_m[index] .
ordered_m wird als zirkulär betrachtet und abhängig vom zweiten Parameter in natürlicher oder umgekehrter Reihenfolge untersucht.
Der Code ist ungefähr wie folgt:
%Vor%Angesichts dessen:
Wie kann ich die string_after -Methode beschleunigen, die milliardenfach aufgerufen wird und etwa 10% der Ausführungszeit in Anspruch nimmt?
BEARBEITEN:
Ich habe versucht, position_m a vector anstelle von unordered_map zu machen und die folgende Methode zu verwenden, um Sprünge zu vermeiden:
Die Änderung von position_m scheint am effektivsten zu sein (ich bin mir nicht sicher, ob die Eliminierung der Verzweigungen einen Unterschied macht, ich bin versucht zu sagen, dass der Code kompakter ist, aber genauso effizient in dieser Hinsicht).
> vector lookups sind blitzschnell. size() Aufrufe und einfache Arithmetik sind blitzschnell. map lookups sind im Vergleich dazu so langsam wie eine tote Schildkröte mit einem Betonblock auf dem Rücken. Ich habe oft gesehen, dass diese bei ansonsten einfachem Code wie diesem zu einem Flaschenhals werden.
Sie könnten stattdessen unordered_map aus TR1 oder C ++ 0x (eine Drop-in-Hashtabelle-Ersetzung von map ) versuchen und sehen, ob das einen Unterschied macht.
Nun, in solchen Fällen (eine kleine Funktion, die oft aufgerufen wird) kann jede Verzweigung sehr teuer sein. Da fallen mir zwei Dinge ein.
reverse weglassen und zwei separate Methoden erstellen? Dies macht nur dann Sinn, wenn die if -Anweisung nicht einfach an den aufrufenden Code übergeben wird. pos : pos = (pos + 1) % ordered_m.size() zu berechnen (dies gilt für den Vorwärtsfall). Dies funktioniert nur, wenn Sie sicher sind, dass pos beim Inkrementieren niemals überläuft. Im Allgemeinen versuchen Sie, in solchen Fällen Zweige durch arithmetische Operationen zu ersetzen, dies kann zu einer erheblichen Beschleunigung führen.
Tags und Links optimization c++ performance