Überprüfen Sie, ob mindestens zwei von drei Booleschen Werten wahr sind

579

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?

Benutzer282886
quelle
170
Inline die return-Anweisung.
Finglas
45
Klingt nach einem Interview mit dem Titel "Wer hat den höchsten IQ?". Ich würde scheitern.
Chris Dutrow
79
atLeastTwo(iWantYou, iNeedYou, imEverGonnaLoveYou)
Andrew Grimm
92
Warum stimmen die Leute den trivialsten Fragen zu?
BlueRaja - Danny Pflughoeft
46
Fragen, die allgemein und leicht zu verstehen sind, erhalten viele Stimmen. Fragen, die sehr spezifisch und technisch sind, tun dies nicht.
Jay

Antworten:

820

Anstatt zu schreiben:

if (someExpression) {
    return true;
} else {
    return false;
}

Schreiben:

return someExpression;

Was den Ausdruck selbst betrifft, so etwas:

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    return a ? (b || c) : (b && c);
}

oder dies (je nachdem, was Sie leichter verstehen):

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    return a && (b || c) || (b && c);
}

Es testet aund bgenau einmal undc höchstens einmal.

Verweise

Polygenschmierstoffe
quelle
144
+1: schöne Lösung für das Rätsel, aber hoffentlich sehen wir so etwas in der realen Welt nicht :)
Julia
124
@ Juliet: Ich weiß nicht, ich denke, wenn dies eine reale Anforderung wäre (mit echten Variablennamen), würde es ziemlich gut lesen. Bedenken Sie return hasGoodAttendance ? (passedCoursework || passed Exam) : (passedCoursework && passedExam), das sieht für mich gut aus.
Andrzej Doyle
18
Ich denke nicht, dass das schlecht aussieht , aber wenn die Anforderung in der Domäne als "mindestens zwei" verstanden wird, wäre es meiner Meinung nach einfacher zu lesen atLeastTwo(hasgoodAttendance, passedCoursework, passedExam). Die Idee von "mindestens 2 Bools sind wahr" ist allgemein genug, um ihre eigene Funktion zu verdienen.
Ken
17
@Lese: Die Frage nach dem mikrooptimiertesten Code in persönlichen Interviews ist unpraktisch und ich wage zu sagen, nutzlos. Mikrooptimierungen werden, wenn sie von der Notwendigkeit abhängen, von Ergebnissen der Laufzeitprofilerstellung geleitet, nicht von menschlichen Instinkten (von denen bekannt ist, dass sie schrecklich sind). Sie können die Befragten sicherlich fragen, durch welchen Prozess Sie dies weiter optimieren würden. Das ist wichtiger als das Ergebnis selbst.
Polygenelubricants
17
Der ternäre Operator ist eine gebräuchliche Redewendung, die Sie lesen sollten. Wenn Sie es nicht lesen können, sollten Sie es studieren, bis Sie können. Die Verwendung des ternären Operators halte ich nicht für "klug" im abfälligen Sinne. Aber ja, ich würde dies als Hauptteil eines Methodenaufrufs verwenden, wenn Sie üblicherweise die Logik "mindestens zwei" verwenden.
Stephen P
494

Nur um XOR zur Beantwortung eines relativ einfachen Problems zu verwenden ...

return a ^ b ? c : a
Tim Stone
quelle
160
Wow, coole Lösung. Aber für mich ist die invertierte Version leichter zu verstehen: a == b? a: c
Rotsor
5
a ^ b? c: a ^ b? c: a ^ b? c: a
alexanderpas
4
Yay, .. XOR bekommt so eine schlechte Presse und man bekommt selten die Chance, sie zu benutzen.
EightyOne Unite
19
@ Stimul8d vielleicht, weil es für Boolesche das gleiche ist wie! = Aber weniger lesbar? Das herauszufinden war ein eureka Moment für mich ...
Tikhon Jelvis
2
Ich bevorzuge die rein binäre Form: return ((a ^ b) & c) | (a & b). Es ist verzweigungslos (schneller) und leicht zu lesen: (a oder b ist wahr und c ist wahr) oder (a und b sind beide wahr). Beachten Sie, dass (a | b) und (a ^ b) beide mit dieser Formel arbeiten.
Flanglet
217

Warum nicht wörtlich umsetzen? :) :)

(a?1:0)+(b?1:0)+(c?1:0) >= 2

In C könnte man einfach schreiben a+b+c >= 2(oder !!a+!!b+!!c >= 2um sehr sicher zu sein).

Als Antwort auf TofuBeers Vergleich des Java-Bytecodes ist hier ein einfacher Leistungstest:

class Main
{
    static boolean majorityDEAD(boolean a,boolean b,boolean c)
    {
        return a;
    }

    static boolean majority1(boolean a,boolean b,boolean c)
    {
        return a&&b || b&&c || a&&c;
    }

    static boolean majority2(boolean a,boolean b,boolean c)
    {
        return a ? b||c : b&&c;
    }

