Im Moment findet meine Funktion den Median von 3 Zahlen und sortiert sie, aber sie macht immer drei Vergleiche. Ich denke, dass ich eine verschachtelte if-Anweisung irgendwo verwenden kann, so dass meine Funktion manchmal nur zwei Vergleiche macht.
%Vor%Ich bin mir nicht sicher, ob ich sehe, wo ich diese verschachtelte if-Anweisung machen kann.
Wenn Sie nur den Medianwert benötigen, verwenden Sie eine Verzweigungslösung, die auf Min / Max-Operatoren basiert:
median = max(min(a,b), min(max(a,b),c));
Intel CPUs haben SSE min / max Vektor Befehle, abhängig von der Fähigkeit Ihres Compilers zu vektorisieren, kann dies extrem schnell laufen.
Wenn wir zusätzliche Operationen zulassen, können wir höchstens zwei Vergleiche verwenden, um den Median zu finden. Der Trick besteht darin, exklusive oder die Beziehung zwischen drei Zahlen zu verwenden.
%Vor% Das erste exklusive oder (e ^ f) soll die Differenz des Vorzeichenbits zwischen (a-b) und (a-c) herausfinden.
Wenn sie unterschiedliche Vorzeichen haben, ist a der Median. Ansonsten ist a entweder das Minimum oder das Maximum. In diesem Fall brauchen wir das zweite exklusive oder (e ^ g).
Auch hier werden wir den Unterschied des Vorzeichenbits zwischen (a-b) und (b-c) herausfinden. Wenn sie ein anderes Vorzeichenbit haben, ist ein Fall, dass ein & gt; b & amp; & amp; b & lt; c. In diesem Fall erhalten wir auch a & gt; c weil in diesem Fall das Maximum ist. Also haben wir a & gt; c & gt; b. Der andere Fall ist a & lt; b & amp; & amp; b & gt; c & amp; & amp; ein & lt; c . Also haben wir ein & lt; c & lt; b ; In beiden Fällen ist c der Median .
Wenn (ab) und (bc) dasselbe Vorzeichenbit haben, ist b der Median Verwenden ähnlicher Argumente wie oben. Experimente zeigen, dass eine zufällige Eingabe 1,667 Vergleiche benötigt, um den Median und einen zusätzlichen Vergleich zu ermitteln, um die Reihenfolge zu erhalten.
Um 3 Elemente zu sortieren, benötigen Sie genau 3 Vergleiche.
Um den mittleren zufällig zu finden, brauchen Sie 2.
Um den mittleren genau zu finden, benötigen Sie im Durchschnitt 2 + 2/3 ~ = 2,67 (mit gleichmäßig verteilten Zufallsdaten)
%Vor%Als zusätzliche Randnotiz: Einige Sprachen (Fortran, IIRC), sowie einige ISAs (VAX, wieder IIRC) unterstützen Vergleiche, wobei die nächste PC-Adresse aus drei Möglichkeiten ausgewählt wird: LT, EQ, GT. Mit klein genug Alphabet reduziert diese Chance leicht die Anzahl der benötigten Vergleiche.
Auch dies hat vermutlich keinen praktischen Nutzen, da Strafen aufgrund falscher Verzweigungsvorhersagen wegen zu komplexer verschachtelter Strukturen viel größer sein können als Gewinne aus einem gespeicherten Vergleich.