java - 如何才能最好地优化循环超过十亿次的循环？

Question

假设我想执行循环十亿次，如何优化循环以更快地获得结果？

举个例子:

double randompoint;
for(long count =0; count < 1000000000; count++) {
        randompoint = (Math.random() * 1) + 0;  //generate a random point
        if(randompoint <= .75) {
            var++; 
        }
    }

我正在阅读矢量化？但我不太确定该怎么做。有什么想法吗？

Answer 1

由于 Java 是跨平台的，因此您几乎必须依赖 JIT 来进行矢量化。在你的情况下它不能，因为每次迭代都很大程度上依赖于前一次迭代(由于 RNG 的工作方式)。

但是，还有另外两种主要方法可以改进计算。

首先，这项工作非常适合并行化。技术术语是embarrassingly parallel 。这意味着多线程将在核心数量上提供完美的线性加速。

第二个是 Math.random() 被编写为多线程安全的，这也意味着它很慢，因为它需要使用原子操作。这没有什么帮助，因此我们可以通过使用非线程安全的 RNG 来跳过该开销。

自 1.5 以来，我没有编写太多 Java，但这里有一个愚蠢的实现:

import java.util.*;
import java.util.concurrent.*;

class Foo implements Runnable {
  private long count;
  private double threshold;
  private long result;

  public Foo(long count, double threshold) {
    this.count = count;
    this.threshold = threshold;
  }

  public void run() {
    ThreadLocalRandom rand = ThreadLocalRandom.current();
    for(long l=0; l<count; l++) {
      if(rand.nextDouble() < threshold)
        result++;
    }
  }

  public static void main(String[] args) throws Exception {
    long count = 1000000000;
    double threshold = 0.75;
    int cores = Runtime.getRuntime().availableProcessors();
    long sum = 0;

    List<Foo> list = new ArrayList<Foo>();
    List<Thread> threads = new ArrayList<Thread>();
    for(int i=0; i<cores; i++) {
      // TODO: account for count%cores!=0
      Foo t = new Foo(count/cores, threshold);
      list.add(t);
      Thread thread = new Thread(t);
      thread.start();
      threads.add(thread);
    }
    for(Thread t : threads) t.join();
    for(Foo f : list) sum += f.result;

    System.out.println(sum);
  }
}

您还可以优化和内联随机生成器，以避免使用 double 。这是从 ThreadLocalRandom 文档中获取的代码:

  public void run() {
    long seed = new Random().nextLong();
    long limit = (long) ((1L<<48) * threshold);

    for(int i=0; i<count; i++) {
      seed = (seed * 0x5DEECE66DL + 0xBL) & ((1L << 48) - 1);
      if (seed < limit) ++result;
    }
  }

但是，最好的方法是更聪明地工作，而不是更努力地工作。随着事件数量的增加，概率趋于正态分布。这意味着，对于您的巨大范围，您可以随机生成具有这种分布的数字并对其进行缩放:

import java.util.Random;

class StayInSchool {
  public static void main(String[] args) {
    System.out.println(coinToss(1000000000, 0.75));
  }
  static long coinToss(long iterations, double threshold) {
    double mean = threshold * iterations;
    double stdDev = Math.sqrt(threshold * (1-threshold) * iterations);

    double p = new Random().nextGaussian();
    return (long) (p*stdDev + mean);
  }
}

以下是我的 4 核系统(包括 VM 启动)上这些方法的计时:

• 您的基线:20.9 秒
• 单线程ThreadLocalRandom:6.51s
• 单线程优化随机:1.75s
• 多线程ThreadLocalRandom:1.67s
• 多线程优化随机:0.89s
• 生成高斯:0.14s