    static boolean majority3(boolean a,boolean b,boolean c)
    {
        return a&b | b&c | c&a;
    }

    static boolean majority4(boolean a,boolean b,boolean c)
    {
        return (a?1:0)+(b?1:0)+(c?1:0) >= 2;
    }

    static int loop1(boolean[] data, int i, int sz1, int sz2)
    {
        int sum = 0;
        for(int j=i;j<i+sz1;j++)
        {
            for(int k=j;k<j+sz2;k++)
            {
                sum += majority1(data[i], data[j], data[k])?1:0; 
                sum += majority1(data[i], data[k], data[j])?1:0; 
                sum += majority1(data[j], data[k], data[i])?1:0; 
                sum += majority1(data[j], data[i], data[k])?1:0; 
                sum += majority1(data[k], data[i], data[j])?1:0; 
                sum += majority1(data[k], data[j], data[i])?1:0; 
            }
        }
        return sum;
    }

    static int loop2(boolean[] data, int i, int sz1, int sz2)
    {
        int sum = 0;
        for(int j=i;j<i+sz1;j++)
        {
            for(int k=j;k<j+sz2;k++)
            {
                sum += majority2(data[i], data[j], data[k])?1:0; 
                sum += majority2(data[i], data[k], data[j])?1:0; 
                sum += majority2(data[j], data[k], data[i])?1:0; 
                sum += majority2(data[j], data[i], data[k])?1:0; 
                sum += majority2(data[k], data[i], data[j])?1:0; 
                sum += majority2(data[k], data[j], data[i])?1:0; 
            }
        }
        return sum;
    }

    static int loop3(boolean[] data, int i, int sz1, int sz2)
    {
        int sum = 0;
        for(int j=i;j<i+sz1;j++)
        {
            for(int k=j;k<j+sz2;k++)
            {
                sum += majority3(data[i], data[j], data[k])?1:0; 
                sum += majority3(data[i], data[k], data[j])?1:0; 
                sum += majority3(data[j], data[k], data[i])?1:0; 
                sum += majority3(data[j], data[i], data[k])?1:0; 
                sum += majority3(data[k], data[i], data[j])?1:0; 
                sum += majority3(data[k], data[j], data[i])?1:0; 
            }
        }
        return sum;
    }

    static int loop4(boolean[] data, int i, int sz1, int sz2)
    {
        int sum = 0;
        for(int j=i;j<i+sz1;j++)
        {
            for(int k=j;k<j+sz2;k++)
            {
                sum += majority4(data[i], data[j], data[k])?1:0; 
                sum += majority4(data[i], data[k], data[j])?1:0; 
                sum += majority4(data[j], data[k], data[i])?1:0; 
                sum += majority4(data[j], data[i], data[k])?1:0; 
                sum += majority4(data[k], data[i], data[j])?1:0; 
                sum += majority4(data[k], data[j], data[i])?1:0; 
            }
        }
        return sum;
    }

    static int loopDEAD(boolean[] data, int i, int sz1, int sz2)
    {
        int sum = 0;
        for(int j=i;j<i+sz1;j++)
        {
            for(int k=j;k<j+sz2;k++)
            {
                sum += majorityDEAD(data[i], data[j], data[k])?1:0; 
                sum += majorityDEAD(data[i], data[k], data[j])?1:0; 
                sum += majorityDEAD(data[j], data[k], data[i])?1:0; 
                sum += majorityDEAD(data[j], data[i], data[k])?1:0; 
                sum += majorityDEAD(data[k], data[i], data[j])?1:0; 
                sum += majorityDEAD(data[k], data[j], data[i])?1:0; 
            }
        }
        return sum;
    }

    static void work()
    {
        boolean [] data = new boolean [10000];
        java.util.Random r = new java.util.Random(0);
        for(int i=0;i<data.length;i++)
            data[i] = r.nextInt(2) > 0;
        long t0,t1,t2,t3,t4,tDEAD;
        int sz1 = 100;
        int sz2 = 100;
        int sum = 0;

        t0 = System.currentTimeMillis();

        for(int i=0;i<data.length-sz1-sz2;i++)
            sum += loop1(data, i, sz1, sz2);

        t1 = System.currentTimeMillis();

        for(int i=0;i<data.length-sz1-sz2;i++)
            sum += loop2(data, i, sz1, sz2);

        t2 = System.currentTimeMillis();

        for(int i=0;i<data.length-sz1-sz2;i++)
            sum += loop3(data, i, sz1, sz2);

        t3 = System.currentTimeMillis();

        for(int i=0;i<data.length-sz1-sz2;i++)
            sum += loop4(data, i, sz1, sz2);

        t4 = System.currentTimeMillis();

        for(int i=0;i<data.length-sz1-sz2;i++)
            sum += loopDEAD(data, i, sz1, sz2);

        tDEAD = System.currentTimeMillis();

        System.out.println("a&&b || b&&c || a&&c : " + (t1-t0) + " ms");
        System.out.println("   a ? b||c : b&&c   : " + (t2-t1) + " ms");
        System.out.println("   a&b | b&c | c&a   : " + (t3-t2) + " ms");
        System.out.println("   a + b + c >= 2    : " + (t4-t3) + " ms");
        System.out.println("       DEAD          : " + (tDEAD-t4) + " ms");
        System.out.println("sum: "+sum);
    }

