logicos - metodo boolean java

Comprueba si al menos dos de cada tres booleanos son verdaderos

Question

Un entrevistador recientemente me hizo esta pregunta: dadas tres variables booleanas, a, b, yc, devuelve verdadero si al menos dos de los tres son verdaderos

Mi solución sigue:

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

Dijo que esto se puede mejorar aún más, pero ¿cómo?

Answer 1

¿Por qué no implementarlo literalmente? :)

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

En C, simplemente puedes escribir a+b+c >= 2 (o !!a+!!b+!!c >= 2 para ser muy seguro).

En respuesta a la comparación de TofuBeer del código de bytes de Java, aquí hay una prueba de rendimiento 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);
}
}
}

Esto imprime lo siguiente en mi máquina (ejecutando Ubuntu en Intel Core 2 + sun java 1.6.0_15-b03 con HotSpot Server VM (14.1-b02, modo mixto)):

Primera y segunda iteraciones:

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

Iteraciones posteriores:

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

Me pregunto, ¿qué podría hacer Java VM que degrada el rendimiento con el tiempo para (a + b + c> = 2) caso.

Y esto es lo que sucede si ejecuto java con un -client VM de -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

Misterio...

Y si lo ejecuto en GNU Java Interpreter , se vuelve casi 100 veces más lento, pero a&&b || b&&c || a&&c a&&b || b&&c || a&&c a&&b || b&&c || a&&c versión de a&&b || b&&c || a&&c gana entonces.

Resultados de Tofubeer con el último código que ejecuta 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

Resultados de Paul Wagland con una 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

Answer 2

Añádelo. Se llama álgebra booleana por una razón:

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

Si miras las tablas de verdad allí, puedes ver que la multiplicación es booleana y, simplemente, la suma es xor.

Para responder tu pregunta:

return (a + b + c) >= 2

Answer 3

Aquí hay otra implementación usando map / reduce. Esto se adapta bien a miles de millones de booleanos ^© en un entorno distribuido. Utilizando MongoDB:

Creando una base de datos de values booleanos:

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

Creando el mapa, reducir funciones:

Edición : Me gusta CurtainDog answer CurtainDog acerca de que map / reduce se aplique a listas genéricas, por lo que aquí va una función de mapa que toma una devolución de llamada que determina si un valor debe contarse o no.

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

Mapa de ejecución / reducir:

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 4

Aquí hay un enfoque general basado en pruebas. No es tan "eficiente" como la mayoría de las soluciones ofrecidas hasta ahora, pero es claro, probado, funcional y generalizado.

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

Answer 5

En Clojure :

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

Uso:

(at-least 2 true false true)

Answer 6

En lugar de escribir:

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

Escribir:

return someExpression;

En cuanto a la expresión en sí, algo como esto:

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

o esto (lo que encuentre más fácil de entender):

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

Prueba a y b exactamente una vez, c como máximo una vez.

Referencias

• JLS 15.25 Operador Condicional? :

Answer 7

Este tipo de preguntas se pueden resolver con un Mapa de Karnaugh :

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

de lo que deduce que necesita un grupo para la primera fila y dos grupos para la primera columna, obteniendo la solución óptima de poligénelubricantes:

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

Answer 8

La legibilidad debe ser el objetivo. Alguien que lea el código debe entender su intención de inmediato. Así que aquí está mi solución.

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

Answer 9

Las mejoras más obvias son:

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

y entonces

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

Pero esas mejoras son menores.

Answer 10

No creo que haya visto esta solución todavía:

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

Su ventaja es que una vez que alcanza el número que estás buscando, se rompe. Entonces, si esto fue "al menos 2 de estos 1,000,000 valores son verdaderos" donde los dos primeros son realmente verdaderos, entonces debería ir más rápido que algunas de las soluciones más "normales".

Answer 11

No es necesario utilizar las formas de cortocircuito de los operadores.

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

Esto realiza el mismo número de operaciones lógicas que su versión, sin embargo, no tiene sucursales.

Answer 12

No me gusta el ternario ( return a ? (b || c) : (b && c); de la respuesta superior), y no creo que haya visto a nadie mencionarlo. Está escrito así:

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

Answer 13

Otra forma de hacer esto, pero no muy buena:

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

Los valores de código hash Boolean se fijan en 1231 para true y 1237 para false, por lo que igualmente podrían haber usado <= 3699

Answer 14

Otro ejemplo de código directo:

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

No es el código más conciso, obviamente.

Apéndice

Otra versión (ligeramente optimizada) de esto:

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

