una - La forma más eficiente de encontrar el más pequeño de 3 números Java?

numeros primos en una matriz java

Question

Tengo un algoritmo escrito en Java que me gustaría hacer más eficiente. Una parte que creo que podría hacerse más eficiente es encontrar el más pequeño de 3 números. Actualmente estoy usando el método Math.min siguiente manera:

double smallest = Math.min(a, Math.min(b, c));

¿Qué tan eficiente es esto? ¿Sería más eficiente reemplazar con declaraciones if como a continuación?

double smallest;
if (a <= b && a <= c) {
    smallest = a;
} else if (b <= c && b <= a) {
    smallest = b;
} else {
    smallest = c;
}

O si de alguna otra manera es más eficiente

Me pregunto si vale la pena cambiar lo que estoy usando actualmente.

Cualquier aumento de velocidad sería de gran ayuda

Answer 1

El código eficiente de OP tiene un error:

cuando a == b , y a (or b) < c , el código elegirá c en lugar de a o b.

Answer 2

Escriba un método minimum3 que devuelva el más pequeño de los tres números de coma flotante. Use el método Math.min para implementar minimum3. Incorpore el método en una aplicación que lea tres valores del usuario, determine el valor más pequeño y muestre el resultado.

Answer 3

No, en serio no vale la pena cambiarlo. El tipo de mejoras que obtendrás cuando juegues con micro-optimizaciones como esta no valdrá la pena. Incluso el costo de la llamada al método se eliminará si la función min se llama suficiente.

Si tiene un problema con su algoritmo, su mejor opción es estudiar las macro-optimizaciones ("gran imagen", como la selección de algoritmos o la optimización); por lo general, obtendrá mejoras de rendimiento mucho mejores.

Y su comentario de que la eliminación de Math.pow dio mejoras puede ser correcto, pero eso se debe a que es una operación relativamente costosa. Math.min ni siquiera se Math.min a eso en términos de costo.

Answer 4

Para aquellos que encuentran este tema mucho más tarde:

Si solo tiene tres valores para comparar, no hay una diferencia significativa. Pero si tiene que encontrar un mínimo de, por ejemplo, treinta o sesenta valores, "min" podría ser más fácil para que cualquiera lo lea en el código el próximo año:

int smallest;

smallest = min(a1, a2);
smallest = min(smallest, a3);
smallest = min(smallest, a4);
...
smallest = min(smallest, a37);

Pero si piensas en la velocidad, tal vez sería mejor poner valores en la lista, y luego encontrar un mínimo de eso:

List<Integer> mySet = Arrays.asList(a1, a2, a3, ..., a37);

int smallest = Collections.min(mySet);

¿Estarías de acuerdo?

Answer 5

Para muchos métodos de tipo utilidad, las bibliotecas de Apache commons tienen implementaciones sólidas que puede aprovechar u obtener una visión adicional. En este caso, hay un método para encontrar el más pequeño de tres dobles disponible en org.apache.commons.lang.math.NumberUtils. Su implementación es en realidad casi idéntica a su pensamiento inicial:

public static double min(double a, double b, double c) {
    return Math.min(Math.min(a, b), c);
}

Answer 6

Para una eficiencia de caracteres de código pura, no puedo encontrar nada mejor que

smallest = a<b&&a<c?a:b<c?b:c;

Answer 7

Permítanme primero repetir lo que otros ya dijeron, citando el artículo "Programación estructurada con ir a declaraciones" de Donald Knuth:

Deberíamos olvidarnos de las pequeñas eficiencias, digamos aproximadamente el 97% del tiempo: la optimización prematura es la raíz de todo mal.

Sin embargo, no deberíamos dejar pasar nuestras oportunidades en ese crítico 3%. Un buen programador no se dejará llevar por la complacencia con tal razonamiento; será prudente que mire cuidadosamente el código crítico; pero solo después de que ese código ha sido identificado.

(énfasis por mí)

Entonces, si ha identificado que una operación aparentemente trivial como el cálculo de un mínimo de tres números es el cuello de botella real (es decir, el "3% crítico") en su aplicación, entonces puede considerar optimizarlo.

Y en este caso, esto es realmente posible: el método Math#min(double,double) en Java tiene una semántica muy especial:

Devuelve el menor de dos valores dobles. Es decir, el resultado es el valor más cercano al infinito negativo. Si los argumentos tienen el mismo valor, el resultado es el mismo valor. Si cualquiera de los valores es NaN, entonces el resultado es NaN. A diferencia de los operadores de comparación numérica, este método considera que el cero negativo es estrictamente más pequeño que el cero positivo. Si un argumento es cero positivo y el otro cero negativo, el resultado es cero negativo.