    public static void main(String[] args) throws InterruptedException
    {
        while(true)
        {
            work();
            Thread.sleep(1000);
        }
    }
}

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:

a&&b || b&&c || a&&c : 1740 ms
   a ? b||c : b&&c   : 1690 ms
   a&b | b&c | c&a   : 835 ms
   a + b + c >= 2    : 348 ms
       DEAD          : 169 ms
sum: 1472612418

Spätere Iterationen:

a&&b || b&&c || a&&c : 1638 ms
   a ? b||c : b&&c   : 1612 ms
   a&b | b&c | c&a   : 779 ms
   a + b + c >= 2    : 905 ms
       DEAD          : 221 ms

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 :

a&&b || b&&c || a&&c : 4034 ms
   a ? b||c : b&&c   : 2215 ms
   a&b | b&c | c&a   : 1347 ms
   a + b + c >= 2    : 6589 ms
       DEAD          : 1016 ms

Geheimnis...

Und wenn ich es in GNU Java Interpreter laufen lasse , wird es fast 100-mal langsamer, aber die a&&b || b&&c || a&&cVersion gewinnt dann.

Ergebnisse von Tofubeer mit dem neuesten Code unter OS X:

a&&b || b&&c || a&&c : 1358 ms
   a ? b||c : b&&c   : 1187 ms
   a&b | b&c | c&a   : 410 ms
   a + b + c >= 2    : 602 ms
       DEAD          : 161 ms

Ergebnisse von Paul Wagland mit einem Mac Java 1.6.0_26-b03-383-11A511

a&&b || b&&c || a&&c : 394 ms 
   a ? b||c : b&&c   : 435 ms
   a&b | b&c | c&a   : 420 ms
   a + b + c >= 2    : 640 ms
   a ^ b ? c : a     : 571 ms
   a != b ? c : a    : 487 ms
       DEAD          : 170 ms
Rotsor
quelle
4
a+b+c >= 2: Das funktioniert nicht mit Negativen, oder? Möglicherweise müssen Sie das !!atun, ich bin mir nicht sicher.
Polygenelubricants
8
<s> -1. Sie sollten das niemals für C tun. Sie wissen nicht, was der Wert von true ist (es könnte genauso gut -1 sein). </ S> Eigentlich enthält C99 in seinem Standard, dass true als 1 definiert ist. Aber Ich würde das immer noch nicht tun.
Mark Peters
1
Ist das möglich, wenn Ihre Eingabe das Ergebnis von Booleschen Operationen ist? Und ist das für den Typ "bool" in C ++ möglich?
Rotsor
2
@Rotsor: Niemand hat gesagt, dass die Eingabe das Ergebnis von booleschen Operationen sein muss. Selbst ohne Negative spielen Sie mit Feuer, als ob Sie es als 2 definieren würden, würde Ihr Zustand falsch positive Ergebnisse haben. Aber das interessiert mich nicht so sehr, wie ich die Idee, Boolesche Werte in Arithmetik zu mischen, nicht mag. Ihre Java-Lösung ist insofern klar, als sie nicht auf nuancierten Konvertierungen von booleschen zu ganzzahligen Typen beruht.
Mark Peters
7
Seien Sie vorsichtig mit Mikrobenchmarks: java.sun.com/docs/hotspot/HotSpotFAQ.html#benchmarking_simple
BalusC
143

Diese Art von Fragen kann mit einer Karnaugh-Karte gelöst werden :

      | C | !C
------|---|----
 A  B | 1 | 1 
 A !B | 1 | 0
!A !B | 0 | 0
!A  B | 1 | 0

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:

(C && (A || B)) || (A && B)  <---- first row
       ^
       |
   first column without third case
Jack
quelle
10
@ Justin, Die Karnaugh-Karte hat die Anzahl der logischen Operationen von 3 UNDs und 2 ODERs auf 2 UNDs und 2 ODERs reduziert. @ Jack, danke, dass du mich an die Existenz der Karnaugh Map erinnert hast.
Tachy
14
+1 für etwas Neues. Meine nächste Funktionsspezifikation wird eine K-Map enthalten, ob sie benötigt wird oder nicht.
Justin R.
2
Vielleicht kann die schlechte Lesbarkeit durch (1) die entsprechende Tabelle im Kommentar und (2) den entsprechenden Unit-Test ... +1 für etwas Nützliches in der Schule kompensiert werden.
Moala
140

