Sprawdź, czy co najmniej dwa z trzech boolanów są prawdziwe


579

Ankieter niedawno zadał mi to pytanie: biorąc pod uwagę trzy zmienne logiczne, a, b i c, zwróć true, jeśli co najmniej dwie z trzech są prawdziwe.

Moje rozwiązanie jest następujące:

boolean atLeastTwo(boolean a, boolean b, boolean c) {
    if ((a && b) || (b && c) || (a && c)) {
        return true;
    }
    else{
        return false;
    }
}

Powiedział, że można to jeszcze poprawić, ale jak?


170
Wstaw instrukcję return.
Finglas,

45
Brzmi jak wywiad „kto ma najwyższe IQ”. Upadłbym
Chris Dutrow,

79
atLeastTwo(iWantYou, iNeedYou, imEverGonnaLoveYou)
Andrew Grimm,

92
Dlaczego ludzie głosują na najbardziej trywialne pytania?
BlueRaja - Danny Pflughoeft

46
Pytania, które są ogólne i łatwe do zrozumienia, zdobywają dużo głosów. Pytania bardzo szczegółowe i techniczne nie.
Jay

Odpowiedzi:


820

Zamiast pisać:

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

Pisać:

return someExpression;

Jeśli chodzi o samo wyrażenie, coś takiego:

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

lub to (w zależności od tego, co łatwiej zrozumieć):

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

Testuje ai bdokładnie raz, a cnajwyżej raz.

Bibliografia


144
+1: cudowne rozwiązanie układanki, ale mam nadzieję, że nie widzimy czegoś takiego w prawdziwym świecie :)
Juliet

124
@Juliet: Nie wiem, myślę, że gdyby był to wymóg w świecie rzeczywistym (z prawdziwymi nazwami zmiennych), czytałby całkiem dobrze. Zastanów się return hasGoodAttendance ? (passedCoursework || passed Exam) : (passedCoursework && passedExam), dla mnie to wygląda dobrze.
Andrzej Doyle,

18
Nie wydaje mi się, aby wyglądało to źle , ale jeśli wymaganie w tej domenie jest rozumiane jako „co najmniej dwa”, myślę, że łatwiej byłoby je odczytać atLeastTwo(hasgoodAttendance, passedCoursework, passedExam). Pomysł „co najmniej 2 boole są prawdziwe” jest na tyle ogólny, że zasługuje na swoją własną funkcję.
Ken

17
@Lese: Zadawanie najbardziej zoptymalizowanego kodu w rozmowach bezpośrednich jest niepraktyczne i śmiem twierdzić, że jest bezużyteczne. Mikrooptymalizacje, gdy są napędzane potrzebą, kierują się wynikami profilowania środowiska wykonawczego, a nie instynktami ludzkimi (o których wiadomo, że są okropne). Z pewnością możesz zapytać rozmówców o proces dalszej optymalizacji; to jest ważniejsze niż sam wynik.
polygenelubricants

17
Operator trójskładnikowy jest powszechnym idiomem, który powinieneś być w stanie przeczytać. Jeśli nie umiesz go przeczytać, powinieneś go przestudiować, aż będziesz mógł. Użycie operatora trójskładnikowego nie jest czymś, co uważam za „sprytne” w sensie uwłaczającym. Ale tak, umieściłbym to jako treść wywołania metody, jeśli często używasz logiki „co najmniej dwóch”.
Stephen P

493

Tylko ze względu na użycie XOR do rozwiązania stosunkowo prostego problemu ...

return a ^ b ? c : a

159
Wow, fajne rozwiązanie. Ale dla mnie jego odwrócona wersja jest łatwiejsza do zrozumienia: a == b? a: c
Rotsor

5
a ^ b? c: a ^ b? c: a ^ b? c: a
alexanderpas

4
Tak, XOR dostaje tak kiepską prasę i rzadko masz szansę z niej skorzystać.
EightyOne Unite

18
@ Stimul8d może dlatego, że dla booleanów jest to to samo, co! =, Ale mniej czytelne? Zrozumienie tego było dla mnie chwilą
eureki

2
Wolę formę czysto binarną: return ((a ^ b) & c) | (a & b). Jest bezgałęziowy (szybszy) i łatwy do odczytania: (a lub b to prawda, a c to prawda) lub (a i b są prawdziwe). Zauważ, że (a | b) i (a ^ b) oba działają z tą formułą.
flanglet