Uno puede echar un vistazo a la implementación y ver que en realidad es bastante compleja:

public static double min(double a, double b) {
    if (a != a)
        return a;   // a is NaN
    if ((a == 0.0d) &&
        (b == 0.0d) &&
        (Double.doubleToRawLongBits(b) == negativeZeroDoubleBits)) {
        // Raw conversion ok since NaN can''t map to -0.0.
        return b;
    }
    return (a <= b) ? a : b;
}

Ahora, puede ser importante señalar que este comportamiento es diferente de una simple comparación. Esto se puede examinar fácilmente con el siguiente ejemplo:

public class MinExample
{
    public static void main(String[] args)
    {
        test(0.0, 1.0);
        test(1.0, 0.0);
        test(-0.0, 0.0);
        test(Double.NaN, 1.0);
        test(1.0, Double.NaN);
    }

    private static void test(double a, double b)
    {
        double minA = Math.min(a, b);
        double minB = a < b ? a : b;
        System.out.println("a: "+a);
        System.out.println("b: "+b);
        System.out.println("minA "+minA);
        System.out.println("minB "+minB);
        if (Double.doubleToRawLongBits(minA) !=
            Double.doubleToRawLongBits(minB))
        {
            System.out.println(" -> Different results!");
        }
        System.out.println();
    }
}

Sin embargo, si el tratamiento de NaN y cero positivo / negativo no es relevante para su aplicación, puede reemplazar la solución que está basada en Math.min con una solución que se basa en una comparación simple y ver si hace una diferencia.

Esto, por supuesto, será dependiente de la aplicación. Aquí hay una microbanda artificial simple (¡ para tomar con un grano de sal! )

import java.util.Random;

public class MinPerformance
{
    public static void main(String[] args)
    {
        bench();
    }

    private static void bench()
    {
        int runs = 1000;
        for (int size=10000; size<=100000; size+=10000)
        {
            Random random = new Random(0);
            double data[] = new double[size];
            for (int i=0; i<size; i++)
            {
                data[i] = random.nextDouble();
            }
            benchA(data, runs);
            benchB(data, runs);
        }
    }

    private static void benchA(double data[], int runs)
    {
        long before = System.nanoTime();
        double sum = 0;
        for (int r=0; r<runs; r++)
        {
            for (int i=0; i<data.length-3; i++)
            {
                sum += minA(data[i], data[i+1], data[i+2]);
            }
        }
        long after = System.nanoTime();
        System.out.println("A: length "+data.length+", time "+(after-before)/1e6+", result "+sum);
    }

    private static void benchB(double data[], int runs)
    {
        long before = System.nanoTime();
        double sum = 0;
        for (int r=0; r<runs; r++)
        {
            for (int i=0; i<data.length-3; i++)
            {
                sum += minB(data[i], data[i+1], data[i+2]);
            }
        }
        long after = System.nanoTime();
        System.out.println("B: length "+data.length+", time "+(after-before)/1e6+", result "+sum);
    }

    private static double minA(double a, double b, double c)
    {
        return Math.min(a, Math.min(b, c));
    }

    private static double minB(double a, double b, double c)
    {
        if (a < b)
        {
            if (a < c)
            {
                return a;
            }
            return c;
        }
        if (b < c)
        {
            return b;
        }
        return c;
    }
}

(Descargo de responsabilidad: Microbenchmarking en Java es un arte, y para obtener resultados más confiables, uno debe considerar el uso de JMH o Caliper ).

Ejecutar esto con JRE 1.8.0_31 puede dar como resultado algo así como

....
A: length 90000, time 545.929078, result 2.247805342620906E7
B: length 90000, time 441.999193, result 2.247805342620906E7
A: length 100000, time 608.046928, result 2.5032781001456387E7
B: length 100000, time 493.747898, result 2.5032781001456387E7

Esto al menos sugiere que podría ser posible exprimir un pequeño porcentaje aquí (nuevamente, en un ejemplo muy artificial).

Analizando esto más a fondo, mirando la salida de desensamblaje del hotspot creada con

java -server -XX:+UnlockDiagnosticVMOptions -XX:+TraceClassLoading -XX:+LogCompilation -XX:+PrintAssembly MinPerformance

uno puede ver las versiones optimizadas de ambos métodos, minA y minB .

Primero, el resultado del método que usa Math.min :