Lesbarkeit sollte das Ziel sein. Jemand, der den Code liest, muss Ihre Absicht sofort verstehen. Hier ist meine Lösung.

int howManyBooleansAreTrue =
      (a ? 1 : 0)
    + (b ? 1 : 0)
    + (c ? 1 : 0);

return howManyBooleansAreTrue >= 2;
danatel
quelle
21
Ich stimme der Prämisse zu, aber (a && b) || (b && c) || (a && c) ist meiner Meinung nach viel besser lesbar als Ihre Lösung.
Adrian Grigore
62
Hmm, jetzt brauche ich eine "Zwei aus VIER Booleschen" Version ... Danatels Version ist jetzt viel einfacher.
Arafangion
6
Oder in Scala:Seq(true, true, false).map(if (_) 1 else 0).sum >= 2
Retronym
5
@retronym: Hmm, nein. Der Java-Weg funktioniert in Scala einwandfrei und ist sowohl lesbarer als auch effizienter.
Seun Osewa
134
return (a==b) ? a : c;

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ückkehren a). Wenn beide falsch sind, kann es auch dann keine zwei wahren Booleschen Werte geben, wenn cdies wahr ist. Daher geben wir false zurück (indem wir zurückkehren a). Das ist der (a==b) ? aTeil. Was ist mit : c? Nun, wenn a==bes falsch ist, dann ist genau eines von aoder bmuss wahr sein, also haben wir den ersten wahren Booleschen Wert gefunden, und das einzige, was noch zählt, ist, ob ces auch wahr ist, also kehren wir cals Antwort zurück.

Boann
quelle
8
c wird noch nie getestet ... genial!
CurtainDog
Verwendet transitive Gleichheitsrelation und die Tatsache, dass ein Boolescher Wert entweder wahr oder falsch ist +1
Christophe Roussy
3
So elegant! Ich musste mit Stift und Papier nachsehen, um es zu glauben :) Ein großes Lob an Sie, Sir!
Adrian
3
Ich denke darüber nach als "wenn aund bstimme zu, sie haben die Mehrheit der Stimmen, also mach mit, was auch immer es ist, sonst sind sie anderer Meinung, so cist die entscheidende Stimme"
Ben Millwood
34

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.

Mondschatten
quelle
11
Warum sollten Sie 5 Bewertungen erzwingen wollen, wenn 1 dies könnte? In Wahrheit führt es nicht die gleiche Anzahl von Logikoperationen aus. In der Tat würde es immer mehr leisten.
Mark Peters
2
Ich halte es für eine schlechte Idee, binäre Arithmetik und boolesche Arithmetik zu mischen. Es ist, als würde man mit einem Schraubenschlüssel Schrauben in die Wand treiben. Am schlimmsten ist, dass sie unterschiedliche Semantiken haben.
Peter Tillemans
12
@Mark - es könnte schneller sein ... abhängig von der Auswirkung einer falschen Verzweigungsvorhersage auf die CPU-Pipeline. Es ist jedoch am besten, solche Mikrooptimierungen dem JIT-Compiler zu überlassen.
Stephen C
4
Es ist in Ordnung, so etwas in Java (oder einer anderen Sprache) zu tun ... mit ein paar Einschränkungen: 1) Es muss schneller sein (in diesem Fall glaube ich, siehe meine zweite Antwort) 2) vorzuziehen deutlich schneller (nicht sicher, ob es ist), 3) am wichtigsten dokumentiert, da es "ungerade" ist. Solange es einen Zweck erfüllt und dokumentiert ist, ist es in Ordnung, "die Regeln zu brechen", wenn es Sinn macht.
TofuBeer
11
@Peter Tillemans Es gibt keine Vermischung mit binären Operatoren, in Java sind dies boolesche Operatoren.
Starblue
27

Hier ist ein testgetriebener, allgemeiner Ansatz. Nicht so "effizient" wie die meisten bisher angebotenen Lösungen, aber klar, getestet, funktionsfähig und verallgemeinert.

public class CountBooleansTest extends TestCase {
    public void testThreeFalse() throws Exception {
        assertFalse(atLeastTwoOutOfThree(false, false, false));
    }

    public void testThreeTrue() throws Exception {
        assertTrue(atLeastTwoOutOfThree(true, true, true));
    }

    public void testOnes() throws Exception {
        assertFalse(atLeastTwoOutOfThree(true, false, false));
        assertFalse(atLeastTwoOutOfThree(false, true, false));
        assertFalse(atLeastTwoOutOfThree(false, false, true));
    }

    public void testTwos() throws Exception {
        assertTrue(atLeastTwoOutOfThree(false, true, true));
        assertTrue(atLeastTwoOutOfThree(true, false, true));
        assertTrue(atLeastTwoOutOfThree(true, true, false));
    }

    private static boolean atLeastTwoOutOfThree(boolean b, boolean c, boolean d) {
        return countBooleans(b, c, d) >= 2;
    }

