用Java测量排序时间

我写了一个程序来测试和验证"插入排序"的运行时间，它应该是O（n^2）。在我看来，输出并不正确，而且不同的运行之间似乎没有太大差异。另一件奇怪的事情是，第二次通过总是最小的。我预计每次运行程序时都会有更大的差异，但运行时间似乎没有我预期的那么波动。我只是想知道JVM或编译器是否正在进行某种优化或做一些事情。我在C#中有类似的代码，它似乎变化更大，输出如预期。我不希望每次运行时间都是平方的，但我希望它们比实际增加得更多，我当然希望在最后一次迭代时会有更大的方差。

样本输出（它的变化不足以让我包括多个输出）：

47
20（这个总是最低的……毫无意义！）
44
90
133
175
233
298
379

490

public class SortBench {
public static void main(String args[]){
    Random rand = new Random(System.currentTimeMillis());
    for(int k = 100; k <= 1000; k += 100)
    {
        //Keep track of time
        long time = 0;
        //Create new arrays each time
        int[] a = new int[k];
        int[] b = new int[k];
        int[] c = new int[k];
        int[] d = new int[k];
        int[] e = new int[k];
        //Insert random integers into the arrays
        for (int i = 0; i < a.length; i++)
        {
            int range = Integer.MAX_VALUE;
            a[i] = rand.nextInt(range);
            b[i] = rand.nextInt(range);
            c[i] = rand.nextInt(range);
            d[i] = rand.nextInt(range);
            e[i] = rand.nextInt(range);
        }
        long start = System.nanoTime();
        insertionSort(a);
        long end = System.nanoTime();
        time += end-start;
        start = System.nanoTime();
        insertionSort(b);
        end = System.nanoTime();
        time += end-start;
        start = System.nanoTime();
        insertionSort(c);
        end = System.nanoTime();
        time += end-start;
        start = System.nanoTime();
        insertionSort(d);
        end = System.nanoTime();
        time += end-start;
        start = System.nanoTime();
        insertionSort(e);
        end = System.nanoTime();
        time += end-start;
        System.out.println((time/5)/1000);
    }
}
    static void insertionSort(int[] a)
    {
        int key;
        int i;
        for(int j = 1; j < a.length; j++)
        {
            key = a[j];
            i = j - 1;
            while(i>=0 && a[i]>key)
            {
                a[i + 1] = a[i];
                i = i - 1;
            }
            a[i + 1] = key;
        }
    }
}

在您的第一次迭代中，您还测量JIT时间（或者至少一些JIT时间-HotSpot将进一步优化）。先运行几次，然后开始测量。我怀疑随着时间的推移，您已经看到了HotSpot的好处——早期的测试由于JIT和所花费的时间以及它没有作为最佳代码运行的事实而减慢。（与.NET相比，JIT只运行一次-没有渐进式优化。）

如果可以，也先分配所有内存，并确保在结束之前没有垃圾收集。否则，您将在时间安排中包含分配和GC。

您还应该考虑尝试采集更多的样本，使n上升另一个数量级，以更好地了解时间是如何增加的。（我还没有仔细研究你所做的，以确定它是否真的应该是O（n²）。）

在定时区域之前预热JVM对函数、内存分配器、TLB、CPU频率等的JIT优化。

在RNG播种后，在现有计时循环之前添加一些无计时呼叫。

Random rand = new Random(System.currentTimeMillis()); 
// warmup
for(int k = 100; k <= 10000; k += 100) 
{
    int[]w = new int[1000];
    for (int i = 0; i < w.length; i++) 
    { 
       int range = Integer.MAX_VALUE; 
       w[i] = rand.nextInt(range); 
       insertionSort(w);
     }
 }

升温后的结果：

未加温的结果：

相关内容

最新更新

热门标签：