链表插入速度

Question

在性能测试时，我注意到一些有趣的事情。

我注意到第一次插入 LinkedList（C# 泛型）比在列表头部完成的任何其他插入要慢得多。我只是使用了 C# 模板 LinkedList，并使用 AddFirst() 来每次插入 LinkedList。为什么第一次插入最慢？

---

前五个插入结果：

第一次插入列表：0.0152毫秒

第二次插入列表（在头部）：0.0006毫秒

第三次插入列表（在头部）：0.0003毫秒

第四次插入插入列表（在头部）：0.0006 毫秒

第五次插入列表（在头部）：0.0006 毫秒

性能测试代码：

        using (StreamReader readText = new StreamReader("MillionNumbers.txt"))
        {
            String line;
            Int32 counter = 0; 
            while ((line = readText.ReadLine()) != null)
            {

                watchTime.Start();
                theList.AddFirst(line);
                watchTime.Stop();
                Double time = watchTime.Elapsed.TotalMilliseconds;
                totalTime = totalTime + time; 
                Console.WriteLine(time);
                watchTime.Reset();
                ++counter; 
            }
            Console.WriteLine(totalTime);
            Console.WriteLine(counter);
            Console.WriteLine(totalTime / counter); 
        }

Answer 1

为单个操作计时是非常危险的——最轻微的卡顿都会对结果产生巨大的影响。此外，不清楚在此代码之前您是否已使用 LinkedList 完成任何操作，这意味着您需要对 AddFirst 甚至可能涉及整个其他类型。

仅对第一次插入进行计时相当困难，因为一旦完成，就无法轻易重复。但是，您可以重复“插入和删除”的时间，就像这段代码所做的那样：

using System;
using System.Collections.Generic;
using System.Diagnostics;

class Program
{
    public static void Main(string[] args)
    {
        // Make sure we've JITted the LinkedList code
        new LinkedList<string>().AddFirst("ignored");

        LinkedList<string> list = new LinkedList<string>();        
        TimeInsert(list);
        list.AddFirst("x");
        TimeInsert(list);
        list.AddFirst("x");
        TimeInsert(list);
        list.AddFirst("x");        
    }

    const int Iterations = 100000000;

    static void TimeInsert(LinkedList<string> list)
    {
        GC.Collect();
        GC.WaitForPendingFinalizers();

        Stopwatch sw = Stopwatch.StartNew();
        for (int i = 0; i < Iterations; i++)
        {
            list.AddFirst("item");
            list.RemoveFirst();
        }
        sw.Stop();

        Console.WriteLine("Initial size: {0}; Ticks: {1}",
                           list.Count, sw.ElapsedTicks);
    }
}

我的结果：

Initial size: 0; Ticks: 5589583
Initial size: 1; Ticks: 8137963
Initial size: 2; Ticks: 8399579

这是我所期望的，因为根据内部表示，在连接“前一个头”方面还需要做更多的工作" 在添加和删除已填充的列表时。

我的猜测是您看到的是 JIT 时间，但实际上您的代码的时间不够准确，无法发挥作用，IMO。