为何不同迭代步长下ThreeSum算法单次耗时差异大但总耗时相近？

注意：本代码使用的是普林斯顿大学的标准算法库，所用类/函数语义清晰易懂。

暴力三数之和计数算法 #

以下是统计输入数组中和为0的三元组数量的暴力实现：

public static int count(int[] a) {
    int n = a.length;
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if (a[i] + a[j] + a[k] == 0) {
                    count++;
                }
            }
        }
    }
    return count;
}

两种测试方式及结果 #

方式一：步长250迭代（从250到4000） #

测试代码：

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.Stopwatch;

public class DoublingTest {
    public static double timeTrial(int N) {
        int MAX = 1000000;
        int[] a = new int[N];
        for (int i = 0; i < N; i++)
            a[i] = StdRandom.uniform(-MAX, MAX);
        Stopwatch timer = new Stopwatch();
        int cnt = ThreeSum.count(a);
        return timer.elapsedTime();
    }

    public static void main(String[] args) {
        double total = 0;
        for (int i = 250; i <= 4000; i += 250) {
            double time = timeTrial(i);
            total += time;
            StdOut.printf("%7d %5.2f", i, time);
            StdOut.printf("Total time = %5.2f\n", total);
        }
    }
}

测试输出（仅展示到i=4000的结果）：

250  0.03
Total time =  0.03
    500  0.10
Total time =  0.13
    750  0.43
Total time =  0.56
   1000  0.95
Total time =  1.51
   1250  1.80
Total time =  3.31
   1500  3.12
Total time =  6.44
   1750  1.11
Total time =  7.55
   2000  1.65
Total time =  9.20
   2250  2.35
Total time = 11.54
   2500  3.19
Total time = 14.74
   2750  4.26
Total time = 18.99
   3000  5.51
Total time = 24.50
   3250  6.99
Total time = 31.50
   3500  8.73
Total time = 40.23
   3750 10.66
Total time = 50.88
   4000 12.91
Total time = 63.80

方式二：翻倍迭代（从250到4000） #

测试代码：

import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.Stopwatch;

public class DoublingTest {
    public static double timeTrial(int N) {
        int MAX = 1000000;
        int[] a = new int[N];
        for (int i = 0; i < N; i++)
            a[i] = StdRandom.uniform(-MAX, MAX);
        Stopwatch timer = new Stopwatch();
        int cnt = ThreeSum.count(a);
        return timer.elapsedTime();
    }

    public static void main(String[] args) {
        double total = 0;
        for (int i = 250; i <= 4000; i *= 2) {
            double time = timeTrial(i);
            total += time;
            StdOut.printf("%7d %5.2f", i, time);
            StdOut.printf("Total time = %5.2f\n", total);
        }
    }
}

测试输出：

250  0.04
Total time =  0.04
    500  0.12
Total time =  0.16
   1000  0.96
Total time =  1.11
   2000  7.38
Total time =  8.50
   4000 59.22
Total time = 67.71

耗时差异的原因解析 #

两种方式下i=4000的单次耗时差距巨大，但总耗时却相近，核心原因有三点：

1. CPU缓存的预热与命中率差异 #

方式一从小规模数组开始逐步测试，多次运行后，CPU的指令缓存和数据缓存完成预热——代码段被缓存到高速缓存，小数组也更容易被完全缓存。后续测试大数组时，缓存命中率更高，单个运算的耗时被显著降低。

而方式二每次直接翻倍数组规模，数组大小突然跃变，缓存需要重新加载大量数据，大数组无法完全放入高速缓存，导致缓存命中率骤降，内存访问耗时大幅增加，最终表现为i=4000的单次耗时远超方式一。

2. 随机数组的三元组数量差异 #

每次测试的数组都是随机生成的，不同数组中和为0的三元组数量差异很大：三元组数量越多，count++的执行次数就越多，分支预测的压力也越大，整体耗时会明显增加。

方式二中的4000规模数组恰好包含更多符合条件的三元组，导致单次测试耗时陡增；而方式一中的多个测试数组的三元组数量分布更平均，总耗时被分摊，最终与方式二的总耗时拉平。

3. 总运算量与实际耗时的抵消 #

从时间复杂度看，暴力三数之和是O(n³)：

• 方式一到4000时，总运算量是250³×(1³+2³+...+16³)=250³×18496
• 方式二到4000时，总运算量是250³×(1+8+64+512+4096)=250³×4681

方式一的运算量是方式二的近4倍，但由于缓存预热带来的效率提升，以及方式二大数组的缓存低效，两者的总耗时被抵消到相近水平。

内容的提问来源于stack exchange，提问作者oresky