找到最小的3个数字Java最有效的方法？

Question

我有一个用Java编写的算法,我想提高效率.我认为可以提高效率的一个部分是找到3个数字中最小的一个.目前我正在使用如下Math.min方法:

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

这有多高效？用if语句替换是否更有效率:

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

或者,如果任何其他方式更有效

我想知道是否值得改变我目前正在使用的东西？

任何提速都会非常有帮助

Answer 1

对于许多实用程序类型的方法,apache commons库具有可靠的实现,您可以利用它们或从中获得额外的洞察力.在这种情况下,有一种方法可以找到org.apache.commons.lang.math.NumberUtils中可用的三个双打中最小的一个.它们的实现实际上几乎与您最初的想法相同:

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

Answer 2

不,这真的不值得改变.当摆弄这样的微优化时,你将获得的那种改进是不值得的.如果调用该min函数足够,即使是方法调用成本也将被删除.

如果你有你的算法有问题,最好的办法是寻找到宏观的优化("大局"的东西一样算法选择或调整) -你一般会得到很多更好的性能改善那里.

而你的评论表明删除Math.pow改进可能是正确的,但这是因为它是一个相对昂贵的操作.Math.min在成本方面甚至不会接近.

Answer 3

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

不一定比你的代码快.

Answer 4

让我先重复其他人已经说过的话,引用Donald Knuth撰写的"结构化编程与陈述"一文:

我们应该忘记小的效率,大约97%的时间说:过早的优化是所有邪恶的根源.

然而,我们不应该放弃那个关键的3%的机会.一个优秀的程序员不会因为这样的推理而自满,他会明智地仔细研究关键代码; 但只有在确定了该代码之后.

(我强调)

因此,如果您已经确定一个看似微不足道的操作,例如计算最少三个数字是您应用程序中的实际瓶颈(即"关键3%"),那么您可以考虑优化它.

在这种情况下,这实际上是可能的:Math#min(double,double)Java中的方法具有非常特殊的语义:

返回两个double值中较小的一个.也就是说,结果是值更接近负无穷大.如果参数具有相同的值,则结果是相同的值.如果任一值为NaN,则结果为NaN.与数值比较运算符不同,此方法将负零视为严格小于正零.如果一个参数为正零而另一个参数为负零,则结果为负零.

可以看看实现,看看它实际上相当复杂:

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

现在,指出这种行为与简单比较不同可能很重要.可以使用以下示例轻松检查:

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

但是:如果NaN零和正/零的处理与您的应用程序无关,您可以使用Math.min基于简单比较的解决方案替换基于解决方案的解决方案,并查看它是否有所不同.

当然,这将取决于应用程序.这是一个简单的人造微型基准标记(用一粒盐来拍摄!)

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

(免责声明:Java中的Microbenchmarking是一门艺术,为了获得更可靠的结果,我们应该考虑使用JMH或Caliper).

使用JRE 1.8.0_31运行此操作可能会产生类似的结果

....
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

这至少表明这里有可能挤出几个百分点(再次,在一个非常人为的例子中).

通过查看使用创建的热点反汇编输出进一步分析

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

我们可以看到两种方法的优化版本,minA以及minB.

首先,使用的方法的输出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

可以看出,特殊情况的处理涉及一些努力 - 与使用简单比较的输出相比,这是相当简单的:

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

是否存在这样的优化确实对应用程序产生影响的情况很难说.但至少,底线是:

• 该Math#min(double,double)方法是不一样的一个简单的比较,以及特殊病例的治疗并没有免费的午餐
• 有些情况下,不需要进行特殊情况处理,Math#min然后基于比较的方法可能更有效
• 正如其他答案中已经指出的那样:在大多数情况下,性能差异无关紧要.但是,对于这个特定的例子,min(double,double,double)无论如何都应该创建一个实用程序方法,以获得更好的方便性和可读性,然后使用不同的实现很容易进行两次运行,并查看它是否真的会影响性能.

(旁注:积分类型方法,Math.min(int,int)实际上是一个简单的比较 - 所以我希望这些没有区别).

Answer 5

您可以按如下方式使用三元运算符：

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

仅需进行一次分配，并至少进行两次比较。

但是我认为这些语句不会对执行时间产生任何影响，您的初始逻辑将与我的以及其他所有逻辑花费相同的时间。

Answer 6

OP的高效代码有一个bug：

当a == b, and 时a (or b) < c，代码将选择 c 而不是 a 或 b。