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

Question

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

我说的是小列表，只有几个搜索。转换为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}");
}

在我的机器上，我得到了这些结果。请注意，List上Contains时间与数组之间的比率非常接近 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