具有流和性能的 Java 8 嵌套循环

Question

为了练习 Java 8 流，我尝试将以下嵌套循环转换为 Java 8 流 API。它计算 a^b (a,b < 100) 的最大数字总和，并在我的 Core i5 760 上花费大约 0.135 秒。

public static int digitSum(BigInteger x)
{
    int sum = 0;
    for(char c: x.toString().toCharArray()) {sum+=Integer.valueOf(c+"");}
    return sum;
}

@Test public void solve()
    {
        int max = 0;
        for(int i=1;i<100;i++)
            for(int j=1;j<100;j++)
                max = Math.max(max,digitSum(BigInteger.valueOf(i).pow(j)));
        System.out.println(max);
    }

我的解决方案，由于并行性，我预计会更快，但实际上只用了 0.25 秒(没有 parallel() 时为 0.19 秒):

int max =   IntStream.range(1,100).parallel()
            .map(i -> IntStream.range(1, 100)
            .map(j->digitSum(BigInteger.valueOf(i).pow(j)))
            .max().getAsInt()).max().getAsInt();

我的问题

• 我的转换是否正确，或者是否有更好的方法将嵌套循环转换为流计算？
• 为什么流变体比旧变体慢这么多？
• 为什么 parallel() 语句实际上将时间从 0.19 秒增加到 0.25 秒？

我知道微基准测试是脆弱的，并行性仅在解决大问题时才值得，但对于 CPU 来说，即使是 0.1 秒也是永恒的，对吧？

更新

我使用 Eclipse Kepler 中的 Junit 4 框架进行测量(它显示了执行测试所花费的时间)。

我对 a,b<1000 而不是 100 的结果:

• 传统循环 186s
• 顺序流 193s
• 并行流 55s

更新 2将 sum+=Integer.valueOf(c+""); 替换为 sum+= c - '0';(感谢 Peter!)节省了并行方法的整整 10 秒，把它带到 45s。没想到性能影响这么大!

此外，减少 CPU 内核数量(在我的例子中是 4 个)的并行度并没有多大作用，因为它只将时间减少到 44.8 秒(是的，它增加了 a 和 b=0，但我认为这不会'对性能影响不大):

int max = IntStream.range(0, 3).parallel().
          .map(m -> IntStream.range(0,250)
          .map(i -> IntStream.range(1, 1000)
          .map(j->.digitSum(BigInteger.valueOf(250*m+i).pow(j)))
          .max().getAsInt()).max().getAsInt()).max().getAsInt();

Answer 1

我已经根据您的代码创建了一个快速而粗略的微基准测试。结果是:

loop: 3192
lambda: 3140
lambda parallel: 868

所以循环和 lambda 是等价的，并行流显着提高了性能。由于您的基准测试方法，我怀疑您的结果不可靠。

public static void main(String[] args) {
    int sum = 0;

    //warmup
    for (int i = 0; i < 100; i++) {
        solve();
        solveLambda();
        solveLambdaParallel();
    }

    {
        long start = System.nanoTime();
        for (int i = 0; i < 100; i++) {
            sum += solve();
        }
        long end = System.nanoTime();
        System.out.println("loop: " + (end - start) / 1_000_000);
    }
    {
        long start = System.nanoTime();
        for (int i = 0; i < 100; i++) {
            sum += solveLambda();
        }
        long end = System.nanoTime();
        System.out.println("lambda: " + (end - start) / 1_000_000);
    }
    {
        long start = System.nanoTime();
        for (int i = 0; i < 100; i++) {
            sum += solveLambdaParallel();
        }
        long end = System.nanoTime();
        System.out.println("lambda parallel : " + (end - start) / 1_000_000);
    }
    System.out.println(sum);
}

public static int digitSum(BigInteger x) {
    int sum = 0;
    for (char c : x.toString().toCharArray()) {
        sum += Integer.valueOf(c + "");
    }
    return sum;
}

public static int solve() {
    int max = 0;
    for (int i = 1; i < 100; i++) {
        for (int j = 1; j < 100; j++) {
            max = Math.max(max, digitSum(BigInteger.valueOf(i).pow(j)));
        }
    }
    return max;
}

public static int solveLambda() {
    return  IntStream.range(1, 100)
            .map(i -> IntStream.range(1, 100).map(j -> digitSum(BigInteger.valueOf(i).pow(j))).max().getAsInt())
            .max().getAsInt();
}

public static int solveLambdaParallel() {
    return  IntStream.range(1, 100)
            .parallel()
            .map(i -> IntStream.range(1, 100).map(j -> digitSum(BigInteger.valueOf(i).pow(j))).max().getAsInt())
            .max().getAsInt();
}

---

我还使用 jmh 运行它，它比手动测试更可靠。结果与上面一致(每次调用微秒):

Benchmark                                Mode   Mean        Units
c.a.p.SO21968918.solve                   avgt   32367.592   us/op
c.a.p.SO21968918.solveLambda             avgt   31423.123   us/op
c.a.p.SO21968918.solveLambdaParallel     avgt   8125.600    us/op