    private static int countBooleans(boolean... bs) {
        int count = 0;
        for (boolean b : bs)
            if (b)
                count++;
        return count;
    }
}
Carl Manaster
quelle
8
Wow, ich habe noch nie eine vollständig getestete Methode gesehen, bevor ich diese gesehen habe.
Rotsor
51
Ich persönlich finde diesen Code aus so vielen Gründen schrecklich. Ich werde nicht abstimmen, aber wenn ich das jemals im Produktionscode sehen würde, würde ich fluchen. Eine extrem einfache boolesche Operation muss nicht so kompliziert sein.
CaptainCasey
10
Es würde mich sehr interessieren, Ihre Gründe zu kennen, @CaptainCasey. Ich denke, das ist ziemlich guter Code. Es gibt eine nette verallgemeinerte Funktion, die leicht zu verstehen, leicht zu überprüfen ist, und eine spezielle Funktion, die sie nutzt, die auch leicht zu verstehen und zu verifizieren ist. In der realen Welt würde ich sie öffentlich machen und in eine andere Klasse einordnen. anders als das - ich würde diesen Code gerne in Produktion bringen. Oh - ja - ich würde countBooleans () in countTrue () umbenennen.
Carl Manaster
5
Wenn es nicht um Leistung geht, sieht diese Lösung für mich nahezu perfekt aus: sehr einfach zu lesen und erweiterbar. Genau dafür sind var-args gemacht.
Atamanroman
7
Was zur Hölle, Leute? Dies ist klarer und gut getesteter Code, und der einzige Grund, warum es viel aussieht, ist, dass es die Tests enthält. A +++ würde wieder upvoten.
Christoffer Hammarström
24

Fass es zusammen. Es heißt Boolesche Algebra aus einem Grund:

  0 x 0 = 0
  1 x 0 = 0
  1 x 1 = 1

  0 + 0 = 0
  1 + 0 = 1
  1 + 1 = 0 (+ carry)

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:

return (a + b + c) >= 2
memet
quelle
2
Dies ist meiner Meinung nach die eleganteste Lösung.
Torbjørn Kristoffersen
9
Rookie Fehler, ein boolescher Wert ist NICHT 0, das heißt nicht, es ist immer 1.
Tomdemuyt
13
Außer dass das Tag im Beitrag "Java" sagt und Sie nicht "a + b + c" schreiben können, wenn sie in Java als Boolesche Werte definiert sind.
Jay
Um in Java zu arbeiten, müsste es sein return ((a?1:0) + (b?1:0) + (c?1:0)) >= 2.
David R Tribble
Duh, ich habe dafür gestimmt, weil ich dachte, es sei eine C ++ - Frage ... warum lese ich Java-Fragen? : /
Carlo Wood
15
boolean atLeastTwo(boolean a, boolean b, boolean c) 
{
  return ((a && b) || (b && c) || (a && c));
}
Malu
quelle
15

Es kommt wirklich darauf an, was Sie unter "verbessert" verstehen:

Klarer?

boolean twoOrMoreAreTrue(boolean a, boolean b, boolean c)
{
    return (a && b) || (a && c) || (b && c);
}

Terser?

boolean moreThanTwo(boolean a, boolean b, boolean c)
{
    return a == b ? a : c;
}

Allgemeiner?

boolean moreThanXTrue(int x, boolean[] bs)
{
    int count = 0;

    for(boolean b : bs)
    {
        count += b ? 1 : 0;

        if(count > x) return true;
    }

    return false;
}

Skalierbarer?

boolean moreThanXTrue(int x, boolean[] bs)
{
    int count = 0;

    for(int i < 0; i < bs.length; i++)
    {
        count += bs[i] ? 1 : 0;

        if(count > x) return true;

        int needed = x - count;
        int remaining = bs.length - i;

        if(needed >= remaining) return false;
    }

    return false;
}

Schneller?

// Only profiling can answer this.

Welches "verbessert" wird, hängt stark von der Situation ab.

kerkeslager
quelle
14

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 valuesmit Booleschen Werten:

db.values.insert({value: true});
db.values.insert({value: false});
db.values.insert({value: true});

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.

var mapper = function(shouldInclude) {
    return function() {
        emit(null, shouldInclude(this) ? 1 : 0);
    };
}

var reducer = function(key, values) {
    var sum = 0;
    for(var i = 0; i < values.length; i++) {
        sum += values[i];
    }
    return sum;
}

Laufende Karte / Reduzieren:

var result = db.values.mapReduce(mapper(isTrue), reducer).result;

containsMinimum(2, result); // true
containsMinimum(1, result); // false


function isTrue(object) {
    return object.value == true;
}

