Java：如何优化大数组求和

Question

//array could be Integer.MAX_VALUE length
private long canocicalSum(int[] array) { 
    int sum = 0;
    for (int i = 0; i < array.length; i++)
        sum += array[i];
    return sum;
}

问题1[主]:是否可以优化canonicalsum？

我尝试过：避免使用非常大的数字的操作。所以我决定使用辅助数据。例如，我将array1[100]转换为array2[10]，其中array2[I]=array1[I]+array1[I+1]+array1[I+9]。

private long optimizedSum(int[] array, int step) {
    do {
        array = sumItr(array, step);
    } while (array.length != 1);
    return array[0];
}

private  int[] sumItr(int[] array, int step) {
    int length = array.length / step + 1;
    boolean needCompensation = (array.length % step == 0) ? false : true;
    int aux[] = new int[length];
    for (int i = 0, auxSum = 0, auxPointer = 0; i < array.length; i++) {
        auxSum += array[i];
        if ((i + 1) % step == 0) {
            aux[auxPointer++] = auxSum;
            auxSum = 0;
        }
        if (i == array.length - 1 && needCompensation) {
            aux[auxPointer++] = auxSum;
        }
    }
    return aux;
}

问题：但是canonicalsum似乎比optimizedsum快十倍。这里是我的测试：

@Test
public void sum_comparison() {
    final int ARRAY_SIZE = 100000000;
    final int STEP = 1000;
    int[] array = genRandomArray(ARRAY_SIZE);

    System.out.println("Start canonical Sum");
    long beg1 = System.nanoTime();
    long sum1 = canocicalSum(array);
    long end1 = System.nanoTime();
    long time1 = end1 - beg1;
    System.out.println("canon:" + TimeUnit.MILLISECONDS.convert(time1, TimeUnit.NANOSECONDS) + "milliseconds");

    System.out.println("Start optimizedSum");
    long beg2 = System.nanoTime();
    long sum2 = optimizedSum(array, STEP);
    long end2 = System.nanoTime();
    long time2 = end2 - beg2;
    System.out.println("custom:" + TimeUnit.MILLISECONDS.convert(time2, TimeUnit.NANOSECONDS) + "milliseconds");

    assertEquals(sum1, sum2);
    assertTrue(time2 <= time1);
}

private int[] genRandomArray(int size) {
    int[] array = new int[size];
    Random random = new Random();
    for (int i = 0; i < array.length; i++) {
        array[i] = random.nextInt();
    }
    return array;
}

Answer 1

问题1[主]:是否可能优化CanonicalSum？

是的，是的。但我不知道是什么因素造成的。

您可以做的一些事情是：

null

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);
}

这里可以看到多线程方法的数学运算的实现。

Java7中引入的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, 0, 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, start + length/2, sequentialCalculator);
     leftTask.fork();
     ForkJoinCalculator rightTask = new ForkJoinCalculator(numbers, start + length/2, end, sequentialCalculator);
     Double rightResult = rightTask.compute();
     Double leftResult = leftTask.join();
     return leftResult + rightResult;
  }
}

在这里，我们开发了一个recursivetask来拆分一个数组，直到子数组的长度不低于给定的阈值。此时，子数组将按顺序进行处理，并对其应用由以下接口定义的操作

public interface SequentialCalculator {
  double computeSequentially(double[] numbers, int start, 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 start, 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 start, 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;
}