Linq 包含：列表与数组的性能

Question

在我的程序中，我有一个整数数组 (int[])。稍后我需要向列表中添加更多整数。这就是我将数组转换为 List<int> 的原因。我想知道我应该在哪个 Enumerable 上应用我需要的 Contains 调用。

我说的是小列表，只有几次搜索。转换为 HashSet 开销太大。

理论上，在列表和数组中查找特定项目的复杂度为 O(n)。在找到想要的项目之前，平均 n/2 项需要迭代和检查。

我很好奇这个理论在实践中是否也成立。所以我的问题是：对于小数据集，List<int>.Contains() 和 int[].Contains() 之间是否存在明显的性能差异？

Answer 1

我创建了一个测试方法显示：

使用随机数据时两者之间没有可测量的差异。

此处的测试代码使用随机生成器插入并调用 Contains 随机数据以获得 List。然后重置随机生成器并插入相同的序列，然后在数组上查询。

var seedGenerator = new Random();
const int RunsPerRound = 10;
int[] itemsPerRound = { 10, 20, 30, 40, 50, 100, 1000, 2000, 3000, 4000, 5000, 10000, 20000 };
foreach (var items in itemsPerRound)
{
    var runsPerRound = RunsPerRound;
    // For very small test sets, increase number of runs
    if (items < 100)
        runsPerRound = 1000;
    int totalRoundItems = items * runsPerRound;
    long totalRoundTicksList = 0;
    long totalRoundTicksArray = 0;
    for (int i = 0; i < runsPerRound; i++)
    {
        // List
        int seed = seedGenerator.Next();
        var r = new Random(seed);
        var list = new List<int>(items);
        for (int j = 0; j < items; j++)
            list.Add(r.Next());
        var sw = new System.Diagnostics.Stopwatch();
        sw.Start();
        for (int j = 0; j < items; j++)
            list.Contains(r.Next());
        sw.Stop();
        totalRoundTicksList += sw.ElapsedTicks;

        // Array
        r = new Random(seed);
        var array = new int[items];
        for (int j = 0; j < items; j++)
            array[j] = r.Next();
        sw.Reset();
        sw.Start();
        for (int j = 0; j < items; j++)
            list.Contains(r.Next());
        sw.Stop();
        totalRoundTicksArray += sw.ElapsedTicks;
    }

    double perItemTicksList = totalRoundTicksList / totalRoundItems;
    double perItemTicksArray = totalRoundTicksArray / totalRoundItems;
    double ticksRatio = (double)totalRoundTicksList / totalRoundTicksArray;
    Console.WriteLine($"ItemsPerRound {items}:\tList:{totalRoundTicksList}\tArray:{totalRoundTicksArray}\tRatio:{ticksRatio:0.###}\tListPerItem:{perItemTicksList}\tArrayPerItem:{perItemTicksArray}");
}

在我的机器上我得到了这些结果。请注意，Contains 在 List 上的时间与数组的时间之比非常接近 1。

ItemsPerRound 10:       List:1576       Array:1373      Ratio:1.148     ListPerItem:0   ArrayPerItem:0
ItemsPerRound 20:       List:3640       Array:4203      Ratio:0.866     ListPerItem:0   ArrayPerItem:0
ItemsPerRound 30:       List:7617       Array:7652      Ratio:0.995     ListPerItem:0   ArrayPerItem:0
ItemsPerRound 40:       List:12675      Array:12565     Ratio:1.009     ListPerItem:0   ArrayPerItem:0
ItemsPerRound 50:       List:19381      Array:19098     Ratio:1.015     ListPerItem:0   ArrayPerItem:0
ItemsPerRound 100:      List:664        Array:616       Ratio:1.078     ListPerItem:0   ArrayPerItem:0
ItemsPerRound 1000:     List:57581      Array:56698     Ratio:1.016     ListPerItem:5   ArrayPerItem:5
ItemsPerRound 2000:     List:239500     Array:259884    Ratio:0.922     ListPerItem:11  ArrayPerItem:12
ItemsPerRound 3000:     List:547807     Array:526768    Ratio:1.04      ListPerItem:18  ArrayPerItem:17
ItemsPerRound 4000:     List:1059016    Array:1023493   Ratio:1.035     ListPerItem:26  ArrayPerItem:25
ItemsPerRound 5000:     List:1402850    Array:1385418   Ratio:1.013     ListPerItem:28  ArrayPerItem:27
ItemsPerRound 10000:    List:5814664    Array:5888034   Ratio:0.988     ListPerItem:58  ArrayPerItem:58
ItemsPerRound 20000:    List:22417904   Array:22015204  Ratio:1.018     ListPerItem:112 ArrayPerItem:110

Linq 包含：列表与数组的性能

Linq Contains: Performance on list vs array

contains