java - exemple - variable booléenne excel




Vérifiez si au moins deux booléens sur trois sont vrais (20)

À Clojure :

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

Usage:

(at-least 2 true false true)

Un intervieweur m'a récemment posé cette question: étant donné trois variables booléennes, a, b et c, retourner vrai si au moins deux des trois sont vraies.

Ma solution suit:

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

Il a dit que cela peut être amélioré, mais comment?


Ce genre de questions peut être résolu avec une carte de Karnaugh :

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

d'où vous déduisez que vous avez besoin d'un groupe pour la première rangée et deux groupes pour la première colonne, en obtenant la solution optimale de polygenelubricants:

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

Comme il n'a pas été précisé comment le code devrait être amélioré, je m'efforcerai d'améliorer le code en le rendant plus amusant. Voici ma solution:

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

Au cas où quelqu'un se demanderait si ce code fonctionne, voici une simplification utilisant la même logique:

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; 

}

Cela peut être réduit plus loin à ce qui suit:

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

Mais maintenant ce n'est plus drôle.


Encore une autre façon de le faire mais pas très bien:

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

Les valeurs de hashcode Boolean sont fixées à 1231 pour true et 1237 pour false, ce qui aurait également permis d'utiliser <= 3699


Je ne pense pas avoir déjà vu cette solution:

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

Son avantage est qu'une fois qu'il atteint le nombre que vous cherchez, il casse. Ainsi, si «au moins 2 des 1 000 000 de ces valeurs sont vraies», alors que les deux premières sont vraies, elles devraient aller plus vite que certaines des solutions les plus «normales».


Juste pour utiliser XOR pour répondre à un problème relativement simple ...

return a ^ b ? c : a

La lisibilité devrait être l'objectif. Quelqu'un qui lit le code doit comprendre votre intention immédiatement. Alors voici ma solution.

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

return howManyBooleansAreTrue >= 2;

Nous pouvons convertir les bools en entiers et effectuer cette vérification facile:

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

Pourquoi ne pas l'implémenter littéralement? :)

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

En C, vous pouvez simplement écrire a+b+c >= 2 (ou !!a+!!b+!!c >= 2 pour être très sûr).

En réponse à la comparaison de java bytecode par TofuBeer , voici un test de performance simple:

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

Cela imprime les éléments suivants sur ma machine (exécutant Ubuntu sur Intel Core 2 + sun java 1.6.0_15-b03 avec HotSpot Server VM (14.1-b02, mode mixte)):

Première et deuxième itérations:

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

Itérations ultérieures:

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

Je me demande ce que java VM pourrait faire pour dégrader les performances dans le temps pour (a + b + c> = 2) cas.

Et voici ce qui se passe si je lance java avec un -client VM -client :

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

Mystère...

Et si je le lance dans GNU Java Interpreter , il devient presque 100 fois plus lent, mais le & a&&b || b&&c || a&&c a&&b || b&&c || a&&c a&&b || b&&c || a&&c version a&&b || b&&c || a&&c gagne alors.

Résultats de Tofubeer avec le dernier code exécutant 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

Résultats de Paul Wagland avec un 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

Prenant les réponses (jusqu'à présent) ici:

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

et en les exécutant dans le décompilateur (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
}

Vous pouvez voir que les?: Ones sont légèrement mieux que la version corrigée de votre original. Celui qui est le meilleur est celui qui évite complètement la ramification. C'est bien du point de vue des instructions moins nombreuses (dans la plupart des cas) et mieux pour les parties de prédiction de branchement de la CPU, car une mauvaise estimation dans la prédiction de branchement peut provoquer un blocage du CPU.

Je dirais que le plus efficace est celui de Moonshadow dans son ensemble. Il utilise le plus petit nombre d'instructions en moyenne et réduit les risques de blocage de pipeline dans le processeur.

Pour être sûr à 100% que vous auriez besoin de connaître le coût (en cycles CPU) pour chaque instruction, ce qui, malheureusement, n'est pas facilement disponible (vous devez regarder la source pour hotspot puis les spécifications des vendeurs CPU pour le moment pris pour chaque instruction générée).

Voir la réponse mise à jour par Rotsor pour une analyse du code à l'exécution.


Solution CA

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

ou vous pouvez préférer:

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

Un autre exemple de code direct:

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

Ce n'est pas le code le plus succinct, évidemment.

Addenda

Une autre version (légèrement optimisée) de ceci:

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

Cela pourrait s'exécuter légèrement plus rapidement, en supposant que la comparaison avec 0 utilisera un code plus rapide (ou peut-être moins) que la comparaison avec 2.


Voici une autre implémentation utilisant map / reduce. Cela correspond bien à des milliards de booléens © dans un environnement distribué. Utiliser MongoDB:

Création d'une base de données de values de booléens:

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

Créer la carte, réduire les fonctions:

Edit : J'aime CurtainDog answer CurtainDog answer propos de l'application de map / reduce aux listes génériques, alors voici une fonction map qui prend un callback qui détermine si une valeur doit être comptée ou non.

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

Carte en cours d'exécution / réduire:

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

Vous n'avez pas besoin d'utiliser les formes de court-circuit des opérateurs.

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

Ceci effectue le même nombre d'opérations logiques que votre version, mais est complètement dépourvu de branchement.


As an addition to @TofuBeer TofuBeer's excellent post, consider @pdox pdox's answer:

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

Consider also its disassembled version as given by "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

pdox's answer compiles to less byte code than any of the previous answers. How does its execution time compare to the others?

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

At least on my computer, pdox's answer is just slightly faster than @moonshadow moonshadow's answer, making pdox's the fastest overall (on my HP/Intel laptop).


He's probably not looking for anything convoluted like bitwise comparison operators (not normally convoluted but with booleans, it's extremely odd to use bitwise operators) or something that is very roundabout like converting to int and summing them up.

The most direct and natural way to solve this is with an expression like this:

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

Put it in a function if you prefer, but it's not very complicated. The solution is logically concise and efficient.


In Ruby:

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

Which could be run in JRuby on the JavaVM. ;-)


The simplest way (IMO) that is not confusing and easy to read:

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

Explication:

Si a==b , alors les deux sont vrais ou les deux sont faux. Si les deux sont vrais, nous avons trouvé nos deux vrais booléens, et pouvons retourner vrai (en retournant a ). Si les deux sont faux, il ne peut y avoir deux vrais booléens, même si c est vrai, donc nous retournons faux (en retournant a ). C'est le (a==b) ? a (a==b) ? a partie. Qu'en est-il de : c ? Eh bien, si a==b est faux, alors exactement un de a ou b doit être vrai, donc nous avons trouvé le premier vrai booléen, et la seule chose qui compte est que si c est aussi vrai, alors nous renvoyons c comme réponse .







boolean-logic