Проверьте, верно ли хотя бы два из трех логических значений

Question

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

Мое решение следующее:

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

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

Answer 1

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

Более ясным?

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

Терсером?

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

Более общим?*

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

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.

Какая из них "улучшена", сильно зависит от ситуации.

Answer 2

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

Создание базы данных values логических значений:

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

Создание карты, уменьшение функций:

Редактировать : мне нравится CurtainDog ответ о том, что map / lower применяется к универсальным спискам, поэтому здесь идет функция map, которая принимает обратный вызов, который определяет, значение должно быть посчитано или нет.

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

Answer 3

Взяв ответы (пока) здесь:

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
}

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

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

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

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

Answer 4

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

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.

Answer 5

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

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

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

Answer 6

Еще один способ сделать это, но не очень удачный:

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

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

Answer 7

Мне не нравится троичный (return a ? (b || c) : (b && c); из верхнего ответа), и я не думаю, что видел, чтобы кто-то упоминал об этомЭто написано так:

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

Answer 8

В Clojure :

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

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

(at-least 2 true false true)

Answer 9

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

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

В случае, если кому-то интересно, работает ли этот код, вот упрощение с использованием той же логики:

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; 

}

Это можно закипетьдалее к следующему:

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

Но теперь это уже не смешно.

Answer 10

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

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