Ich würde gerne wissen, was die Worst-Case-Laufzeit Komplexität einer switch-Anweisung ist, vorausgesetzt, Sie haben n Fällen.Was ist die Laufzeitkomplexität einer switch-Anweisung?
Ich nahm immer an, es war O (n). Ich weiß nicht, ob Compiler etwas schlaues tun. Wenn die Antwort Implementierung spezifisch ist, würde Ich mag für die folgenden Sprachen wissen:
Es ist schlimmstenfalls O (n). Manchmal (und dies ist abhängig von Sprache und Compiler) wird es in eine Jump-Table-Suche übersetzt (für "nette" Switches, die keinen zu großen Fallbereich haben). Dann ist das O (1).
Wenn der Compiler funky sein will, kann ich mir vorstellen, wie die Komplexität implementiert werden kann, um irgendetwas dazwischen zu sein (z. B. binäre Suche in den Fällen, für logn). In der Praxis erhalten Sie jedoch eine lineare oder konstante Zeit.
Die große O-Komplexität einer switch-Anweisung ist nicht wirklich der wichtige Punkt. Die Big-O-Notation bezieht sich auf die Performance, wenn n in Richtung Unendlichkeit zunimmt. Wenn Sie eine switch-Anweisung haben, die groß genug ist, dass die asymptotische Leistung ein Problem ist, dann ist es zu groß und sollte refaktorisiert werden.
Abgesehen von der Lesbarkeit, in Java und C# Ich glaube, Sie würden bald einige interne Grenzen für die maximale Größe einer einzelnen Methode treffen.
Für relativ kleine Switch-Anweisungen, die oft aufgerufen werden, wäre es wahrscheinlich informativer, die tatsächliche Leistung der switch-Anweisung mit anderen Ansätzen zu vergleichen, die Sie stattdessen verwenden könnten. Diese Messung könnte durch wiederholtes Durchführen der Operation in einer Schleife durchgeführt werden.
Für größere Switch-Anweisungen würde ich Refactoring vorschlagen, um ein Wörterbuch oder ähnliche Datenstruktur zu verwenden, die ungefähr O (1) Leistung hat sogar n wird sehr groß und es wird keine Probleme mit der begrenzten Methode Größe.
Wenn eine 10-Fall-Switch-Anweisung oft genug aufgerufen wird, wäre es nicht sinnvoll zu versuchen, zu verstehen wie es intern funktioniert? – Fragsworth
stimme ich voll und ganz zu. Wenn Sie mehr als 10 Fälle bekommen, verlieren Sie schnell die Lesbarkeit und Einfachheit. Normalerweise gibt es einen besseren, klareren Weg. –
@Fragsworth ja, du solltest unbedingt versuchen zu verstehen, wie es intern funktioniert. Aber das einzige, was Big-O Ihnen sagt, ist, wie schnell es mit vielen Fällen ist, sagen wir 100+. Der Punkt von Mark ist, dass es viel bessere Möglichkeiten gibt, die Interna der Switch-Anweisungen zu analysieren, ohne auf sein Big-O zu schauen, wie der Compiler es optimiert und wie es mit anderen Methoden wie einer Look-Up-Tabelle verglichen wird. –
C++ - Compiler können Switch-Anweisungen in eine Jump-Tabelle umwandeln (d. H. Ein Array von Jump-Offsets erstellen, dann den Wert übernehmen und als Index in die Tabelle verwenden). Das ist O (1).
Der C# -Compiler verwendet einen ähnlichen Ansatz, außer dass es eine Hash-Tabelle zusammenstellen kann.
Der schlechteste Fall könnte O (n) sein, aber zumindest für Sprachen wie C/C++, Java und C#, wo die Fälle Kompilierzeitkonstanten sind, kann eine Sprungtabelle oft verwendet werden (und wird oft verwendet) um die Komplexität auf O (1) zu bringen.
Ich weiß nicht, ob die dynamischeren Sprachen wie PHP oder Javascript versuchen Sprungtabellen zu erstellen oder nicht.
Für PHP müssen Fall Ausdrücke nicht konstant sein; 'switch (true) {fall expr: doSomething(); } 'ist gültig, auch wenn ausdruck nicht konstant ist. Das heißt, wenn ich mich richtig erinnere. Also Sprungtabellen wären für so etwas unwahrscheinlich. – user314104
C mit GCC-Compiler hat O (1) für engen Bereich (Jump-Tabelle) oder im schlimmsten Fall O (log N) für losen Bereich (binäre Suche).
Die Antwort ist nicht nur sprachspezifisch, nicht einmal compilerspezifisch. Es hängt vom tatsächlichen Code ab. Einige switch-Anweisungen werden von einigen Compilern in Jump-Tabellen umgewandelt. –
Im anderen Extremfall können die Werte dazu führen, dass andere Funktionen aufgerufen werden. In Ruby zum Beispiel werden Werte mit dem Operator '===' überprüft, der alles kann. Eine übliche Verwendung davon sind reguläre Ausdrücke, die (in bestimmten Fällen) sehr teuer sein können - also werden die Kosten des Schalters von den Werten selbst bestimmt, nicht von der Anzahl der Werte. – Ken
Gibt es eine Situation, in der es * größer * als O (n) sein könnte (für * n * Fälle im Switch)? – FrustratedWithFormsDesigner