function containsMinimum(count, resultDoc) {
    var record = db[resultDoc].find().next();
    return record.value >= count;
}
Anurag
quelle
@Anurag: So sehr ich M / R und die Belichtung, die Google kürzlich gegeben hat, liebe (auch wenn es nicht das einzig wahre M / R von FP ist), würde ich Ihre Antwort eher als Bullsh! T bezeichnen. Es gibt Milliarden und Abermilliarden Codezeilen, die Real-World [TM] "Zeug" ausführen, bei dem keine einzige Zeile der Karte / Verkleinerung verwendet wird. Jemand eine solche Frage mit der Beantwortung dieser ist auf jeden Fall in meinem Buch markiert als: „Versuch , die smartie zu spielen“ . Ganz zu schweigen davon, dass die meisten Interviewer nicht sagen können, ob Sie versuchen, sie zu bescheißen oder nicht, weil sie in ihrer Karriere tatsächlich nie ein einziges Programm mit M / R geschrieben haben.
SyntaxT3rr0r
2
@ Syntax - Jeder hat ein Recht auf seine Meinung. Meine Antwort ist nur ein weiterer Ansatz, um das Problem zu betrachten. Sicher, es klingt übertrieben für 3 Boolesche Werte, aber das bedeutet nicht, dass ich versuche, hier die Smarty-Pants zu sein. Dies ist ein gängiger Ansatz zur Problemlösung, den jeder verwendet - zerlegen Sie das Problem in kleine Teile. So funktioniert mathematische Induktion, so funktionieren die meisten rekursiven Algorithmen und so lösen Menschen Probleme im Allgemeinen.
Anurag
13

Nehmen Sie die Antworten (bisher) hier:

public class X
{
    static boolean a(final boolean a, final boolean b, final boolean c)
    {
    return ((a && b) || (b && c) || (a && c));
    }

    static boolean b(final boolean a, final boolean b, final boolean c)
    {
    return a ? (b || c) : (b && c);
    }

    static boolean c(final boolean a, final boolean b, final boolean c)
    {
    return ((a & b) | (b & c) | (c & a));
    }

    static boolean d(final boolean a, final boolean b, final boolean c)
    {
    return ((a?1:0)+(b?1:0)+(c?1:0) >= 2);
    }
}

und sie durch den Dekompiler laufen lassen (javap -c X> results.txt):

Compiled from "X.java"
public class X extends java.lang.Object{
public X();
  Code:
   0:   aload_0
   1:   invokespecial   #1; //Method java/lang/Object."<init>":()V
   4:   return

static boolean a(boolean, boolean, boolean);
  Code:
   0:   iload_0
   1:   ifeq    8
   4:   iload_1
   5:   ifne    24
   8:   iload_1
   9:   ifeq    16
   12:  iload_2
   13:  ifne    24
   16:  iload_0
   17:  ifeq    28
   20:  iload_2
   21:  ifeq    28
   24:  iconst_1
   25:  goto    29
   28:  iconst_0
   29:  ireturn

static boolean b(boolean, boolean, boolean);
  Code:
   0:   iload_0
   1:   ifeq    20
   4:   iload_1
   5:   ifne    12
   8:   iload_2
   9:   ifeq    16
   12:  iconst_1
   13:  goto    33
   16:  iconst_0
   17:  goto    33
   20:  iload_1
   21:  ifeq    32
   24:  iload_2
   25:  ifeq    32
   28:  iconst_1
   29:  goto    33
   32:  iconst_0
   33:  ireturn

static boolean c(boolean, boolean, boolean);
  Code:
   0:   iload_0
   1:   iload_1
   2:   iand
   3:   iload_1
   4:   iload_2
   5:   iand
   6:   ior
   7:   iload_2
   8:   iload_0
   9:   iand
   10:  ior
   11:  ireturn

static boolean d(boolean, boolean, boolean);
  Code:
   0:   iload_0
   1:   ifeq    8
   4:   iconst_1
   5:   goto    9
   8:   iconst_0
   9:   iload_1
   10:  ifeq    17
   13:  iconst_1
   14:  goto    18
   17:  iconst_0
   18:  iadd
   19:  iload_2
   20:  ifeq    27
   23:  iconst_1
   24:  goto    28
   27:  iconst_0
   28:  iadd
   29:  iconst_2
   30:  if_icmplt   37
   33:  iconst_1
   34:  goto    38
   37:  iconst_0
   38:  ireturn
}

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.

TofuBeer
quelle
5
Sie sehen nur den Bytecode. Nach allem, was Sie wissen, nimmt die JIT eine Version mit Verzweigungen im Bytecode und wandelt sie in eine Version ohne Verzweigungen im nativen Code um. Aber man würde eher denken, dass weniger Zweige im Bytecode besser wären.
David Conrad
13

Ein weiteres Beispiel für direkten Code:

int  n = 0;
if (a) n++;
if (b) n++;
if (c) n++;
return (n >= 2);

Es ist offensichtlich nicht der prägnanteste Code.

Nachtrag

Eine andere (leicht optimierte) Version davon:

int  n = -2;
if (a) n++;
if (b) n++;
if (c) n++;
return (n >= 0);