Decoding compiled method 0x0000000002992310:
Code:
[Entry Point]
[Verified Entry Point]
[Constants]
  # {method} {0x000000001c010910} 'minA' '(DDD)D' in 'MinPerformance'
  # parm0:    xmm0:xmm0   = double
  # parm1:    xmm1:xmm1   = double
  # parm2:    xmm2:xmm2   = double
  #           [sp+0x60]  (sp of caller)
  0x0000000002992480: mov    %eax,-0x6000(%rsp)
  0x0000000002992487: push   %rbp
  0x0000000002992488: sub    $0x50,%rsp
  0x000000000299248c: movabs $0x1c010cd0,%rsi
  0x0000000002992496: mov    0x8(%rsi),%edi
  0x0000000002992499: add    $0x8,%edi
  0x000000000299249c: mov    %edi,0x8(%rsi)
  0x000000000299249f: movabs $0x1c010908,%rsi   ; {metadata({method} {0x000000001c010910} 'minA' '(DDD)D' in 'MinPerformance')}
  0x00000000029924a9: and    $0x3ff8,%edi
  0x00000000029924af: cmp    $0x0,%edi
  0x00000000029924b2: je     0x00000000029924e8  ;*dload_0
                        ; - MinPerformance::minA@0 (line 58)

  0x00000000029924b8: vmovsd %xmm0,0x38(%rsp)
  0x00000000029924be: vmovapd %xmm1,%xmm0
  0x00000000029924c2: vmovapd %xmm2,%xmm1       ;*invokestatic min
                        ; - MinPerformance::minA@4 (line 58)

  0x00000000029924c6: nop
  0x00000000029924c7: callq  0x00000000028c6360  ; OopMap{off=76}
                        ;*invokestatic min
                        ; - MinPerformance::minA@4 (line 58)
                        ;   {static_call}
  0x00000000029924cc: vmovapd %xmm0,%xmm1       ;*invokestatic min
                        ; - MinPerformance::minA@4 (line 58)

  0x00000000029924d0: vmovsd 0x38(%rsp),%xmm0   ;*invokestatic min
                        ; - MinPerformance::minA@7 (line 58)

  0x00000000029924d6: nop
  0x00000000029924d7: callq  0x00000000028c6360  ; OopMap{off=92}
                        ;*invokestatic min
                        ; - MinPerformance::minA@7 (line 58)
                        ;   {static_call}
  0x00000000029924dc: add    $0x50,%rsp
  0x00000000029924e0: pop    %rbp
  0x00000000029924e1: test   %eax,-0x27623e7(%rip)        # 0x0000000000230100
                        ;   {poll_return}
  0x00000000029924e7: retq
  0x00000000029924e8: mov    %rsi,0x8(%rsp)
  0x00000000029924ed: movq   $0xffffffffffffffff,(%rsp)
  0x00000000029924f5: callq  0x000000000297e260  ; OopMap{off=122}
                        ;*synchronization entry
                        ; - MinPerformance::minA@-1 (line 58)
                        ;   {runtime_call}
  0x00000000029924fa: jmp    0x00000000029924b8
  0x00000000029924fc: nop
  0x00000000029924fd: nop
  0x00000000029924fe: mov    0x298(%r15),%rax
  0x0000000002992505: movabs $0x0,%r10
  0x000000000299250f: mov    %r10,0x298(%r15)
  0x0000000002992516: movabs $0x0,%r10
  0x0000000002992520: mov    %r10,0x2a0(%r15)
  0x0000000002992527: add    $0x50,%rsp
  0x000000000299252b: pop    %rbp
  0x000000000299252c: jmpq   0x00000000028ec620  ; {runtime_call}
  0x0000000002992531: hlt
  0x0000000002992532: hlt
  0x0000000002992533: hlt
  0x0000000002992534: hlt
  0x0000000002992535: hlt
  0x0000000002992536: hlt
  0x0000000002992537: hlt
  0x0000000002992538: hlt
  0x0000000002992539: hlt
  0x000000000299253a: hlt
  0x000000000299253b: hlt
  0x000000000299253c: hlt
  0x000000000299253d: hlt
  0x000000000299253e: hlt
  0x000000000299253f: hlt
[Stub Code]
  0x0000000002992540: nop                       ;   {no_reloc}
  0x0000000002992541: nop
  0x0000000002992542: nop
  0x0000000002992543: nop
  0x0000000002992544: nop
  0x0000000002992545: movabs $0x0,%rbx          ; {static_stub}
  0x000000000299254f: jmpq   0x000000000299254f  ; {runtime_call}
  0x0000000002992554: nop
  0x0000000002992555: movabs $0x0,%rbx          ; {static_stub}
  0x000000000299255f: jmpq   0x000000000299255f  ; {runtime_call}
