java - 循环 i++ 与 i+=2

Question

我一直在尝试创建一个有效的算法来查找素数，作为我尝试的一部分，我一直在使用以下代码。我想通过将激励更改为 i+=2 来加快循环，但实际上进行此更改似乎会使我的程序运行时间增加 2 秒。任何人都可以解释为什么会发生这种情况，因为循环似乎必须完成一半的工作才能完成？

for(int i = answers.get(answers.size()-1)+2;i<n;i++) {
        int bit = i%64;
        int currentInt = i/64;

        int isPrime = (primes[currentInt] >> bit) & 1;
        if(isPrime == 1) {answers.add(i);}
    }

完整代码如下:

import java.util.ArrayList;
import java.util.List;
import java.util.stream.IntStream;

public class Primes15 {
  static Long start;

  public static IntStream stream() {
    int numbers = 15350808;
    int n = 982451712;
    List<Integer> answers = new ArrayList<>();
    long[] inverseShifts = new long[64];
    long temp = 1;

    for(int i = 0; i < inverseShifts.length; i++) {
      inverseShifts[i] = temp ^ -1;
      temp = temp << 1;
    }

    long[] primes = new long[numbers+1];
    primes[0] = -6148914691370734930L;
    for(int i = 1;i<primes.length; i++) {
      primes[i] = -6148914691370734934L;
    }

    System.out.println("Setup taken " + (System.currentTimeMillis() - start) + "  millis");
    start = System.currentTimeMillis();

    for(int p =3; p*p <=n; p+=2) {
      int bit = p%64;
      int currentInt = p/64;
      long isPrime = (primes[currentInt] >> bit) & 1;
      if(isPrime == 1) {
        answers.add(p);
        int cPrimeSquared = p*p;
        int change = (p==2)? p : p+p;
        for(int i = cPrimeSquared; i <= n; i += change) {
          int innerBit = i % 64;
          int innerInt = i /64;
          isPrime = (primes[innerInt] >> innerBit) & 1;
          if(isPrime == 1) {
            primes[innerInt] = primes[innerInt] & inverseShifts[innerBit];
          }
        }
      }
      System.out.println("finder took " + (System.currentTimeMillis() - start) + "  ms");
      start = System.currentTimeMillis();
      for(int i = answers.get(answers.size()-1)+2; i<n; i++) {
        int bit = i%64;
        int currentInt = i/64;
        long isPrime = (primes[currentInt] >> bit) & 1;
        if(isPrime == 1) {answers.add(i);}
      }
      System.out.println("search took " + (System.currentTimeMillis() - start) + "  ms");
      start = System.currentTimeMillis();

      return answers.stream().mapToInt(i->i);
    }

  public static void main(String[] args) {
    start = System.currentTimeMillis();
    stream();
    Long finish = System.currentTimeMillis();
    System.out.println("Time taken " + (finish - start) + "  millis");
  }
}

Answer 1

我用 JMH 做了一些测试 - 由于整个代码丢失并且仍然难以阅读，我使用了一个简化的、天真的版本(不能用于查找素数，但具有类似的计算恕我直言):

@State(Scope.Benchmark)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class Increments {

    private long[] primes;

    @Setup
    public void setup() {
        primes = new long[] {3, 5, 7, 11, 13, 17, 19, 23};
    }

    @Benchmark
    @Fork(1)
    public List<Integer> inc() {
        List<Integer> answers = new ArrayList<>();
        for (int i = 3; i < 100; i++) {
            int bit = i % 32;
            int cur = i / 32;
            long test = (primes[cur] >> bit) & 1;
            if (test == 1) {
                answers.add(i);
            }
        }
        return answers;
    }

    @Benchmark
    @Fork(1)
    public List<Integer> addOne() {
        List<Integer> answers = new ArrayList<>();
        for (int i = 3; i < 100; i+=1) {
            int bit = i % 32;
            int cur = i / 32;
            long test = (primes[cur] >> bit) & 1;
            if (test == 1) {
                answers.add(i);
            }
        }
        return answers;
    }

    @Benchmark
    @Fork(1)
    public List<Integer> addTwo() {
        List<Integer> answers = new ArrayList<>();
        for (int i = 3; i < 100; i+=2) {
            int bit = i % 32;
            int cur = i / 32;
            long test = (primes[cur] >> bit) & 1;
            if (test == 1) {
                answers.add(i);
            }
        }
        return answers;
    }
}

结果(5 次预热迭代，5 次测量迭代):

Benchmark          Mode  Cnt    Score    Error  Units
Increments.addOne  avgt    5  304,670 ± 73,226  ns/op
Increments.addTwo  avgt    5  131,429 ± 13,616  ns/op
Increments.inc     avgt    5  249,329 ± 14,866  ns/op

即每次操作按纳秒排序:

i+=2  131ns
i++   249ns
i+=1  304ns

有点符合预期:递增 2 快 2 倍；有点意外，i += 1 比 i++ 慢一点——我本以为编译器会为两者创建相同的操作码

_{第一次接触 JMH，不确定我是否做到了 100% 正确，但必须对其进行测试 [:-)}