217

Dlaczego nie wdrożyć tego dosłownie? :)

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

W C możesz po prostu pisać a+b+c >= 2(lub !!a+!!b+!!c >= 2być bardzo bezpiecznym).

W odpowiedzi na TofuBeer porównania „s Java kodu bajtowego, o to prosty test wydajności:

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

Spowoduje to wydrukowanie następujących informacji na moim komputerze (z systemem Ubuntu na Intel Core 2 + Sun Java 1.6.0_15-b03 z maszyną wirtualną serwera HotSpot Server (14.1-b02, tryb mieszany)):

Pierwsza i druga iteracja:

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

Późniejsze iteracje:

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

Zastanawiam się, co mogłaby zrobić maszyna wirtualna Java, która z czasem obniża wydajność w przypadku (a + b + c> = 2).

A oto co się stanie, jeśli uruchomię Java z -clientprzełącznikiem VM:

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

Zagadka...

A jeśli uruchomię go w GNU Java Interpreter , robi się prawie 100 razy wolniej, ale wtedy a&&b || b&&c || a&&cwersja wygrywa.

Wyniki Tofubeera z najnowszym kodem z systemem 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

Wyniki od Paula Waglanda z 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

4
a+b+c >= 2: to nie działa z negatywami, prawda? Być może będziesz musiał to zrobić !!a, nie jestem pewien.
polygenelubricants

8
<s> -1. Nigdy nie powinieneś tego robić dla C. Nie wiesz, jaka jest wartość prawdy (równie łatwo może wynosić -1). </s> Właściwie to C99 zawiera w swoim standardzie, że prawda jest zdefiniowana jako 1. Ale Nadal bym tego nie zrobił.
Mark Peters

1
Czy to możliwe, jeśli Twój wkład jest wynikiem operacji logicznych? Czy jest to możliwe w przypadku typu „bool” w C ++?
Rotsor,

2
@Rotsor: Nikt nie powiedział, że dane wejściowe muszą być wynikiem operacji logicznych. Nawet bez negatywów bawisz się ogniem, tak jakbyś zdefiniował go jako 2, twój stan miałby fałszywe alarmy. Ale nie obchodzi mnie to tak bardzo, jak nie podoba mi się pomysł przenikania boolean do arytmetyki. Twoje rozwiązanie Java jest jasne, ponieważ nie opiera się na niuansowych konwersjach typu logicznego na liczbę całkowitą.
Mark Peters

7
Bądź ostrożny z mikrodrukami
BalusC

143

Tego rodzaju pytania można rozwiązać za pomocą mapy Karnaugh :

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

z którego wywnioskujesz, że potrzebujesz grupy dla pierwszego rzędu i dwóch grup dla pierwszej kolumny, uzyskując optymalne rozwiązanie dla wieloskładnikowych środków smarnych:

(C && (A || B)) || (A && B)  <---- first row
       ^
       |
   first column without third case

10
@Justin, mapa Karnaugh zmniejszyła liczbę operacji logicznych z 3 AND i 2 OR do 2 AND i 2 OR. @ Jack, dziękuję za przypomnienie mi o istnieniu mapy Karnaugh.
Tachy

14
+1 za coś nowego. Moja następna funkcjonalna specyfikacja będzie obejmować mapę K, niezależnie od tego, czy jej potrzebuje czy nie.
Justin R.

2
Być może słaba czytelność może zostać zrekompensowana przez (1) odpowiednią tabelę w komentarzu i (2) odpowiedni test jednostkowy ... +1 za coś pożytecznego nauczonego w szkole.
moala

140

Celem powinna być czytelność. Ktoś, kto czyta kod, musi natychmiast zrozumieć twoje zamiary. Oto moje rozwiązanie.

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

return howManyBooleansAreTrue >= 2;

21
Zgadzam się z założeniem, ale (a && b) || (b && c) || (A&&C) jest znacznie bardziej czytelny niż Twoje rozwiązanie IMHO.
Adrian Grigore,

62
Hmm, teraz potrzebuję wersji „dwa z CZTERECH CZĘSTOTLIWOŚCI”… wersja Danatela jest teraz znacznie łatwiejsza.
Arafangion

6
Lub w Scali:Seq(true, true, false).map(if (_) 1 else 0).sum >= 2
retronym

5
@retronym: Hmm, nie. Sposób Java działa dobrze w Scali i jest zarówno bardziej czytelny, jak i bardziej wydajny.
Seun Osewa