[Exception Handler]
  0x0000000002992564: callq  0x000000000297b9e0  ; {runtime_call}
  0x0000000002992569: mov    %rsp,-0x28(%rsp)
  0x000000000299256e: sub    $0x80,%rsp
  0x0000000002992575: mov    %rax,0x78(%rsp)
  0x000000000299257a: mov    %rcx,0x70(%rsp)
  0x000000000299257f: mov    %rdx,0x68(%rsp)
  0x0000000002992584: mov    %rbx,0x60(%rsp)
  0x0000000002992589: mov    %rbp,0x50(%rsp)
  0x000000000299258e: mov    %rsi,0x48(%rsp)
  0x0000000002992593: mov    %rdi,0x40(%rsp)
  0x0000000002992598: mov    %r8,0x38(%rsp)
  0x000000000299259d: mov    %r9,0x30(%rsp)
  0x00000000029925a2: mov    %r10,0x28(%rsp)
  0x00000000029925a7: mov    %r11,0x20(%rsp)
  0x00000000029925ac: mov    %r12,0x18(%rsp)
  0x00000000029925b1: mov    %r13,0x10(%rsp)
  0x00000000029925b6: mov    %r14,0x8(%rsp)
  0x00000000029925bb: mov    %r15,(%rsp)
  0x00000000029925bf: movabs $0x515db148,%rcx   ; {external_word}
  0x00000000029925c9: movabs $0x2992569,%rdx    ; {internal_word}
  0x00000000029925d3: mov    %rsp,%r8
  0x00000000029925d6: and    $0xfffffffffffffff0,%rsp
  0x00000000029925da: callq  0x00000000512a9020  ; {runtime_call}
  0x00000000029925df: hlt
[Deopt Handler Code]
  0x00000000029925e0: movabs $0x29925e0,%r10    ; {section_word}
  0x00000000029925ea: push   %r10
  0x00000000029925ec: jmpq   0x00000000028c7340  ; {runtime_call}
  0x00000000029925f1: hlt
  0x00000000029925f2: hlt
  0x00000000029925f3: hlt
  0x00000000029925f4: hlt
  0x00000000029925f5: hlt
  0x00000000029925f6: hlt
  0x00000000029925f7: hlt

Se puede ver que el tratamiento de casos especiales implica cierto esfuerzo, en comparación con el resultado que utiliza comparaciones simples, lo que es bastante sencillo:

Decoding compiled method 0x0000000002998790:
Code:
[Entry Point]
[Verified Entry Point]
[Constants]
  # {method} {0x000000001c0109c0} 'minB' '(DDD)D' in 'MinPerformance'
  # parm0:    xmm0:xmm0   = double
  # parm1:    xmm1:xmm1   = double
  # parm2:    xmm2:xmm2   = double
  #           [sp+0x20]  (sp of caller)
  0x00000000029988c0: sub    $0x18,%rsp
  0x00000000029988c7: mov    %rbp,0x10(%rsp) ;*synchronization entry
                        ; - MinPerformance::minB@-1 (line 63)

  0x00000000029988cc: vucomisd %xmm0,%xmm1
  0x00000000029988d0: ja     0x00000000029988ee  ;*ifge
                        ; - MinPerformance::minB@3 (line 63)

  0x00000000029988d2: vucomisd %xmm1,%xmm2
  0x00000000029988d6: ja     0x00000000029988de  ;*ifge
                        ; - MinPerformance::minB@22 (line 71)

  0x00000000029988d8: vmovapd %xmm2,%xmm0
  0x00000000029988dc: jmp    0x00000000029988e2
  0x00000000029988de: vmovapd %xmm1,%xmm0 ;*synchronization entry
                        ; - MinPerformance::minB@-1 (line 63)

  0x00000000029988e2: add    $0x10,%rsp
  0x00000000029988e6: pop    %rbp
  0x00000000029988e7: test   %eax,-0x27688ed(%rip)        # 0x0000000000230000
                        ;   {poll_return}
  0x00000000029988ed: retq
  0x00000000029988ee: vucomisd %xmm0,%xmm2
  0x00000000029988f2: ja     0x00000000029988e2  ;*ifge
                        ; - MinPerformance::minB@10 (line 65)

  0x00000000029988f4: vmovapd %xmm2,%xmm0
  0x00000000029988f8: jmp    0x00000000029988e2
  0x00000000029988fa: hlt
  0x00000000029988fb: hlt
  0x00000000029988fc: hlt
  0x00000000029988fd: hlt
  0x00000000029988fe: hlt
  0x00000000029988ff: hlt