Esto podría ejecutarse un poco más rápido, suponiendo que la comparación con 0 utilizará un código más rápido (o quizás menos) que la comparación con 2.

Answer 15

Podemos convertir los bools en enteros y realizar esta sencilla comprobación:

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

Answer 16

Realmente depende de lo que quieras decir con "mejorado":

Más claro?

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

¿Mas general?

boolean moreThanXTrue(int x, boolean[] bs)
{
int count = 0;
for(boolean b : bs)
{
count += b ? 1 : 0;
if(count > x) return true;
}
return false;
}

¿Más escalable?

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

¿Más rápido?

// Only profiling can answer this.

Cuál es "mejorado" depende en gran medida de la situación.

Answer 17

Solo por usar XOR para responder a un problema relativamente sencillo ...

return a ^ b ? c : a

Answer 18

Solución de ca.

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

o usted puede preferir:

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

Answer 19

Tomando las respuestas (hasta ahora) aquí:

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

y ejecutándolos a través del decompilador (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
}

Puedes ver que los?: Unos son ligeramente mejores que la versión corregida de tu original. El que es el mejor es el que evita la ramificación por completo. Eso es bueno desde el punto de vista de tener menos instrucciones (en la mayoría de los casos) y mejor para las partes de predicción de ramificación de la CPU, ya que una estimación errónea de la predicción de ramificación puede provocar un bloqueo de la CPU.

Yo diría que el más eficiente es el de Moonshadow en general. Utiliza la menor cantidad de instrucciones en promedio y reduce la posibilidad de que se detengan las tuberías en la CPU.

Para estar 100% seguro de que necesitaría averiguar el costo (en ciclos de CPU) para cada instrucción, que, desafortunadamente, no está disponible (tendría que buscar en la fuente de punto de acceso y luego las especificaciones de los proveedores de CPU por el momento) tomado para cada instrucción generada).

Vea la respuesta actualizada de Rotsor para un análisis del código en tiempo de ejecución.

Answer 20

Ya que no se especificó cómo debería mejorarse el código, me esforzaré por mejorar el código haciéndolo más divertido. Aquí está mi solución:

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

En caso de que alguien se pregunte si este código funciona, aquí hay una simplificación utilizando la misma lógica:

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;

}

Esto puede reducirse a lo siguiente:

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

Pero ahora ya no es divertido.

Answer 21

Cía:

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

Answer 22

Como una adición a la excelente publicación de @TofuBeer TofuBeer, considere la respuesta de @pdox pdox:

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

Considere también su versión desensamblada según lo dado por "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

La respuesta de pdox se compila en menos código de bytes que cualquiera de las respuestas anteriores. ¿Cómo se compara su tiempo de ejecución con los demás?

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

Al menos en mi computadora, la respuesta de pdox es solo un poco más rápida que la respuesta de @moonshadow moonshadow, haciendo de pdox el más rápido en general (en mi portátil HP / Intel).

Answer 23

En Ruby:

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

Que podría ejecutarse en JRuby en el JavaVM. ;-)

Answer 24

La forma más sencilla (IMO) que no es confusa y fácil de leer:

// Three booleans, check if two or more are true
return ( a && ( b || c ) ) || ( b && c );

Answer 25

Probablemente no esté buscando nada complicado como los operadores de comparación bit a bit (normalmente no complicado, pero con booleanos, es extremadamente extraño usar operadores bitwise) o algo que es muy rotundo como convertir a int y resumirlos.

La forma más directa y natural de resolver esto es con una expresión como esta:

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

Póngalo en una función si lo prefiere, pero no es muy complicado. La solución es lógicamente concisa y eficiente.

Answer 26

Una interpretación literal funcionará en todos los idiomas principales:

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

Pero probablemente facilitaría la lectura de la gente y la expandiría a más de tres, algo que muchos programadores parecen olvidar:

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

Answer 27

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

Demasiadas maneras de hacer esto ...

Answer 28

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

Answer 29

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

Explicación:

Si a==b , entonces ambos son verdaderos o ambos son falsos. Si ambos son verdaderos, hemos encontrado nuestros dos verdaderos booleanos, y podemos devolverlos verdaderos (devolviendo a ). Si ambos son falsos, no puede haber dos booleanos verdaderos incluso si c es verdadero, por lo que devolvemos falso (devolviendo a ). Esa es la (a==b) ? a (a==b) ? a parte ¿Qué pasa con : c ? Bueno, si a==b es falso, entonces exactamente uno de a o b debe ser verdadero, por lo que hemos encontrado el primer booleano verdadero, y lo único que importa es si c también es verdadero, por lo que devolvemos c como la respuesta .

Answer 30

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