当列表和数据长大时
5.00/5 (14投票s)
本文将深入探讨代码有时会变得缓慢的原因之一。
引言
本文将深入探讨代码有时会变得缓慢的原因之一。关于通用且易于实现的“List”列表的用法，以及当迭代元素变得丰富时其用法，可以通过哪些简单步骤实现多重改进，以及当列表不再足够满足性能要求时您可以做什么。本文将为您提供一个示例项目，该项目将在您自己的计算机上实际执行基准测试，如果您愿意，还可以查看代码实现。
背景
当我发现列表在添加之前使用简单的 lambda 表达式进行存在性检查时，我经常会遇到时间窃取者，但这究竟有多糟糕呢？
if (compareMethod == CompareMethod.LinqAnyBothEquals)
{
if (!list.Any(s => s.ID == data.ID && s.Name == data.Name))
list.Add(data);
}
以及我们在易于获得的改进和未来发展方面有哪些选择？
我决定进行测量并提供一些建议，当您遇到列表操作突然花费大量时间时，您应该怎么做，以及何时表明您已经超越了列表数据结构，以及如果您确实希望数据数量增长并重新获得性能，下一步该怎么做。
使用代码
示例代码是一个适用于 VS 2015 的控制台应用程序，其中包含一个 program.cs 文件，其中包含所有内容，以及一个包含少量定向到控制台窗口的实用程序的扩展类。
如果您觉得我的解释过于肤浅，或者只是想亲自观看性能测试运行，您应该使用该项目，它运行几分钟即可完成。
测试计划
这些测试将基于我们虚构的 TestData 派生类 Data1 和 Data2 的样本数据。基类包含两个属性：ID 和 Name。
这些类型的对象使用递增的 id 号和随机的 10 位数字名称进行实例化。
创建包含 1000、10000 和 100000 个元素的此类列表。这些列表模拟了通过随机抽取 25% 的元素进行访问，并且对于每个元素，都随机地决定是否将其从主列表中删除并添加到测试集中，确保之间会有一些全扫描。这并非旨在进行完全相同的运行，而是可比的实际运行。但是，数字会因每次测试运行而略有不同，但分布趋势保持不变。
var sw = new Stopwatch();
("Compare method " + compareMethod).ToConsole();
foreach (var amt in amountsOfData)
{
int manyData = amt;
"".ToConsole();
GetMeAlistWithManyData(rnd, list, pickLength, manyData);
"Get 25 % of data, each element delete or not at random from list".ToConsole();
int aboutTwentyFivePct = (int)(manyData * 0.25);
var arr = new T[aboutTwentyFivePct];
for (int i = 0; i < aboutTwentyFivePct; i++)
{
int pos = rnd.Next(0, list.Count());
arr[i] = list[pos];
if (rnd.Next(0, 1) == 1)
{
list.Remove(arr[i]);
}
}
然后，将尝试将测试集中的每个元素添加回列表结构，并首先检查其是否存在。
将进行实验，以增强 Data 类并优化数据结构功能。
Lambda 罪魁祸首
Lambda 太棒了，它几乎可以让你做任何事情，让你快速生成可工作的代码，但它是通过反射来实现的，这需要一点时间，究竟需要多少时间？
"Testing to add each element, but only if it does not exist".ToConsole();
sw.Start();
foreach (T data in arr)
{
if (compareMethod == CompareMethod.LinqAnyBothEquals)
{
if (!list.Any(s => s.ID == data.ID && s.Name == data.Name))
list.Add(data);
}
else if (compareMethod == CompareMethod.Contains)
{
if (!list.Contains(data))
list.Add(data);
}
else
{
throw new NotImplementedException("This method is not implemented, comparemethod " + compareMethod);
}
}
sw.Stop();
当您处理少于 1000 个元素的数据时，真的不应该太担心使用 Lambda，尽管使用吧！如果它能让您的生活更轻松，我知道它经常能让我的生活更轻松。
| rows | duration |
| 1000 | 10 毫秒 |
| 10000 | 1107 毫秒 |
| 100000 | 69143 毫秒 |
您可以看到，当列表增长时，这些存在性检查变得很昂贵，但嘿！列表有一个 **.Contains** 方法！
Contains 的脆弱性
您可能知道，泛型 List 类型实现了一个 Contains 方法，很容易让人认为您可以使用它来检查列表是否包含该对象。
for (int i = 0; i < 3; i++)
{
Data1 objX = GetNewData(rnd, pickLength);
list.Add(objX);
}
var objValueCopy = new Data1 { ID = list[2].ID, Name = list[2].Name };
if (list.Contains(objValueCopy)){
//jump around!
} else {
//No i'm a reference to a new object with identical values!
}
正如您可能凭借知识或直觉所怀疑的那样，上面的代码中没有跳转，如果没有帮助，Contains 会查找是否已包含该确切对象，而在我们的情况下，这有时才有用。
Contains 是粘土
但是，如果您的 Data 类定义了如何进行比较，您就可以使用 Contains 来以除引用之外的其他方式进行比较，这里 Data2 实现 IEqualityComparer 来定义如何测试该类的相等性。
public class TestData
{
public int ID { get; set; }
public string Name { get; set; }
};
// Plain vanilla dataclass with nothing special to help
public class Data1 : TestData
{
}
/// Implementing IEqualityComparer to help
public class Data2 : Data1, IEqualityComparer, IEqualityComparer
{
public bool Equals(Data2 x, Data2 y)
{
return x.ID == y.ID && x.Name == y.Name;
}
public new bool Equals(object x, object y)
{
if (x is Data2)
{
if (y is Data2)
{
return Equals((Data2)x, (Data2)y);
}
}
return false;
}
public int GetHashCode(Data2 obj)
{
return (ID.ToString() + Name).GetHashCode();
}
public int GetHashCode(object obj)
{
if (obj is Data2)
{
return (obj as Data2).GetHashCode();
}
return obj.GetHashCode();
}
}
现在我们可以使用 Contains 来获得结果了
| rows | duration |
| 1000 | 1 毫秒 |
| 10000 | 186 毫秒 |
| 100000 | 18330 毫秒 |
部分结论
要点一：实现 IEqualityComparer 可以显著提高列表中存在性检查的性能！
要点二：改进体现在小型列表中，并且最初效果最大，因为与 100K+ 数据集相比，比较次数最终仍将是一个主要瓶颈。
要点三：当需要进行包含性检查时，列表在处理大量数据时性能不佳，如果数据量增长，请考虑除列表以外的其他方法。
IEqualityComparer 是王道
许多不同的 CLR 类都支持并使用 IEqualityComparer，另一个性能非常高的数据结构是 HashSet。
sw.Start();
foreach (T data in arr)
{
if (compareMethod == CompareMethod.LinqAnyBothEquals)
{
if (!hashSet.Any(s => s.ID == data.ID && s.Name == data.Name))
hashSet.Add(data);
}
else if (compareMethod == CompareMethod.Contains)
{
if (!hashSet.Contains(data))
hashSet.Add(data);
}
else
{
throw new NotImplementedException("This method is not implemented, comparemethod " + compareMethod);
}
}
sw.Stop();
| rows | duration |
| 1000 | 0 毫秒 |
| 10000 | 0 毫秒 |
| 100000 | 5 毫秒 |
实际上速度非常快，不是吗？
但这仅适用于 Data2 类型的数据对象集，Data1 类型仍然会遇到性能问题。
| rows | duration |
| 1000 | 12 毫秒 |
| 10000 | 754 毫秒 |
| 100000 | 73748 毫秒 |
HashSet 还有其他优势
如果我们无法控制数据类，我们是否就无能为力了？
不，您可以在实例化 HashSet 时指定 EqualityComparer，这样事情就会变得不同。
public class TestDataEqualityComparer : IEqualityComparer
{
public bool Equals(TestData x, TestData y)
{
return x.ID == y.ID && x.Name == y.Name;
}
public int GetHashCode(TestData obj)
{
return (obj.ID.ToString() + obj.Name).GetHashCode();
}
}
将此比较器的实例传递给构造函数并操作 Data1 对象
| rows | duration |
| 1000 | 0 毫秒 |
| 10000 | 1 毫秒 |
| 100000 | 28 毫秒 |
这几乎一样好了！
部分结论
要点四：是否使用 HashSet 并不重要，如果使用 Linq 进行比较，您的结果一样糟糕。
要点五：考虑为大量数据使用 HashSet，如果您无法控制数据类以包含此类内容，请在构造函数中提供 EqualityComparer。
一点建议
在本文中，我讨论了范围包含性检查。值得考虑的是，如果您不想检查相等性，修改数据类是不明智的。您可以辩称从引用相等性转移到值相等性，但例如，如果您只想查看 ID 是否已存在，例如，因为您想更新对象或其值属性可能已更改，而这并非您的程序流所决定。那么您应该创建一个具有有意义名称的比较器，例如传递一个名为 **TestDataIdentityEqualityComparer** 的东西，这样可以使您的代码易于阅读并避免人们在其他上下文中意外使用 Data 类。最好提供自定义比较器，以避免混淆。
结论
如果您使用的泛型列表包含 100 多个元素，并且使用 lambda 表达式在添加时测试具有相同值的现有对象，请考虑改用 HashSet，如果您要处理的数据类未实现 IEqualityComparer，请记住提供一个 EqualityComparer，您的代码将运行得更快。
至于何时是切换的最佳时机，是在 100 个元素还是 1000 个元素时，这一点尚有争议，但我希望已经证明，即使您因为易用性和涉及的数据量而继续使用列表，通过让您的 Data 类实现 IEqualityComparer，您也可以实现显着的性能提升。
历史
这是本文的第一版