Was ist effizienter, ein Schaltergehäuse oder ein std :: map

StackOverflow https://stackoverflow.com/questions/931890

  •  06-09-2019
  •  | 
  •  

Frage

Ich denke an die tokenizer hier.
Jedes Token ruft eine andere Funktion innerhalb des Parsers.
Was ist effizienter:

  • Eine Karte von std :: Funktionen / boost :: Funktionen
  • Ein Schaltergehäuse
War es hilfreich?

Lösung

STL Karte, die mit Visual Studio 2008 kommt Sie geben O (log (n)) für jede Funktionsaufruf, da sie eine Baumstruktur unterhalb verbirgt. Mit modernen Compiler (je nach Ausführung), wird eine switch-Anweisung gibt Ihnen O (1), den Compiler es zu irgendeiner Art von Lookup-Tabelle übersetzt. So im Allgemeinen Schalter ist schneller.

Doch , die folgenden Fakten:

Der Unterschied zwischen Karte und Schalter ist, dass: Karte eingebaut werden können dynamisch während der Schalter nicht. Karte kann jede beliebige Art als Schlüssel enthalten, während der Schalter ist sehr beschränkt auf c ++ Urtyp (char, int, ENUM, etc ...).

Durch die Art und Weise können Sie einen Hash-Map verwenden fast O (1) Dispatching zu erreichen (wenn auch in Abhängigkeit von der Hash-Tabelle Implementierung kann es manchmal O (n) im schlimmsten Fall sein). Auch wenn wird, Schalter noch schneller sein.

Bearbeiten

Ich schreibe folgende nur zum Spaß und für die Sache der Diskussion

kann ich eine nette Optimierung für Sie vorschlagen, aber es hängt von der Art Ihrer Sprache und ob Sie erwarten können, wie Sie Ihre Sprache verwendet wird.

Wenn Sie den Code schreiben: Sie teilen Sie Ihre Jetons in zwei Gruppen, wird eine Gruppe von sehr hoch seine häufig verwendet und den anderen niedrig häufig verwendet. Sie sortieren auch die hohe häufig verwendeten Token. Für die hohe Token Sie häufig eine if-else-Serie mit dem höchsten häufig verwendeten kommt zuerst schreiben. für die niedrigen häufig verwendet, können Sie eine switch-Anweisung schreiben.

Die Idee ist, die CPU-Verzweigungsvorhersage verwenden, um auf noch eine andere Dereferenzierungsebene zu vermeiden (vorausgesetzt, die Bedingung in der if-Anweisung überprüft ist fast keine Kosten verursachen). In den meisten Fällen wird die CPU den richtigen Zweig ohne Dereferenzierungsebene holen. Sie werden nur wenige Fälle geben, jedoch, dass die Filiale an der falschen Stelle gehen. Je nach Art Ihres languege, statistisch erfasst es kann eine bessere Leistung geben.

Bearbeiten . Aufgrund einiger Kommentare unten, ändert es den Satz zu sagen, dass Compiler und wird immer einen Schalter LUT übersetzen

Andere Tipps

Ich würde vorschlagen, das Lesen Schalter () vs. Lookup-Tabelle? von Joel on Software. Insbesondere diese Antwort ist interessant:

  

“Prime Beispiel von Menschen, Zeit zu verschwenden   versuchen, die am wenigsten zu optimieren   bedeutende Sache. "

     

Ja und nein. In einer VM, Sie in der Regel   rufen kleine Funktionen, die jeder sehr tun   wenig. Es ist das nicht der Anruf / Rückkehr   das tut weh, so viel wie die Präambel   und clean-up-Routine für jede Funktion   wobei oft ein erheblicher Prozentsatz   der Ausführungszeit. Dies wurde   erforscht zu Tode, vor allem durch   Menschen, die Gewinde implementiert haben   Dolmetscher.

In virtuellen Maschinen, Lookup-Tabellen Speichern von Adressen berechnet werden, rufen in der Regel zu den Schaltern bevorzugt. (Direkte Einfädeln oder „Label als Wert“. Anrufe direkt die Label-Adresse in der Nachschlagtabelle gespeichert) Das ist, weil es erlaubt, unter bestimmten Bedingungen zu reduzieren das Verhalten von effiziente Virtual Machine Interpreter auf moderne Architekturen

