Ein Interviewer hat mir kürzlich diese Frage gestellt: Wenn drei boolesche Variablen a, b und c gegeben sind, wird true zurückgegeben, wenn mindestens zwei der drei true sind.
Meine Lösung folgt:
boolean atLeastTwo(boolean a, boolean b, boolean c) {
if ((a && b) || (b && c) || (a && c)) {
return true;
}
else{
return false;
}
}
Er sagte, dass dies weiter verbessert werden kann, aber wie?
java
boolean
boolean-logic
Benutzer282886
quelle
quelle
atLeastTwo(iWantYou, iNeedYou, imEverGonnaLoveYou)
Antworten:
Anstatt zu schreiben:
Schreiben:
Was den Ausdruck selbst betrifft, so etwas:
oder dies (je nachdem, was Sie leichter verstehen):
Es testet
a
undb
genau einmal undc
höchstens einmal.Verweise
quelle
return hasGoodAttendance ? (passedCoursework || passed Exam) : (passedCoursework && passedExam)
, das sieht für mich gut aus.atLeastTwo(hasgoodAttendance, passedCoursework, passedExam)
. Die Idee von "mindestens 2 Bools sind wahr" ist allgemein genug, um ihre eigene Funktion zu verdienen.Nur um XOR zur Beantwortung eines relativ einfachen Problems zu verwenden ...
quelle
Warum nicht wörtlich umsetzen? :) :)
In C könnte man einfach schreiben
a+b+c >= 2
(oder!!a+!!b+!!c >= 2
um sehr sicher zu sein).Als Antwort auf TofuBeers Vergleich des Java-Bytecodes ist hier ein einfacher Leistungstest:
Dies druckt Folgendes auf meinem Computer (unter Ubuntu unter Intel Core 2 + Sun Java 1.6.0_15-b03 mit HotSpot Server VM (14.1-b02, gemischter Modus)):
Erste und zweite Iteration:
Spätere Iterationen:
Ich frage mich, was könnte Java VM tun, das verschlechtert Leistung im Laufe der Zeit für (a + b + c> = 2) Fall .
Und hier ist, was passiert, wenn ich Java mit einem ausführe
-client
VM-Switch :Geheimnis...
Und wenn ich es in GNU Java Interpreter laufen lasse , wird es fast 100-mal langsamer, aber die
a&&b || b&&c || a&&c
Version gewinnt dann.Ergebnisse von Tofubeer mit dem neuesten Code unter OS X:
Ergebnisse von Paul Wagland mit einem Mac Java 1.6.0_26-b03-383-11A511
quelle
a+b+c >= 2
: Das funktioniert nicht mit Negativen, oder? Möglicherweise müssen Sie das!!a
tun, ich bin mir nicht sicher.Diese Art von Fragen kann mit einer Karnaugh-Karte gelöst werden :
Daraus schließen Sie, dass Sie eine Gruppe für die erste Zeile und zwei Gruppen für die erste Spalte benötigen, um die optimale Lösung für Polygenschmierstoffe zu erhalten:
quelle
Lesbarkeit sollte das Ziel sein. Jemand, der den Code liest, muss Ihre Absicht sofort verstehen. Hier ist meine Lösung.
quelle
Seq(true, true, false).map(if (_) 1 else 0).sum >= 2
Erläuterung:
Wenn ja
a==b
, dann sind beide wahr oder beide sind falsch. Wenn beide wahr sind, haben wir unsere zwei wahren Booleschen Werte gefunden und können wahr zurückgeben (indem wir zurückkehrena
). Wenn beide falsch sind, kann es auch dann keine zwei wahren Booleschen Werte geben, wennc
dies wahr ist. Daher geben wir false zurück (indem wir zurückkehrena
). Das ist der(a==b) ? a
Teil. Was ist mit: c
? Nun, wenna==b
es falsch ist, dann ist genau eines vona
oderb
muss wahr sein, also haben wir den ersten wahren Booleschen Wert gefunden, und das einzige, was noch zählt, ist, obc
es auch wahr ist, also kehren wirc
als Antwort zurück.quelle
a
undb
stimme zu, sie haben die Mehrheit der Stimmen, also mach mit, was auch immer es ist, sonst sind sie anderer Meinung, soc
ist die entscheidende Stimme"Sie müssen die Kurzschlussformen der Operatoren nicht verwenden.
return (a & b) | (b & c) | (c & a);
Dies führt die gleiche Anzahl von Logikoperationen aus wie Ihre Version, ist jedoch vollständig verzweigungslos.
quelle
Hier ist ein testgetriebener, allgemeiner Ansatz. Nicht so "effizient" wie die meisten bisher angebotenen Lösungen, aber klar, getestet, funktionsfähig und verallgemeinert.
quelle
Fass es zusammen. Es heißt Boolesche Algebra aus einem Grund:
Wenn Sie sich die Wahrheitstabellen dort ansehen, können Sie sehen, dass die Multiplikation boolesch ist und und die Addition einfach xor ist.
Zur Beantwortung Ihrer Frage:
quelle
return ((a?1:0) + (b?1:0) + (c?1:0)) >= 2
.quelle
Es kommt wirklich darauf an, was Sie unter "verbessert" verstehen:
Klarer?
Terser?
Allgemeiner?
Skalierbarer?
Schneller?
Welches "verbessert" wird, hängt stark von der Situation ab.
quelle
Hier ist eine weitere Implementierung mit map / redu. Dies lässt sich gut auf Milliarden von Booleschen Werten skalieren © in einer verteilten Umgebung. Verwenden von MongoDB:
Erstellen einer Datenbank
values
mit Booleschen Werten:Erstellen Sie die Karte, reduzieren Sie die Funktionen:
Bearbeiten : Ich mag CurtainDogs Antwort, dass Map / Reduce auf generische Listen angewendet werden soll. Hier ist eine Map-Funktion, die einen Rückruf entgegennimmt, der bestimmt, ob ein Wert gezählt werden soll oder nicht.
Laufende Karte / Reduzieren:
quelle
Nehmen Sie die Antworten (bisher) hier:
und sie durch den Dekompiler laufen lassen (javap -c X> results.txt):
Sie können sehen, dass die ?: Diejenigen etwas besser sind als die reparierte Version Ihres Originals. Das Beste ist das, das eine Verzweigung insgesamt vermeidet. Dies ist unter dem Gesichtspunkt weniger Anweisungen (in den meisten Fällen) gut und besser für Teile der Verzweigungsvorhersage der CPU, da eine falsche Schätzung in der Verzweigungsvorhersage zu einem Blockieren der CPU führen kann.
Ich würde sagen, das effizienteste ist das von Moonshadow insgesamt. Es verwendet im Durchschnitt die wenigsten Anweisungen und verringert die Wahrscheinlichkeit, dass die Pipeline in der CPU blockiert.
Um 100% sicher zu sein, müssten Sie die Kosten (in CPU-Zyklen) für jeden Befehl ermitteln, der leider nicht sofort verfügbar ist (Sie müssten sich die Quelle für den Hotspot und dann die Spezifikationen der CPU-Anbieter für die Zeit ansehen für jede generierte Anweisung genommen).
In der aktualisierten Antwort von Rotsor finden Sie eine Laufzeitanalyse des Codes.
quelle
Ein weiteres Beispiel für direkten Code:
Es ist offensichtlich nicht der prägnanteste Code.
Nachtrag
Eine andere (leicht optimierte) Version davon:
Dies läuft möglicherweise etwas schneller, vorausgesetzt, der Vergleich mit 0 verwendet schnelleren (oder möglicherweise weniger) Code als der Vergleich mit 2.
quelle
++n
ist schneller alsn++
weil Sie vor dem Inkrementieren eine weitere Kopie erstellen müssen .n
oben) kompiliert jeder anständige Compiler jede++
Operation in einen einzelnen CPU-Befehl, egal ob vor oder nach dem Vorgang.Noch ein anderer Weg, aber kein sehr guter:
Die
Boolean
Hashcode-Werte sind für true auf 1231 und für false auf 1237 festgelegt und könnten daher ebenfalls verwendet werden<= 3699
quelle
Die offensichtlichsten Verbesserungen sind:
und dann
Diese Verbesserungen sind jedoch geringfügig.
quelle
Ich mag ternary nicht (
return a ? (b || c) : (b && c);
von der obersten Antwort), und ich glaube nicht, dass ich jemanden gesehen habe, der es erwähnt. Es ist so geschrieben:quelle
In Clojure :
Verwendungszweck:
quelle
Ich glaube, ich habe diese Lösung noch nicht gesehen:
Sein Vorteil ist, dass es bricht, sobald es die gesuchte Zahl erreicht hat. Wenn dies also "mindestens 2 von diesen 1.000.000 Werten sind wahr" war, wo die ersten beiden tatsächlich wahr sind, dann sollte es schneller gehen als einige der "normaleren" Lösungen.
quelle
boolean ... boolValues
, es ist einfacher anzurufen, nimmt aber immer noch ein ArrayWir können die Bools in ganze Zahlen konvertieren und diese einfache Überprüfung durchführen:
quelle
Da nicht angegeben wurde, wie der Code verbessert werden soll, werde ich mich bemühen, den Code zu verbessern, indem ich ihn amüsanter mache. Hier ist meine Lösung:
Falls sich jemand fragt, ob dieser Code funktioniert, finden Sie hier eine Vereinfachung mit derselben Logik:
}}
Dies kann weiter auf Folgendes reduziert werden:
Aber jetzt ist es nicht mehr lustig.
quelle
Zu viele Möglichkeiten, dies zu tun ...
quelle
AC-Lösung.
oder Sie bevorzugen vielleicht:
quelle
quelle
Der einfachste Weg (IMO), der nicht verwirrend und leicht zu lesen ist:
quelle
(C && (A || B)) || (A && B)
gerade die * Variablennamen geändert ...Eine wörtliche Interpretation funktioniert in allen wichtigen Sprachen:
Aber ich würde es den Leuten wahrscheinlich leichter machen, zu lesen und auf mehr als drei zu erweitern - etwas, das von vielen Programmierern vergessen zu sein scheint:
quelle
Betrachten Sie als Ergänzung zu @TofuBeer TofuBeers ausgezeichnetem Beitrag die Antwort von @pdox pdox:
Betrachten Sie auch die zerlegte Version von "javap -c":
Die Antwort von pdox wird mit weniger Bytecode kompiliert als jede der vorherigen Antworten. Wie ist die Ausführungszeit im Vergleich zu den anderen?
Zumindest auf meinem Computer ist die Antwort von pdox nur geringfügig schneller als die von @moonshadow moonshadow, sodass pdox insgesamt die schnellste ist (auf meinem HP / Intel-Laptop).
quelle
In Ruby:
[a, b, c].count { |x| x } >= 2
Welches könnte in JRuby auf der JavaVM ausgeführt werden. ;-);
quelle
Er sucht wahrscheinlich nicht nach etwas Verwickeltem wie bitweisen Vergleichsoperatoren (normalerweise nicht verschlungen, aber mit Booleschen Werten ist es äußerst seltsam, bitweise Operatoren zu verwenden) oder etwas, das sehr umständlich ist, wie das Konvertieren in int und das Summieren.
Der direkteste und natürlichste Weg, dies zu lösen, ist ein Ausdruck wie dieser:
Fügen Sie es in eine Funktion ein, wenn Sie es vorziehen, aber es ist nicht sehr kompliziert. Die Lösung ist logisch präzise und effizient.
quelle
In C:
quelle