Ich habe versucht, mir einen Weg zu überlegen, wie ich zwei Vergleiche gleichzeitig machen kann, um die größte / kleinste von drei Zahlen zu finden. Arithmetische Operationen an ihnen werden in diesem Fall als "frei" betrachtet.
Das heißt, der klassische Weg, den größeren von zwei zu finden und ihn dann mit der dritten Zahl zu vergleichen, ist in diesem Fall nicht gültig, weil ein Vergleich vom Ergebnis des anderen abhängt.
Ist es möglich, zwei Vergleiche zu verwenden, wenn dies nicht der Fall ist? Ich dachte daran, vielleicht die Unterschiede der Zahlen irgendwie zu vergleichen oder ihre Produkte oder so etwas, aber nichts gefunden.
Nur um noch einmal zu betonen, zwei Vergleiche werden immer noch gemacht, nur dass keiner der beiden Vergleiche auf dem Ergebnis des anderen Vergleichs beruht.
Tolle Antworten bisher, danke Jungs
Ich denke, es ist möglich (das Folgende ist für das Min, entsprechend der ursprünglichen Form der Frage):
%Vor%und dann kombinieren Sie diese (ich muss es sequentiell schreiben, aber das ist eher ein 3-Wege-Schalter):
%Vor% Sie könnten argumentieren, dass abs() einen Vergleich impliziert, aber das hängt von der Hardware ab. Es gibt einen Trick, es ohne Vergleich zu tun für ganze Zahlen. Für IEEE 754 Gleitkomma ist es nur eine Frage des Erzwingens des Vorzeichen-Bits auf Null.
Bezüglich (A + B - abs(A - B)) / 2 : das ist (A + B) / 2 - abs(A - B) / 2 , d. h. das Minimum von A und B ist die Hälfte der Entfernung zwischen A und B abwärts von ihrem Mittelpunkt. Dies kann erneut angewendet werden, um min (A, B, C) zu erhalten, aber dann verlieren Sie die Identität des Minimums, dh Sie kennen nur den Wert des Minimums aber nicht wo es herkommt.
Eines Tages werden wir feststellen, dass die Parallelisierung der beiden Vergleiche in einigen Situationen zu einer besseren Bearbeitungszeit oder sogar zu einem besseren Durchsatz führt. Wer weiß, vielleicht für eine Vektorisierung oder für eine MapReduce oder für etwas, von dem wir noch nichts wissen.
Wenn man die Möglichkeit gleicher Werte ("Bindungen") ignoriert, gibt es 3! : = 6 mögliche Bestellungen von drei Artikeln. Wenn ein Vergleich genau ein Bit ergibt, können zwei Vergleiche nur 2 * 2: = 4 mögliche Konfigurationen codieren. und 4 & lt; 6. IOW: Sie können die Reihenfolge der drei Elemente nicht anhand von zwei festen Vergleichen bestimmen.
Verwenden einer Wahrheitstabelle:
%Vor% Wie Sie sehen, können Sie die beiden Fälle, die durch (*) markiert sind, nicht unterscheiden, wenn Sie nur die Vergleiche a<b und a<c verwenden. (Die Wahl eines anderen Satzes von zwei Vergleichen wird natürlich ähnlich ausfallen (durch Symmetrie)).
Aber es ist schade: Wir können die drei möglichen Ergebnisse nicht mit nur zwei Bits kodieren. (Ja, wir könnten, aber wir würden einen dritten Vergleich brauchen, oder wählen Sie den zweiten Vergleich basierend auf dem Ergebnis des ersten)
Wenn du nur ganze Zahlen sprichst, denke ich, dass du es mit Null-Vergleichen mit etwas Mathe und etwas Geige machen kannst. Gegeben drei int-Werte a, b und c:
%Vor%mit Abs (x) als
implementiert %Vor%Nicht ausgiebig getestet, also habe ich vielleicht etwas verpasst. Kredit für die Abs Bit-Twiddle geht zu diesen Quellen
Sie können dies mit Null-Vergleichen in der Theorie tun, indem Sie die Zweierkomplement-Zahlendarstellung annehmen (und dass das Rechtsverschieben einer vorzeichenbehafteten Zahl ihr Vorzeichen erhält).
%Vor%und dann
%Vor% Dies funktioniert, weil a >> bit_depth 0 für positive Zahlen und -1 für negative Zahlen annimmt. 2*(a>>bit_depth)+1 ergibt 1 für positive Zahlen und -1 für negative Zahlen. Dies gibt die Funktion signum und wir erhalten abs(a) = signum(a) * a .
Dann ist es nur eine Frage der Formel min (a, b). Dies kann demonstriert werden, indem man die zwei Möglichkeiten durchgeht:
%Vor%Also funktioniert die Formel für min (a, b).
Die obigen Annahmen gelten nur für die abs() -Funktion. Wenn Sie für Ihren Datentyp eine 0-Vergleich abs() -Funktion erhalten, dann können Sie loslegen.
Zum Beispiel haben IEEE754 Gleitkommadaten ein Vorzeichenbit als das oberste Bit, so dass der absolute Wert einfach bedeutet, dass dieses Bit gelöscht wird. Dies bedeutet, dass Sie auch Gleitkommazahlen verwenden können.
Und dann können Sie dies auf min von N Zahlen in 0 Vergleichen erweitern.
In der Praxis ist es schwer vorstellbar, dass diese Methode alles absichtlich langsamer schlagen wird. Es geht darum, weniger als 3 unabhängige Vergleiche zu verwenden, nicht darum, etwas schneller zu machen als die einfache Implementierung in der Praxis.
Tags und Links algorithm comparison