在Java中检测偶数的最有效方法是什么？ [重复]

问题描述 投票：10回答：4

这个问题在这里已有答案：

确定一个数字甚至是使用Java的最有效方法是什么？为什么？

它会使用模数或减法，还是其他一些我没想过的方式？

有人想象我可以确定这是一个简单的测试课 - 我可以 - 但这真的不能解释为什么，是吗？

我没有做一些疯狂的裤子性能调整，以实现更快处理许多项目的一些崇高目标。但我很好奇一种方法应该优先于另一种方法作为常规做法。以同样的方式，我们不会使用&代替&&，为什么在我们可以使用%时使用&？

java performance math
4个回答
19
投票

如果检查这两种方法的热点7生成的程序集：

public static boolean isEvenBit(int i) {
    return (i & 1) == 0;
}
public static boolean isEvenMod(int i) {
    return i % 2 == 0;
}

你会看到虽然mod已经过优化，但基本上是按位and，但它有一些额外的指令，因为这两个操作并不是严格等同的*。其他JVM可能以不同方式对其进行优化。装配在下面张贴以供参考。

我还运行了一个微基准测试，证实了我们的观察结果：isEventBit稍微快一点（但两者都运行在2纳秒左右，因此整个典型程序可能没有太多的影响）：

Benchmark                     Mode  Samples  Score   Error  Units
c.a.p.SO16969220.isEvenBit    avgt       10  1.869 ± 0.069  ns/op
c.a.p.SO16969220.isEvenMod    avgt       10  2.554 ± 0.142  ns/op

isEvenBit

  # {method} 'isEvenBit' '(I)Z' in 'javaapplication4/Test1'
  # parm0:    rdx       = int
  #           [sp+0x20]  (sp of caller)
  0x00000000026c2580: sub    rsp,0x18
  0x00000000026c2587: mov    QWORD PTR [rsp+0x10],rbp  ;*synchronization entry
                                                ; - javaapplication4.Test1::isEvenBit@-1 (line 66)
  0x00000000026c258c: and    edx,0x1
  0x00000000026c258f: mov    eax,edx
  0x00000000026c2591: xor    eax,0x1            ;*ireturn
                                                ; - javaapplication4.Test1::isEvenBit@11 (line 66)
  0x00000000026c2594: add    rsp,0x10
  0x00000000026c2598: pop    rbp
  0x00000000026c2599: test   DWORD PTR [rip+0xfffffffffdb6da61],eax        # 0x0000000000230000
                                                ;   {poll_return}
  0x00000000026c259f: ret

isEvenMod

  # {method} 'isEvenMod' '(I)Z' in 'javaapplication4/Test1'
  # parm0:    rdx       = int
  #           [sp+0x20]  (sp of caller)
  0x00000000026c2780: sub    rsp,0x18
  0x00000000026c2787: mov    QWORD PTR [rsp+0x10],rbp  ;*synchronization entry
                                                ; - javaapplication4.Test1::isEvenMod@-1 (line 63)
  0x00000000026c278c: mov    r10d,edx
  0x00000000026c278f: and    r10d,0x1           ;*irem
                                                ; - javaapplication4.Test1::isEvenMod@2 (line 63)
  0x00000000026c2793: mov    r11d,r10d
  0x00000000026c2796: neg    r11d
  0x00000000026c2799: test   edx,edx
  0x00000000026c279b: cmovl  r10d,r11d
  0x00000000026c279f: test   r10d,r10d
  0x00000000026c27a2: setne  al
  0x00000000026c27a5: movzx  eax,al
  0x00000000026c27a8: xor    eax,0x1            ;*ireturn
                                                ; - javaapplication4.Test1::isEvenMod@11 (line 63)
  0x00000000026c27ab: add    rsp,0x10
  0x00000000026c27af: pop    rbp
  0x00000000026c27b0: test   DWORD PTR [rip+0xfffffffffdb6d84a],eax        # 0x0000000000230000
                                                ;   {poll_return}
  0x00000000026c27b6: ret

*正如评论中指出的那样，%并不是真正的模数;这是剩下的。所以(i % 2) != (i & 1)如果i < 0。 isEvenMod代码中的额外指令将结果的符号设置为i的符号（然后将其与零进行比较，因此浪费了精力）。

5
投票

另一种方法是运行微基准测试并分析每个变体所花费的时间。结果如下：

Benchmark    Mean    Units    Time vs. baseline
baseline     10.330  nsec/op     0.000
bitAnd       12.075  nsec/op     1.745
bitShift     12.309  nsec/op     1.979
modulo       12.309  nsec/op     4.529

（基线是一种只返回i == 0的方法）

结论：

  • i & 1 ----->大约需要1.75ns
  • i << 31 - >需要大约2.00ns
  • i % 2 ----->需要大约4.50ns

换句话说，i % 2比i & 1慢2倍。

注释：使用jmh完成基准测试。基线很高，因为我生成随机数以确保方法不被优化。测试使用热点7在i7 @ 2.8GHz（即一个周期= 0.35ns）上运行。

4
投票
if ((i & 1) == 0) {
  // Even
}
4
投票

TL; DR按位和版本似乎是最快的。下面的基准和样本结果。

这应该比模数更快，因为它只能在硬件中直接处理两个步骤：

if ((n & 1) == 0) {
  // even number here
}

这是一个微基准测试，证明了我和aasylias的观点：

    // setup
    int runs = 10;
    int numbers = 200000000; // 200.000.000
    int[] randomNumbers = new int[numbers];
    Random random = new Random();
    for (int i = 0; i < randomNumbers.length; i++) {
        randomNumbers[i] = random.nextInt();
    }
    int even = 0;
    int odd = 0;

    // bitwiseAnd
    long andStart = System.currentTimeMillis();
    for (int i = 0; i < runs; i++) {
        for (int number : randomNumbers) {
            if ((number & 1) == 0)
                even++;
            else
                odd++;
        }
    }
    long andDone = System.currentTimeMillis();
    long andDuration = andDone - andStart;

    System.out.println("Even " + even + ", odd " + odd);

    // reset variables
    even = 0;
    odd = 0;

    // Modulo
    long moduloStart = System.currentTimeMillis();
    for (int i = 0; i < runs; i++) {
        for (int number : randomNumbers) {
            if (number % 2 == 0)
                even++;
            else
                odd++;
        }
    }
    long moduloDone = System.currentTimeMillis();
    long moduloDuration = moduloDone - moduloStart;
    // Done with modulo

    System.out.println("Even " + even + ", odd " + odd);

    // reset variables
    even = 0;
    odd = 0;

    // Shift
    long shiftStart = System.currentTimeMillis();
    for (int i = 0; i < runs; i++) {
        for (int number : randomNumbers) {
            if ((number << 31) == 0)
                even++;
            else
                odd++;
        }
    }
    long shiftDone = System.currentTimeMillis();
    long shiftDuration = shiftDone - shiftStart;
    // Done with shift

    System.out.println("Even " + even + ", odd " + odd);

    System.out.println("Modulo Time    " + moduloDuration);
    System.out.println("Bitwise & Time " + andDuration);
    System.out.println("Shift Time     " + shiftDuration);

按位总是快一点（即使你用模数块切换代码块）。样本输出：

Even 999999530, odd 1000000470
Even 999999530, odd 1000000470
Even 999999530, odd 1000000470
Modulo Time    17731
Bitwise & Time 9672
Shift Time     10638
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.