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

Question

我尝试解决代码强制上的一个问题.我得到了Time limit exceeded判决.唯一耗时的操作是大数组的计算和.所以我试图优化它,但没有结果.

我想要的:优化下一个功能:

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

问题2:为什么optimizedSum工作速度慢canonicalSum？

Answer 1

从Java 9开始,基于测量代码的全部成本加上其编译的基准,已经实现了该操作的矢量化但禁用了该操作.根据您的处理器,这会产生相对有趣的结果,如果您在还原循环中引入人工并发症,您可以触发自动向量化并获得更快的结果!因此,目前最快的代码,假设数字足够小而不会溢出,是:

public int sum(int[] data) {
    int value = 0;
    for (int i = 0; i < data.length; ++i) {
        value += 2 * data[i];
    }
    return value / 2;
}

这不是一个推荐!这更多地说明了Java中代码的速度取决于JIT,它的权衡以及任何给定版本中的错误/特性.编写可爱的代码来优化这样的问题至多是徒劳的,并且会给你编写的代码带来保质期.例如,如果您手动展开循环以针对较旧版本的Java进行优化,那么在Java 8或9中,您的代码会慢得多,因为此决定将完全禁用自动向量化.你最好真的需要这种表现来做到这一点.