134
return (a==b) ? a : c;

Wyjaśnienie:

Jeśli a==b, to oba są prawdziwe lub oba są fałszywe. Jeśli oba są prawdziwe, znaleźliśmy nasze dwa prawdziwe booleany i możemy zwrócić wartość true (przez powrót a). Jeśli oba są fałszywe, nie mogą istnieć dwa prawdziwe booleany, nawet jeśli cjest to prawda, więc zwracamy fałsz (przez powrót a). To jest (a==b) ? aczęść. Co : c? Cóż, jeśli a==bjest fałszywe, to dokładnie jedna z alub bmusi być prawdziwa, więc znaleźliśmy pierwszą prawdziwą wartość logiczną, a jedyną rzeczą, która się liczy, cjest również prawda, więc wrócimy cjako odpowiedź.


8
c nigdy nie jest nawet testowany ... genialny!
CurtainDog

Wykorzystuje przechodnią relację równości i fakt, że wartość logiczna jest albo prawdą, albo fałszem +1
Christophe Roussy

3
Taki elegancki! Musiałem sprawdzić długopisem i papierem, żeby w to uwierzyć :) Chwała panu!
Adrian

3
Myślę o tym, że „jeśli ai bzgadzają się, mają większość głosów, więc idź z tym, co to jest, w przeciwnym razie nie zgadzają się, tak csamo decyduje głosowanie”
Ben Millwood

34

Nie musisz używać zwarć operatorów.

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

Wykonuje tę samą liczbę operacji logicznych co twoja wersja, jednak jest całkowicie bez rozgałęzień.


11
Dlaczego chcesz wymuszać 5 ocen, gdy 1 może to zrobić? W rzeczywistości tak naprawdę nie wykonuje takiej samej liczby operacji logicznych. W rzeczywistości zawsze działałby więcej.
Mark Peters

2
Myślę, że mieszanie arytmetyki binarnej z arytmetyką logiczną to zły pomysł. To jest jak wkręcanie śrub w ścianę za pomocą klucza. Najgorsze jest to, że mają inną semantykę.
Peter Tillemans,

12
@ Mark - może być szybszy ... w zależności od wpływu niepoprawnej prognozy gałęzi na potok procesora. Jednak najlepiej pozostawić takie mikrooptymalizacje kompilatorowi JIT.
Stephen C

4
Dobrze jest zrobić coś takiego w Javie (lub innym języku) ... z kilkoma zastrzeżeniami: 1) musi być szybsza (w tym przypadku, jak sądzę, patrz moja druga odpowiedź) 2) preferowana znacznie szybciej (nie jestem pewien, czy tak jest), 3) co najważniejsze udokumentowane, ponieważ jest „nieparzyste”. O ile służy to celowi i jest udokumentowane, można „łamać reguły”, gdy ma to sens.
TofuBeer

11
@Peter Tillemans Nie ma mieszania z operatorami binarnymi, w Javie są to operatory logiczne.
starblue

27

Oto testowane, ogólne podejście. Nie tak „wydajny” jak większość dotychczas oferowanych rozwiązań, ale przejrzysty, przetestowany, działający i uogólniony.

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

8
Wow, nigdy przedtem nie widziałem w pełni przetestowanej metody.
Rotsor

51
Osobiście uważam ten kod za okropny z wielu powodów. Nie zamierzam głosować negatywnie, ale gdybym kiedykolwiek zobaczył to w kodzie produkcyjnym, przeklinałbym. Niezwykle prosta operacja logiczna nie musi być tak skomplikowana.
CaptainCasey

10
Bardzo chciałbym poznać twoje powody, @CaptainCasey. Myślę, że to całkiem niezły kod. Jest ładna uogólniona funkcja, która jest łatwa do zrozumienia, łatwa do zweryfikowania, a konkretna funkcja, która z niej korzysta, również łatwa do zrozumienia i weryfikacji. W prawdziwym świecie upubliczniłem je i umieściłem w innej klasie; poza tym - chętnie wprowadzę ten kod do produkcji. Och - tak - zmienię nazwę countBooleans () na countTrue ().
Carl Manaster,

5
jeśli nie chodzi o wydajność, to rozwiązanie wydaje mi się prawie idealne: bardzo łatwe do odczytania i rozszerzalne. To jest dokładnie to, do czego są stworzone var-args.
atamanroman