Aber wie gesagt, ich bin mir ziemlich sicher, dass diese Angaben für nicht relevant sind Ihr Code. Das sind kleine Details, und Sie sollten nicht zu sehr auf sie. Python-Interpreter ist Schalter verwenden, weil sie denken, es den Code besser lesbar macht. Warum Sie nicht über die Verwendung wählen Sie die bequemste mit sind? Auswirkungen auf die Leistung sein wird, eher klein, würden Sie besser auf die Lesbarkeit des Codes konzentrieren jetzt;)

Bearbeiten : Wenn es darauf ankommt, wird eine Hash-Tabelle mit immer langsamer als eine Nachschlagtabelle. Für eine Lookup-Tabelle, verwenden Sie Aufzählungstypen für Ihren „Schlüssel“, und der Wert eines einzelnen indirekten Sprung abgerufen werden. Dies ist ein einziger Montagevorgang. O (1). Eine Hash-Tabelle Lookup erfordert zunächst einen Hash zu berechnen, dann den Wert abzurufen, die viel teurer ist.

unter Verwendung einer Anordnung, wo die Funktionsadressen gespeichert werden, und der Zugriff unter Verwendung von Werten eines ENUM gut ist. Aber mit einer Hash-Tabelle, das gleiche zu tun, fügt einen wichtigen Kopf

Um es zusammenzufassen, wir haben:

  • Kosten (Hash_table) >> Kosten (direct_lookup_table)
  • Kosten (direct_lookup_table) ~ = Kosten (Schalter), wenn Ihr Compiler-Schalter in Lookup-Tabellen übersetzt.
  • Kosten (Schalter) >> Kosten (direct_lookup_table) (O (N) vs O (1)), wenn Ihre Compiler-Schalter nicht übersetzen und conditionals verwenden, aber ich kann nicht, dass dies von jedem Compiler zu tun.
  • Aber inlined direkter Threading macht den Code weniger lesbar.

Was ist Ihre Definition von „effizient“? Wenn Sie schneller bedeuten, dann wahrscheinlich sollten Sie einige Test-Code für eine bestimmte Antwort profilieren. Wenn Sie jedoch nach flexiblen und einfach zu erweitern Code sind, tun Sie sich dann einen Gefallen und die Karte Ansatz. Alles andere ist nur vorzeitige Optimierung ...

Wie yossi1981 sagte ein Schalter optimiert werden, um eine schnelle Lookup-Tabelle des Seins, aber es ist nicht garantiert, hat jeder Compiler andere Algorithmen, um zu bestimmen, ob den Schalter als in Folge zu implementieren, wenn der oder so schnell Lookup-Tabelle, oder vielleicht eine Kombination von beiden.

ein schnell zu gewinnen Ihre Werte wechseln soll die folgende Regel erfüllen: sie sollten in Folge sein, das heißt z.B. 0,1,2,3,4. Sie können einige Werte weglassen, aber Dinge wie 0,1,2,34,43 sind extrem unwahrscheinlich optimiert werden.

Die Frage ist wirklich: ist die Leistung solcher Bedeutung in der Anwendung? Und würde nicht eine Karte, die dynamisch aus einer Datei ihre Werte lädt mehr lesbar und wartbar statt einer großen Erklärung, die mehr Seiten Code umspannt?

Sie sagen nicht, was geben Sie Ihre Token sind. Wenn sie keine ganzen Zahlen sind, haben Sie keine Wahl - Schalter nur mit Integer-Typen arbeiten.

Der C ++ Standard sagt nichts über die Leistung seiner Anforderungen, nur dass die Funktionalität sollte es sein.

Diese Art von Fragen, über die besser oder schneller oder effizienter sind bedeutungslos, wenn Sie angeben, die Implementierung Sie sprechen. Zum Beispiel war die Zeichenfolge in einer bestimmten Version einer bestimmten Implementierung von JavaScript Umgang mit scheußlich, aber man kann das nicht extrapoliert ein Merkmal der entsprechenden Norm zu sein.

Ich würde sogar so weit gehen, zu sagen, es spielt keine Rolle, unabhängig von der Implementierung, da die Funktionalität von switch und std::map bereitgestellt unterscheidet (obwohl es Überschneidungen gibt).

Diese Art von Mikro-Optimierungen sind fast nie nötig, meiner Meinung nach.

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top