Switch-Optimierung für viele Fälle garantiert gleiche Zugriffszeit für jeden Fall? (C ++)

Der Standard garantiert nicht, wie die switch-Anweisung implementiert wird. Ich habe noch nie einen Compiler gesehen, der eine Hash-Tabelle erzeugt, obwohl einige eine Sprungtabelle erzeugen werden. Wenn mein Gedächtnis nicht schlechter arbeitet als gewöhnlich, können sowohl VS als auch gcc Sprungtabellen erzeugen, wenn die Fälle ausreichend dicht sind (für unterschiedliche Werte von "ausreichend"). Leider ist es fast unmöglich zu sagen (oder notwendigerweise sogar herauszufinden), wenn die Sortierung nach Häufigkeit des Auftretens helfen wird - es ist nicht nur zwischen Compilern, sondern auch zwischen verschiedenen Versionen desselben Compilers anders.

Für die gcc-Implementierung siehe:

Ссылка

• C und C ++ garantieren nichts über die Laufzeit von switch-Anweisungen.
• Ich fürchte, ich kenne die Implementierungsdetails für einen Compiler nicht. Es hängt wahrscheinlich von Optimierungsflags ab.
• Das Sortieren von Fällen ist nicht garantiert, um zu helfen, wieder ist es nicht durch den Standard spezifiziert und Ihre Implementierung kann oder kann nicht:
  • Mache verschiedene Dinge entsprechend den Compileroptionen
  • Dokumentieren Sie, was es tut
  • Garantie, nicht zu ändern, was es in zukünftigen Versionen tut
  • Ignoriere die Reihenfolge der Fälle in der Quelle vollständig und ordne sie nach Belieben an. Vorausgesetzt natürlich, die Fälle sind "unabhängig": kein Durchfallen; keine Variablendeklarationen, die in einem Fall beginnen und einen anderen Fall aufspannen; nichts anderes habe ich vergessen.

c (und durch Erweiterung c ++) schaltet nur ganzzahlige Typen ein, so dass Hashing nicht notwendig ist. Der Compiler verwendet normalerweise ein Idiom, das der Architektur entspricht, für die Sie kompilieren. Dies könnte eine indizierte Adressierung sein (wenn ein kleiner Bereich verwendet wird), Sprungtabellen oder etwas völlig anderes.

Das wird der Compiler für Sie tun. Im Fall von GCC wird es eine Sprungtabelle verwenden.

Ein Hash scheint keine effiziente Methode zu sein, einen Switch zu implementieren, weil Sie aufgrund der Suche zusätzliche Cache-Fehler haben werden.