Dies läuft möglicherweise etwas schneller, vorausgesetzt, der Vergleich mit 0 verwendet schnelleren (oder möglicherweise weniger) Code als der Vergleich mit 2.

David R Tribble
quelle
+1 @Loadmaster, tut mir leid, aber du liegst falsch! Dies ist hier die prägnanteste Antwort. (dh kurz UND klar ausgedrückt);)
Ash
Mikrooptimierung: ++nist schneller als n++ weil Sie vor dem Inkrementieren eine weitere Kopie erstellen müssen .
M. Mimpen
@ M.Mimpen: Nur für Klassenobjekte. Bei primitiven Typen (wie noben) kompiliert jeder anständige Compiler jede ++Operation in einen einzelnen CPU-Befehl, egal ob vor oder nach dem Vorgang.
David R Tribble
12

Noch ein anderer Weg, aber kein sehr guter:

return (Boolean.valueOf(a).hashCode() + Boolean.valueOf(b).hashCode() + Boolean.valueOf(c).hashCode()) < 3705);

Die BooleanHashcode-Werte sind für true auf 1231 und für false auf 1237 festgelegt und könnten daher ebenfalls verwendet werden<= 3699

barrowc
quelle
1
oder (a? 1: 0) + (b? 1: 0) + (c? 1: 0)> = 2
Peter Lawrey
12

Die offensichtlichsten Verbesserungen sind:

// There is no point in an else if you already returned.
boolean atLeastTwo(boolean a, boolean b, boolean c) {
    if ((a && b) || (b && c) || (a && c)) {
        return true;
    }
    return false;
}

und dann

// There is no point in an if(true) return true otherwise return false.
boolean atLeastTwo(boolean a, boolean b, boolean c) {
    return ((a && b) || (b && c) || (a && c));
}

Diese Verbesserungen sind jedoch geringfügig.

TofuBeer
quelle
10

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:

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    if (a) {
        return b||c;
    } 
    else {
        return b&&C;
    }
Roman A. Taycher
quelle
8

In Clojure :

(defn at-least [n & bools]
  (>= (count (filter true? bools)) n)

Verwendungszweck:

(at-least 2 true false true)
Vagif Verdi
quelle
2
+1 Große generische Version zeigt die Kraft der Lisps. Danke,
Dsmith
6

Ich glaube, ich habe diese Lösung noch nicht gesehen:

boolean atLeast(int howMany, boolean[] boolValues) {
  // check params for valid values

  int counter = 0;
  for (boolean b : boolValues) {
    if (b) {
      counter++;

      if (counter == howMany) {
        return true;
      }
    }
  }
  return false;
}

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.

Joe Enos
quelle
Das sollte wahrscheinlich sein: if (++ counter == howMany) anstatt zu erhöhen und dann separat zu prüfen.
Joe Enos
2
Oder noch kürzer: if (b && (++ counter == howMany))
Joe Enos
1
Ich würde es tun boolean ... boolValues, es ist einfacher anzurufen, nimmt aber immer noch ein Array
Stephen
Ich bin auf meinem Java nicht auf dem neuesten Stand - wusste nicht, dass es das gibt. Eine seltsame Syntax, aber sie ist nützlich - hin und wieder mache ich das in C # (params keyword), und es macht die Sache schöner, sie aufzurufen. Oder ich weiß nichts über Java, aber in .NET implementieren Arrays und alle Sammlungen IEnumerable <T>, sodass ich wahrscheinlich das Äquivalent von Java verwenden würde.
Joe Enos
Wie ist die Leistung dieses Beispiels im Vergleich zum 2of3-Beispiel? ein zurückgeben? (b || c): (b && c);
Iain Sproat
6

Wir können die Bools in ganze Zahlen konvertieren und diese einfache Überprüfung durchführen:

(int(a) + int(b) + int(c)) >= 2
Weinstock
quelle
6

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:

boolean atLeastTwo(boolean t, boolean f, boolean True) {
    boolean False = True;
    if ((t || f) && (True || False)) 
        return "answer" != "42";
    if (t && f) 
        return !"France".contains("Paris");
    if (False == True) 
        return true == false;
    return Math.random() > 0.5;
}

Falls sich jemand fragt, ob dieser Code funktioniert, finden Sie hier eine Vereinfachung mit derselben Logik:

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    if ((a || b) && (c)) 
        return true;
    if (a && b) 
        return true;
    if (true) 
        return false;
    // The last line is a red herring, as it will never be reached:
    return Math.random() > 0.5; 

}}

Dies kann weiter auf Folgendes reduziert werden:

return ((a || b) && (c)) || (a && b);

Aber jetzt ist es nicht mehr lustig.

Bruce Attah
quelle
5
Function ReturnTrueIfTwoIsTrue(bool val1, val2, val3))
{
     return (System.Convert.ToInt16(val1) +
             System.Convert.ToInt16(val2) +
             System.Convert.ToInt16(val3)) > 1;
}