7
Co do cholery, ludzie? Jest to przejrzysty i dobrze przetestowany kod, a jedynym powodem, dla którego wygląda dużo, jest to, że zawiera testy. +++, zagłosowałbym ponownie.
Christoffer Hammarström,

24

Podsumowując. Nazywa się to algebrą boolowską z jakiegoś powodu:

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

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

Jeśli spojrzysz na tabele prawdy, zobaczysz, że mnożenie ma wartość logiczną i po prostu dodawanie jest xor.

Odpowiedzieć na Twoje pytanie:

return (a + b + c) >= 2

2
To moim zdaniem najbardziej eleganckie rozwiązanie.
Torbjørn Kristoffersen

9
Błąd początkujący, boolowska wartość NIE wynosi 0, co nie oznacza, że ​​zawsze jest 1.
tomdemuyt

13
Tyle że znacznik w poście mówi „Java” i nie można napisać „a + b + c”, gdy są one zdefiniowane jako booleany w Javie.
Jay

Do pracy w Javie musiałoby być return ((a?1:0) + (b?1:0) + (c?1:0)) >= 2.
David R Tribble,

Głosowałem za tym, ponieważ myślałem, że to pytanie C ++ ... dlaczego czytam pytania Java? : /
Carlo Wood

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

15

To naprawdę zależy od tego, co rozumiesz przez „ulepszony”:

Jaśniejsze?

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

Bardziej ogólne?

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

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

        if(count > x) return true;
    }

    return false;
}

Bardziej skalowalny?

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

Szybciej?

// Only profiling can answer this.

To, który zostanie „ulepszony”, zależy w dużej mierze od sytuacji.


14

Oto kolejna implementacja korzystająca z mapowania / zmniejszania. To dobrze skaluje się do miliardów wartości logicznych © w środowisku rozproszonym. Za pomocą MongoDB:

Tworzenie bazy danych valueslogów:

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

Tworząc mapę, zmniejsz funkcje:

Edycja : Podoba mi się odpowiedź CurtainDog na temat zastosowania mapowania / zmniejszania do list ogólnych, więc oto funkcja mapy, która pobiera wywołanie zwrotne, które określa, czy wartość powinna zostać policzona, czy nie.

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

Uruchamianie mapy / zmniejszanie:

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: tak bardzo, jak uwielbiam M / R i ujawnienie, które niedawno Google mu to przekazało (nawet jeśli nie jest to jedyny prawdziwy M / R z FP), chciałbym nazwać bullsh! T twoją odpowiedzią. Istnieją miliardy linii kodu wykonujących „rzeczy” w świecie rzeczywistym, w których nie użyto ani jednej linii mapy / redukcji. Ktoś odpowiadając na takie pytanie z tym jest na pewno w mojej książce oznaczone jako: „stara się odtworzyć Smartie” . Nie wspominając o tym, że większość ankieterów nie byłaby w stanie stwierdzić, czy próbujesz z nimi walić, czy nie, ponieważ w rzeczywistości nigdy nie napisali żadnego programu wykorzystującego M / R w swojej karierze.
Składnia T3rr0r

2
@Syntax - Każdy ma prawo do swojej opinii. Moja odpowiedź to tylko jedno podejście do spojrzenia na problem. Jasne, to brzmi przesadnie jak na 3 wartości logiczne, ale to nie znaczy, że staram się być tutaj smarty-spodnie. Jest to powszechne podejście do rozwiązywania problemów, z którego wszyscy korzystają - rozbicie problemu na małe kawałki. Tak działa indukcja matematyczna, tak działa większość algorytmów rekurencyjnych i tak ludzie w ogóle rozwiązują problemy.
Anurag

13

Biorąc odpowiedzi (jak dotąd) tutaj:

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

i uruchomienie ich przez dekompilator (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
}

Widzisz, że?: Te są nieco lepsze niż poprawiona wersja twojego oryginału. Ten, który jest najlepszy, to ten, który całkowicie unika rozgałęzień. Jest to dobre z punktu widzenia mniejszej liczby instrukcji (w większości przypadków) i lepsze w przypadku części procesora przewidujących rozgałęzienia, ponieważ błędne odgadnięcie w przewidywaniu gałęzi może spowodować zablokowanie procesora.

Powiedziałbym, że najbardziej skuteczny jest ten z cienia księżyca. Wykorzystuje średnio najmniej instrukcji i zmniejsza ryzyko utknięcia rurociągu w procesorze.

