java - 为什么相同算法在倍率测试中运行时间不同？

Question

我正在分析蛮力三和算法。假设这个算法的运行时间是T(N)= a N^3。我正在做的是我正在使用 8Kints.txt 运行这个ThreeSum.java程序，并使用该运行时间来计算常数a。计算后我猜测16Kints.txt的运行时间是多少。这是我的ThreeSum.java文件：

    public class ThreeSum {
        public static int count(int[] a) {
            // Count triples that sum to 0.
            int N = a.length;
            int cnt = 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)
                            cnt++;
            return cnt;
        }

        public static void main(String[] args) {
            In in = new In(args[0]);
            int[] a = in.readAllInts();
            Stopwatch timer = new Stopwatch();
            int count = count(a);
            StdOut.println("elapsed time = " + timer.elapsedTime());
            StdOut.println(count);
        }
    }

当我这样运行时：

$ java ThreeSum 8Kints.txt

我明白了：

elapsed time = 165.335

现在在倍率实验中，我在另一个客户端中使用相同的方法并使用多个文件作为参数运行该客户端，并想尝试将8Kints.txt的运行时间与上述方法进行比较，但我得到不同的结果实际上更快的结果。这是我的DoublingRatio.java客户端：

public class DoublingRatio {
    public static double timeTrial(int[] a) {
        Stopwatch timer = new Stopwatch();
        int cnt = ThreeSum.count(a);
        return timer.elapsedTime();
    }

    public static void main(String[] args) {
        In in;
        int[][] inputs = new int[args.length][];

        for (int i = 0; i < args.length; i++) {
            in = new In(args[i]);
            inputs[i] = in.readAllInts();
        }

        double prev = timeTrial(inputs[0]);
        for (int i = 1; i < args.length; i++) {
            double time = timeTrial(inputs[i]);
            StdOut.printf("%6d %7.3f ", inputs[i].length, time);
            StdOut.printf("%5.1f\n", time / prev);
            prev = time;
        }
    }
}

当我像这样运行时：

$ java DoublingRatio 1Kints.txt 2Kints.txt 4Kints.txt 8Kints.txt 16Kints.txt 32Kints.txt

我得到更快的结果，我想知道为什么：

 N      sec   ratio
2000   2.631   7.8
4000   4.467   1.7
8000  34.626   7.8

我知道这与Java而不是算法有关吗？java是否优化了引擎盖下的一些东西。

标签： javaalgorithmperformance