Zu viele Möglichkeiten, dies zu tun ...

Duby
quelle
3
Sieht eher aus wie C #. Dies sollte als solches in der Antwort erwähnt werden, da die Frage auf Java ausgerichtet ist :)
BalusC
5

AC-Lösung.

int two(int a, int b, int c) {
  return !a + !b + !c < 2;
}

oder Sie bevorzugen vielleicht:

int two(int a, int b, int c) {
  return !!a + !!b + !!c >= 2;
}
Mark Edgar
quelle
4
return 1 << $a << $b << $c >= 1 << 2;
Kevin
quelle
Ich habe Suvegas Antwort nicht gesehen, bevor ich sie gestellt habe, so ziemlich das Gleiche.
Kevin
Funktioniert das wirklich? Ich gehe davon aus, dass dies PHP ist, aber ich habe keinen Zugriff darauf, aber ich werde Sie nur fragen: Was passiert, wenn $ a 0 ist?
Mark Edgar
@Mark Es funktioniert eigentlich nicht, wenn $ a 0 ist. Das war ein Versehen. Vielen Dank für den Hinweis. :)
Kevin
4

Der einfachste Weg (IMO), der nicht verwirrend und leicht zu lesen ist:

// Three booleans, check if two or more are true

return ( a && ( b || c ) ) || ( b && c );
abelito
quelle
Funktionell ist es das gleiche. Syntaktisch erleichtert es das Lesen für diejenigen, die nicht an die Verwendung des Bedingungsoperators für Fragezeichen gewöhnt sind. Ich bin bereit zu wetten, dass mehr Leute wissen, wie man UND- und ODER-Operatoren verwendet, als die Anzahl der Leute, die wissen, wie man Fragezeichen-bedingte Operatoren verwendet. Die ursprüngliche Frage fordert eine "verbesserte Antwort". Die akzeptierte Antwort vereinfacht die Antwort, wirft jedoch eine sehr interessante Frage auf, was man als Verbesserung betrachtet. Programmieren Sie für universelle Lesbarkeit oder zur Vereinfachung? Für mich ist dies eine Verbesserung gegenüber der akzeptierten Antwort :)
abelito
Persönliche Vorlieben. Für mich ist es viel einfacher, den saubereren ternären Operator zu verstehen als diese Lösung.
Nico
1
Ah ja, ich habe dieses Problem gesehen und mich gefragt, warum sonst niemand diese Lösung erwähnt hat. Wenn Sie die Logik des OP als boolesche Algebra schreiben, erhalten Sie A B + A C + B C, das fünf Operationen hat. Mit der assoziativen Eigenschaft können Sie A * (B + C) + B C schreiben , das vier Operationen hat.
Vivian River
Es ist das gleiche wie Jacks Antwort (19. Juni) hat (C && (A || B)) || (A && B)gerade die * Variablennamen geändert ...
user85421
4

Eine wörtliche Interpretation funktioniert in allen wichtigen Sprachen:

return (a ? 1:0) + (b ? 1:0) + (c ? 1:0) >= 2;

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:

boolean testBooleans(Array bools)
{
     int minTrue = ceil(bools.length * .5);
     int trueCount = 0;

     for(int i = 0; i < bools.length; i++)
     {
          if(bools[i])
          {
               trueCount++;
          }
     }
     return trueCount >= minTrue;
}
Blakecallens
quelle
4

Betrachten Sie als Ergänzung zu @TofuBeer TofuBeers ausgezeichnetem Beitrag die Antwort von @pdox pdox:

static boolean five(final boolean a, final boolean b, final boolean c)
{
    return a == b ? a : c;
}

Betrachten Sie auch die zerlegte Version von "javap -c":

static boolean five(boolean, boolean, boolean);
  Code:
    0:    iload_0
    1:    iload_1
    2:    if_icmpne    9
    5:    iload_0
    6:    goto    10
    9:    iload_2
   10:    ireturn

Die Antwort von pdox wird mit weniger Bytecode kompiliert als jede der vorherigen Antworten. Wie ist die Ausführungszeit im Vergleich zu den anderen?

one                5242 ms
two                6318 ms
three (moonshadow) 3806 ms
four               7192 ms
five  (pdox)       3650 ms

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).

Rex Barzee
quelle
3

In Ruby:

[a, b, c].count { |x| x } >= 2

Welches könnte in JRuby auf der JavaVM ausgeführt werden. ;-);

user373826
quelle
3

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:

a ? (b || c): (b && c)

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.

stinky472
quelle
3

In C:

return !!a + !!b + !!c >= 2;
Matt Joiner
quelle
Eigentlich ist diese Antwort falsch… sie sollte> = 2 sein, da Sie mindestens zwei echte Boolesche Werte benötigen, nicht genau zwei.
Paul Wagland
@ Paul Wagland: Danke für den Fang.
Matt Joiner
@ergosys: Wth ich zweimal geantwortet habe?
Matt Joiner