Java：如何优化大数组的总和

Question1 [main]: Is it possible to optimize canonicalSum?

是的.但我不知道有什么因素.

你可以做的一些事情是：

>使用Java 8中引入的并行管道.处理器具有执行2个数组(以及更多)的并行求和的指令.当您使用“.”(并行加法)或“”将两个向量相加时,可以在Octave中观察到这种情况.它比使用循环更快.
>使用多线程.你可以使用分而治之的算法.也许是这样的：

>将数组分成2个或更多
>继续递归分割,直到获得一个具有可管理大小的线程的数组.
>开始使用单独的线程计运算符数组(分割数组)的总和.
>最后将所有子阵列生成的总和(从所有线程)添加到一起以产生最终结果

>也许展开循环也会有所帮助.通过循环展开,我的意思是通过手动在循环中执行更多操作来减少循环必须执行的步骤.

http://en.wikipedia.org/wiki/Loop_unwinding的一个例子：

for (int x = 0; x < 100; x++)
{
    delete(x);
}

变

for (int x = 0; x < 100; x+=5)
{
    delete(x);
    delete(x+1);
    delete(x+2);
    delete(x+3);
    delete(x+4);
}

但是如上所述,这必须谨慎和剖析,因为JIT本身可能会进行这种优化.

可以在here中看到用于多线程方法的数学运算的实现.

使用在Java 7中引入的Fork / Join框架的示例实现基本上执行上面的分而治之的算法：

public class ForkJoinCalculator extends RecursiveTask<Double> {

   public static final long THRESHOLD = 1_000_000;

   private final SequentialCalculator sequentialCalculator;
   private final double[] numbers;
   private final int start;
   private final int end;

   public ForkJoinCalculator(double[] numbers,SequentialCalculator sequentialCalculator) {
     this(numbers,numbers.length,sequentialCalculator);
   }

   private ForkJoinCalculator(double[] numbers,int start,int end,SequentialCalculator sequentialCalculator) {
     this.numbers = numbers;
     this.start = start;
     this.end = end;
     this.sequentialCalculator = sequentialCalculator;
   }

   @Override
   protected Double compute() {
     int length = end - start;
     if (length <= THRESHOLD) {
         return sequentialCalculator.computeSequentially(numbers,start,end);
     }
     ForkJoinCalculator leftTask = new ForkJoinCalculator(numbers,start + length/2,sequentialCalculator);
     leftTask.fork();
     ForkJoinCalculator rightTask = new ForkJoinCalculator(numbers,end,sequentialCalculator);
     Double rightResult = rightTask.compute();
     Double leftResult = leftTask.join();
     return leftResult + rightResult;
  }
}

Here we develop a RecursiveTask splitting an array of doubles until
the length of a subarray doesn’t go below a given threshold. At this
point the subarray is processed sequentially applying on it the
operation defined by the following interface

使用的界面是这样的：

public interface SequentialCalculator {
  double computeSequentially(double[] numbers,int end);
}

用法示例：

public static double varianceForkJoin(double[] population){
   final ForkJoinPool forkJoinPool = new ForkJoinPool();
   double total = forkJoinPool.invoke(new ForkJoinCalculator(population,new SequentialCalculator() {
     @Override
     public double computeSequentially(double[] numbers,int end) {
       double total = 0;
       for (int i = start; i < end; i++) {
         total += numbers[i];
       }
       return total;
     }
  }));
  final double average = total / population.length;
  double variance = forkJoinPool.invoke(new ForkJoinCalculator(population,new SequentialCalculator() {
    @Override
    public double computeSequentially(double[] numbers,int end) {
      double variance = 0;
      for (int i = start; i < end; i++) {
        variance += (numbers[i] - average) * (numbers[i] - average);
      }
      return variance;
    }
 }));
 return variance / population.length;
}