Aby być w 100% pewnym, musisz znaleźć koszt (w cyklach procesora) dla każdej instrukcji, która niestety nie jest łatwo dostępna (musisz spojrzeć na źródło hotspotu, a następnie specyfikacje dostawców procesora na ten czas pobierane dla każdej wygenerowanej instrukcji).

Zobacz zaktualizowaną odpowiedź Rotsora, aby uzyskać analizę kodu wykonawczego.


5
Patrzysz tylko na kod bajtowy. Z tego co wiesz, JIT weźmie wersję z rozgałęzieniami w kodzie bajtowym i przekształci ją w wersję bez rozgałęzień w kodzie natywnym. Ale można by pomyśleć, że mniej gałęzi w kodzie bajtowym byłoby lepsze.
David Conrad

13

Kolejny przykład kodu bezpośredniego:

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

Oczywiście nie jest to najbardziej zwięzły kod.

Uzupełnienie

Kolejna (nieco zoptymalizowana) wersja tego:

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

Może to działać nieco szybciej, przy założeniu, że porównanie z 0 spowoduje użycie szybszego (lub być może mniejszego) kodu niż porównanie z 2.


+1 @Loadmaster, przepraszam ale się mylisz! To jest najbardziej zwięzła odpowiedź tutaj. (tj. krótko ORAZ jasno wyrażone);)
Ash


@ M.Mimpen: Tylko dla obiektów klasy. W przypadku typów pierwotnych (jak nwyżej) każdy przyzwoity kompilator skompiluje każdą ++operację w jedną instrukcję CPU, zarówno przed, jak i po.
David R Tribble

12

Jeszcze inny sposób na zrobienie tego, ale niezbyt dobry:

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

Wartości Booleanhashcode są ustalone na 1231 dla wartości true i 1237 dla wartości false, więc równie dobrze mogłyby zostać użyte<= 3699


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

12

Najbardziej oczywistym zestawem ulepszeń są:

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

i wtedy

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

Ale te ulepszenia są niewielkie.


10

Nie lubię trójki ( return a ? (b || c) : (b && c);z najwyższej odpowiedzi) i nie sądzę, żeby ktoś o tym wspominał. Jest napisane w ten sposób:

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

8

W Clojure :

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

Stosowanie:

(at-least 2 true false true)

2
+1 Świetna ogólna wersja pokazuje moc Lisps. Dzięki,
dsmith

6

Nie sądzę, że widziałem jeszcze takie rozwiązanie:

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

Jego zaletą jest to, że gdy osiągnie liczbę, której szukasz, pęka. Więc jeśli było to „co najmniej 2 z tych 1 000 000 wartości są prawdziwe”, gdzie dwie pierwsze są rzeczywiście prawdziwe, to powinno pójść szybciej niż niektóre z bardziej „normalnych” rozwiązań.


Prawdopodobnie powinno to być: if (++ counter == howMany) zamiast zwiększania, a następnie sprawdzania osobno.
Joe Enos

2
Lub nawet krócej: if (b && (++ counter == howMany))
Joe Enos

1
Zrobiłbym to boolean ... boolValues, że łatwiej jest zadzwonić, ale nadal ma tablicę
Stephen

Nie jestem na bieżąco na mojej Javie - nie wiedziałem, że istnieje. Niby dziwna składnia, ale jest przydatna - co jakiś czas będę to robił w C # (słowo kluczowe params), a to sprawia, że ​​łatwiej jest wywoływać. Lub, nie wiem o Javie, ale w .NET, tablice i wszystkie kolekcje implementują IEnumerable <T>, więc prawdopodobnie użyłbym dowolnego odpowiednika Javy.
Joe Enos

Jak wypada to w porównaniu z przykładem 2of3? zwrócić? (b || c): (b & c);
Iain Sproat

6

Możemy przekonwertować wartości logiczne na liczby całkowite i wykonać tę łatwą kontrolę:

(int(a) + int(b) + int(c)) >= 2

6

Ponieważ nie określono, jak należy poprawić kod, postaram się ulepszyć kod, czyniąc go bardziej zabawnym. Oto moje rozwiązanie:

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

Jeśli ktoś zastanawia się, czy ten kod działa, oto uproszczenie z wykorzystaniem tej samej logiki:

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; 

}

Można to sprowadzić do następujących elementów:

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

