-6

考虑以下两个代码示例。所有基准测试都是在用于计算采样执行时间平均值的容器之外完成的。在我的机器上,运行 Windows 7 和 JDK 1.6,我看到示例 2 中的平均执行时间比示例 1 慢了近 1,000 倍。我可以推测的唯一解释是编译器正在优化 LinkedList 使用的一些代码以其他一切的损害。有人可以帮我理解这一点吗?

示例 1:使用数组

public class TimingTest 
{

    static long startNanos, endNanos;
    static long[] samples = new long[1000];


    public static void main(String[] args) 
    {
    for (int a = 0; a < 100; a++) 
    {
        for (int numRuns = 0; numRuns < 1000; numRuns++) 
        {
            startNanos = System.nanoTime();
            long sum = 0;
            for (long i = 1; i <= 500000; i++) 
            {
                sum += i % 13;
            }
            endNanos = System.nanoTime() - startNanos;
            samples[numRuns] =(endNanos);
        }
        long avgPrim = 0L;
        for (long sample : samples) 
        {
            avgPrim += sample;
        }
        System.out.println("Avg: " + (avgPrim / samples.length) );
        }
    }
}

示例 2:使用 LinkedList

public class TimingTest 
{

    static long startNanos, endNanos;
    static List<Long> samples = new LinkedList<Long>();

    public static void main(String[] args) 
    {
        for (int a = 0; a < 100; a++) 
        {
            for (int numRuns = 0; numRuns < 1000; numRuns++) 
            {
                startNanos = System.nanoTime();
                long sum = 0;
                int index = 0;
                for (long i = 1; i <= 500000; i++) 
                {
                    sum += i % 13;
                }
                endNanos = System.nanoTime() - startNanos;
                samples.add(endNanos);
            }
            long avgPrim = 0L;
            for (long sample : samples) 
            {
                avgPrim += sample;
            }
            System.out.println("Avg: " + (avgPrim / samples.size()));
        }
    }
}
4

2 回答 2

3

这里出了点问题:当我运行数组版本时,我得到的平均执行时间为 20000 纳秒。我的 2 GHz CPU 在那个时候执行 500000 次循环迭代是完全不可能的,因为这意味着平均循环迭代需要 20000/500000 = 0.04 ns,或 0.08 个 cpu cpu 周期......

主要原因是您的时序逻辑中的错误:在数组版本中,您可以

int index = 0;

对于每个时间,因此

samples[index++] =(endNanos);

将始终分配给第一个数组元素,将所有其他元素保留为默认值 0。因此,当您取数组的平均值时,您会得到最后一个样本的 1/1000,而不是所有样本的平均值。

实际上,如果您将 index 声明移到循环之外,则不会报告两个变体之间的显着差异。

于 2013-01-14T00:51:50.727 回答
0

这是您的代码的真实运行(为了清楚起见,重命名了类,并a < 1为了时间的缘故将每个类中的外部 for 循环剪掉了):

$ for f in *.class
do
  class=$(echo $f | sed 's`\(.*\)\.class`\1`')
  echo Running $class
  java $class
done
Running OriginalArrayTimingTest
Avg: 18528
Running UpdatedArrayTimingTest
Avg: 41111273
Running LinkedListTimingTest
Avg: 41340483

显然,您最初的担忧是由@meriton 指出的错字引起的,您在问题中更正了该错字。我们可以看到,对于您的测试用例,数组和 LinkedList 的行为几乎相同。一般来说,对 LinkedList 的插入非常快。由于您使用 Meriton 的更改更新了您的问题,但没有更新您声称前者比后者快得多的说法,因此您不再清楚您在问什么;但是我希望您现在可以看到,在这种情况下,两种数据结构的行为都相当相似。

于 2013-03-04T05:43:04.970 回答