[Exception Handler]
[Stub Code]
  0x0000000002998900: jmpq   0x00000000028ec920  ;   {no_reloc}
[Deopt Handler Code]
  0x0000000002998905: callq  0x000000000299890a
  0x000000000299890a: subq   $0x5,(%rsp)
  0x000000000299890f: jmpq   0x00000000028c7340  ; {runtime_call}
  0x0000000002998914: hlt
  0x0000000002998915: hlt
  0x0000000002998916: hlt
  0x0000000002998917: hlt

Si es o no hay casos en que dicha optimización realmente hace una diferencia en una aplicación es difícil de decir. Pero al menos, el resultado final es:

• El método Math#min(double,double) no es lo mismo que una simple comparación, y el tratamiento de los casos especiales no es gratis.
• Hay casos en los que el tratamiento de casos especiales que se realiza mediante Math#min no es necesario, y luego un enfoque basado en la comparación puede ser más eficiente.
• Como ya se señaló en otras respuestas: en la mayoría de los casos, la diferencia de rendimiento no tendrá importancia. Sin embargo, para este ejemplo en particular, uno probablemente debería crear un método de utilidad min(double,double,double) todos modos, para una mejor conveniencia y legibilidad, y entonces sería fácil hacer dos ejecuciones con las diferentes implementaciones, y ver si realmente afecta el rendimiento.

(Nota al Math.min(int,int) : los métodos de tipo integral, como Math.min(int,int) realidad son una comparación simple, así que no esperaría ninguna diferencia para estos).

Answer 8

Puede usar el operador ternario de la siguiente manera:

smallest=(a<b)?((a<c)?a:c):((b<c)?b:c);

Lo cual toma solo una asignación y un mínimo de dos comparaciones.

Pero creo que estas declaraciones no tendrán ningún efecto en el tiempo de ejecución, su lógica inicial tomará el mismo tiempo que el mío y todos los demás.

Answer 9

Si llama a min () alrededor de 1kk veces con diferentes a, b, c, entonces use mi método:

Aquí solo dos comparaciones. No hay forma de calcificar más rápido: P

public static double min(double a, double b, double c) {
    if (a > b) {     //if true, min = b
        if (b > c) { //if true, min = c
            return c;
        } else {     //else min = b
            return b; 
        }
    }          //else min = a
    if (a > c) {  // if true, min=c
        return c;
    } else {
        return a;
    }
}

Answer 10

Simplemente usa esta función matemática

System.out.println(Math.min(a,b,c));

Obtendrás la respuesta en una sola línea.

Answer 11

Todo parece estar bien, tu código estará bien, a menos que estés haciendo esto en un circuito cerrado. Yo también consideraría

double min;
min = (a<b) ? a : b;
min = (min<c) ? min : c;

Answer 12

Yo usaría min/max (y no me preocuparía de otra forma) ... sin embargo, aquí hay otro enfoque de "mano larga" que puede o no ser más fácil de entender para algunas personas. (No esperaría que fuera más rápido o más lento que el código en la publicación).

int smallest;
if (a < b) {
  if (a > c) {
    smallest = c;
  } else { // a <= c
    smallest = a;
  }
} else { // a >= b
  if (b > c) {
    smallest = c;
  } else { // b <= c
    smallest = b;
  }
}

Solo lanzándolo a la mezcla.

Tenga en cuenta que esta es solo la variante de efecto secundario de la respuesta de Abhishek.

Answer 13

Math.min usa una comparación simple para hacer su trabajo. La única ventaja de no usar Math.min es guardar las llamadas a funciones adicionales, pero eso es un ahorro insignificante.

Si tiene más de tres números, tener un método minimum para cualquier número de double puede ser valioso y se verá algo así como:

public static double min(double ... numbers) {
    double min = numbers[0];
    for (int i=1 ; i<numbers.length ; i++) {
        min = (min <= numbers[i]) ? min : numbers[i];
    }
    return min;
}

Para tres números, este es el equivalente funcional de Math.min(a, Math.min(b, c)); pero guarda una invocación de método.

Answer 14

double smallest = a;
if (smallest > b) smallest = b;
if (smallest > c) smallest = c;

No necesariamente más rápido que tu código.

Answer 15

double smallest;
if(a<b && a<c){
    smallest = a;
}else if(b<c && b<a){
    smallest = b;
}else{
    smallest = c;
}

se puede mejorar a:

double smallest;
if(a<b && a<c){
smallest = a;
}else if(b<c){
    smallest = b;
}else{
    smallest = c;
}