Prüfen, ob mindestens zwei von drei Booleschen Werten wahr sind

Question

Ein Interviewer hat mir kürzlich folgende Frage gestellt: Geben Sie bei drei booleschen Variablen a, b und c true zurück, wenn mindestens zwei der drei Variablen wahr 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 noch verbessert werden kann, aber wie?

Answer 1

Es kommt wirklich darauf an, was Sie mit "verbessert" meinen:

Deutlicher?

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;
}

Besser skalierbar?

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.

Welche davon "besser" ist, hängt stark von der Situation ab.

Answer 2

Hier ist eine weitere Implementierung mit map/reduce. Diese skaliert gut auf Milliarden von Booleschen © in einer verteilten Umgebung. MongoDB verwenden:

Erstellen einer Datenbank values von Booleschen:

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

Erstellen der Map- und Reduce-Funktionen:

Editar : Ich mag CurtainDog's Antwort über mit map/reduce gelten für generische Listen, so geht hier eine map-Funktion, die einen Callback, der bestimmt, ob ein Wert gezählt werden sollte oder nicht nimmt.

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;
}

Ausführen von map/reduce:

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;
}

Answer 3

Ein weiteres Beispiel für direkten Code:

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

Das ist natürlich 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);

Das könnte etwas schneller gehen, wenn man davon ausgeht, dass der Vergleich gegen 0 schnelleren (oder vielleicht weniger) Code benötigt als der Vergleich gegen 2.

Answer 4

Hier finden Sie die Antworten (bis jetzt):

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 lassen sie durch den Decompiler laufen (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 ?: etwas besser sind als die korrigierte Version Ihres Originals. Am besten ist diejenige, bei der die Verzweigung ganz vermieden wird. Das ist gut im Hinblick auf weniger Anweisungen (in den meisten Fällen) und besser für die Verzweigungsvorhersageteile der CPU, da eine falsche Schätzung bei der Verzweigungsvorhersage zum Abwürgen der CPU führen kann.

Ich würde sagen, die effizienteste ist die von moonshadow insgesamt. Sie verwendet im Durchschnitt die wenigsten Anweisungen und verringert die Gefahr von Pipeline-Störungen in der CPU.

Um 100 % sicher zu sein, müssten Sie die Kosten (in CPU-Zyklen) für jede Anweisung herausfinden, was leider nicht ohne weiteres möglich ist (Sie müssten sich die Quelle für Hotspot und dann die Spezifikationen des CPU-Anbieters für die Zeit ansehen, die für jede generierte Anweisung benötigt wird).

Siehe die aktualisierte Antwort von Rotsor für eine Laufzeitanalyse des Codes.

Answer 5

Die offensichtlichste Reihe von 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));
}

Aber diese Verbesserungen sind geringfügig.