Ale teraz to już nie jest śmieszne.


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

Zbyt wiele sposobów na zrobienie tego ...


3
Wyglądają bardziej jak C #. Należy o tym wspomnieć w odpowiedzi, ponieważ pytanie jest skierowane do Javy :)
BalusC

5

Rozwiązanie AC

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

lub możesz preferować:

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

4
return 1 << $a << $b << $c >= 1 << 2;

Nie widziałem odpowiedzi Suvegi przed postawieniem tego, właściwie to samo.
Kevin

Czy to naprawdę działa? Zakładam, że to PHP, ale nie mam do niego dostępu, ale po prostu zapytam: co się stanie, jeśli $ a wynosi 0?
Mark Edgar

@ Mark To nie działa, jeśli $ a wynosi 0. To był przeoczenie. Dzięki za zwrócenie na to uwagi. :)
Kevin

4

Najprostszy sposób (IMO), który nie jest mylący i łatwy do odczytania:

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

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

Funkcjonalnie jest tak samo. Składniowo ułatwia czytanie osobom nieprzyzwyczajonym do korzystania z operatora warunkowego znaku zapytania. Jestem skłonny założyć się, że więcej osób wie, jak używać operatorów AND i OR, niż liczba osób, które wiedzą, jak używać operatorów warunkowych znaku zapytania. Pierwotne pytanie wymaga „poprawionej odpowiedzi”. Przyjęta odpowiedź upraszcza odpowiedź, ale rodzi bardzo interesujące pytanie o to, co uważa się za poprawę. Czy programujesz dla uniwersalnej czytelności czy dla uproszczenia? Dla mnie jest to poprawa w stosunku do przyjętej odpowiedzi :)
abelito

Preferencje osobiste. Dla mnie znacznie łatwiej jest zrozumieć czystszego operatora trójskładnikowego niż to rozwiązanie.
nico

1
Ach tak, widziałem ten problem i zastanawiałem się, dlaczego nikt inny nie wspomniał o tym rozwiązaniu. Jeśli wypiszesz logikę OP jako algebrę boolowską, otrzymasz A B + A C + B C, która ma pięć operacji. Za pomocą właściwości asocjacyjnej można napisać A * (B + C) + B C, która ma cztery operacje.
Vivian River

To jest to samo, co odpowiedź Jacka (19 czerwca) (C && (A || B)) || (A && B)właśnie zmieniła * nazwy zmiennych ...
user85421

4

Dosłowna interpretacja będzie działać we wszystkich głównych językach:

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

Ale prawdopodobnie ułatwiłbym ludziom czytanie i możliwość rozszerzenia na więcej niż trzy - coś, co wydaje się być zapomniane przez wielu programistów:

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

4

Jako dodatek do doskonałego postu @TofuBeer TofuBeer rozważ odpowiedź @pdox pdox:

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

Rozważ także jego zdemontowaną wersję podaną przez „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

Odpowiedź pdox kompiluje się do mniej bajtowego kodu niż którakolwiek z poprzednich odpowiedzi. Jaki jest czas jego wykonania w porównaniu do innych?

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

Przynajmniej na moim komputerze odpowiedź pdox jest tylko nieco szybsza niż odpowiedź @moonshadow moonshadow, dzięki czemu pdox jest najszybszy ogólnie (na moim laptopie HP / Intel).



3

Prawdopodobnie nie szuka czegoś zwiniętego, jak operatory porównania bitowego (zwykle nie jest to skomplikowane, ale w przypadku logicznych wartości, użycie operatorów bitowych jest niezwykle dziwne) lub czegoś, co jest bardzo okrągłe, jak konwersja na int i ich sumowanie.

Najbardziej bezpośrednim i naturalnym sposobem rozwiązania tego jest takie wyrażenie:

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

Jeśli wolisz, włącz tę funkcję, ale nie jest to zbyt skomplikowane. Rozwiązanie jest logicznie zwięzłe i wydajne.


3

W C:

return !!a + !!b + !!c >= 2;

W rzeczywistości ta odpowiedź jest błędna… powinna wynosić> = 2, ponieważ potrzebujesz co najmniej dwóch prawdziwych boolanów, a nie dokładnie dwóch.
Paul Wagland,

@Paul Wagland: Dzięki za połów.
Matt Joiner,

@ergosys: Czy odpowiedziałem dwukrotnie?
Matt Joiner
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.