пример - java check boolean is false




Проверьте, соответствуют ли по крайней мере два из трех логических значений (20)

AC решение.

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

или вы можете предпочесть:

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

Недавно интервьюер задал мне этот вопрос: учитывая три логические переменные a, b и c, верните true, если по крайней мере два из трех являются истинными.

Мое решение:

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

Он сказал, что это можно улучшить и дальше, но как?


В Clojure :

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

Использование:

(at-least 2 true false true)

Вместо того, чтобы писать:

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

Написать:

return someExpression;

Что касается самого выражения, что-то вроде этого:

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

или это (в зависимости от того, что вам легче понять):

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

Он проверяет a и b ровно один раз, и c не более одного раза.

Рекомендации


Вот еще одна реализация, использующая map / reduce. Это хорошо масштабируется до миллиардов булевых © в распределенной среде. Использование MongoDB:

Создание values базы данных булевых:

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

Создание карты, сокращение функций:

Edit : Мне нравится answer CurtainDog о том, что map / reduce применим к общим спискам, поэтому здесь идет функция карты, которая принимает обратный вызов, который определяет, следует ли подсчитывать значение или нет.

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

Запуск карты / уменьшения:

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

Другой пример прямого кода:

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

Очевидно, это не самый краткий код.

добавление

Другая (слегка оптимизированная) версия:

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

Это может работать немного быстрее, предполагая, что сравнение с 0 будет использовать более быстрый (или, возможно, меньше) код, чем сравнение с 2.


Еще один способ сделать это, но не очень хороший:

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

Boolean значения хэш-кода фиксированы в 1231 для true и 1237 для false, поэтому он мог бы использовать <= 3699


Мы можем преобразовать bools в целые числа и выполнить эту легкую проверку:

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

Наиболее очевидный набор улучшений:

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

а потом

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

Но эти улучшения незначительны.


Почему бы не реализовать его буквально? :)

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

В C вы можете просто написать a+b+c >= 2 (или !!a+!!b+!!c >= 2 чтобы быть очень безопасным).

В ответ на сравнение Java-байт-кода TofuBeer , это простой тест производительности:

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

Это выводит на мой компьютер следующее (работает Ubuntu на Intel Core 2 + sun java 1.6.0_15-b03 с VM сервера HotSpot (14.1-b02, смешанный режим)):

Первая и вторая итерации:

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

Позднее итерации:

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

Интересно, что может сделать Java Java, что ухудшает производительность с течением времени (a + b + c> = 2).

И вот что произойдет, если я запустил java с -client 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

Тайна ...

И если я запустил его в GNU Java Interpreter , он будет почти в 100 раз медленнее, но a&&b || b&&c || a&&c a&&b || b&&c || a&&c Затем выигрывает версия a&&b || b&&c || a&&c .

Результаты Tofubeer с последним кодом, работающим под управлением ОС 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

Результаты Paul Wagland с 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

Принимая ответы (пока):

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

и запускать их через декомпилятор (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
}

Вы можете видеть, что?: Одни немного лучше, чем исправленная версия вашего оригинала. Лучшим является тот, который избегает разветвления вообще. Это хорошо с точки зрения меньшего количества инструкций (в большинстве случаев) и лучше для частей предсказания ветвлений процессора, поскольку неправильное предположение в предсказании ветвления может привести к остановке CPU.

Я бы сказал, что самый эффективный из них - тот, что есть у самого лунного тенью. Он использует в среднем наименьшее количество инструкций и уменьшает вероятность наличия киосков конвейера в CPU.

Чтобы быть на 100% уверенным, вам нужно будет узнать стоимость (в цикле процессора) для каждой инструкции, которая, к сожалению, недоступна (вам нужно будет посмотреть источник для горячей точки, а затем спецификации поставщиков процессоров на время принятых для каждой сгенерированной команды).

См. Обновленный ответ Rotsor для анализа кода во время выполнения.


Суммировать. Это называется булевой алгеброй по одной причине:

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

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

Если вы посмотрите на таблицы истинности, вы увидите, что умножение является логическим, а просто добавление - xor.

Чтобы ответить на ваш вопрос:

return (a + b + c) >= 2

Такие вопросы можно решить с помощью карты Карно :

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

из которого вы заключаете, что вам нужна группа для первого ряда и две группы для первой колонки, получая оптимальное решение для полигенных смазок:

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

Это действительно зависит от того, что вы подразумеваете под «улучшением»:

Яснее?

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

Более общий?

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

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

        if(count > x) return true;
    }

    return false;
}

Более масштабируемый?

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

Быстрее?

// Only profiling can answer this.

Какой из них «улучшен» сильно зависит от ситуации.


Я не думаю, что видел это решение:

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

Его преимуществом является то, что как только он достигает числа, которое вы ищете, он ломается. Так что, если это было «по крайней мере 2 из этих 1 000 000 значений истинны», где первые два действительно являются истинными, тогда он должен идти быстрее, чем некоторые из более «нормальных» решений.


В C:

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

В Ruby:

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

Что можно запустить в JRuby на JavaVM. ;-)


Вероятно, он не ищет ничего запутанного, как побитовые операторы сравнения (обычно не свернутые, а с булевыми, крайне странно использовать побитовые операторы) или что-то очень крутое, как преобразование в int и суммирование их.

Самый прямой и естественный способ решить это - это выражение:

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

Положите его в функцию, если хотите, но это не очень сложно. Решение является логически кратким и эффективным.


Самый простой способ (IMO), который не путает и легко читается:

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

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

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

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

Объяснение:

Если a==b , то оба истины или оба являются ложными. Если оба они истинны, мы нашли два наших истинных логических элемента и можем вернуть true (возвращая a ). Если оба они ложны, не может быть двух истинных булевых, даже если c истинно, поэтому мы возвращаем false (путем возврата a ). Это (a==b) ? a часть. Как насчет : c ? Ну, если a==b является ложным, то точно один из a или b должен быть истинным, поэтому мы нашли первое истинное булево значение, и единственное, что осталось, - это если c также верно, поэтому мы возвращаем c как ответ ,





boolean-logic