列表 A 中存在但列表 B 中不存在的性能项
3.91/5 (8投票s)
列表 A 中存在但列表 B 中不存在的性能项。
目录
引言
在阅读了一些 Stack Overflow 上关于如何查找 A 列表中不在 B 列表中的项目，以及某些解决方案的性能问题（并在现实生活中遇到这些性能问题）的帖子后，我决定研究如何创建一个高性能的 "不在其中" 方法，以满足我的要求，即我不是在比较简单的值类型，而是在比较不同类中的属性（或多个属性）。
请注意，我忽略了整个 "重写 Equals 和 GetHashCode" 的概念，因为它没有为解决方案添加任何东西。
测试设置
我的测试设置创建了 5000 个整数条目，0-4999，以及另外 5000 个条目，5000-9999，在几个列表中，这样我就可以测试直接值比较和包含在简单测试类中的属性中的值。
鉴于
class A
{
public int Value { get; set; }
}
class B
{
public int Value { get; set; }
}
和
static List<A> listOfA;
static List<B> listOfB;
static List<int> listA;
static List<int> listB;
static int samples = 5000;
static int repeat = 10;
测试用例如下设置：
<a>public static void CreateTestData(int samples)
{
listA = new List<int>();
listB = new List<int>();
listOfA = new List<A>();
listOfB = new List<B>();
samples.ForEach(n => listA.Add(n));
samples.ForEach(n => listB.Add(n + samples));
samples.ForEach(n => listOfA.Add(new A() { Value = n }));
samples.ForEach(n => listOfB.Add(new B() { Value = n + samples }));
}
运行测试
测试了几种不同的实现以了解它们的性能
static void Main(string[] args)
{
CreateTestData(samples);
Test("Except", ValueNotInUsingExcept);
Test("Where", ValueNotInUsingWhere);
Test("NotIn with Equals", ValueNotInUsingEquals);
Test("NotIn with Comparitor", ValueNotInUsingComparitor);
Test("NotIn with Selector and Comparitor", ValueNotInUsingSelectorAndComparitor);
Test("HashedNotIn with Selector and Comparitor",
ValueNotInUsingHashedSelectorAndComparitor);
Test("ExceptNotIn with Selector and Comparitor", ValueNotInUsingExceptSelector);
Console.WriteLine("\r\nDone.\r\nPress ENTER to close window.");
Console.ReadLine();
}
以及运行测试的支持代码，其想法是运行每个测试 10 次，并平均每个测试的运行时间
public static void Test(string msg, Action action)
{
var avg = repeat.Average(() => Timing.Time(action));
Console.WriteLine($"{msg}: {avg}ms");
}
和
public static decimal Average(this int n, Func<long> func)
{
long count = 0;
n.ForEach(() => count += func());
decimal avg = count / (decimal)n;
return avg;
}
我们使用内置的 Stopwatch 类
static class Timing
{
public static long Time(Action action)
{
Stopwatch sw = new Stopwatch();
sw.Start();
action();
sw.Stop();
return sw.ElapsedMilliseconds;
}
}
Except 方法
Linq 有一个非常棒的 Except 扩展方法，它非常快。 因此，给定一个简单的值列表，我们可以获得列表 A 中不在列表 B 中的项目
public static void ValueNotInUsingExcept()
{
// force evaluation with ToList()
var items = listA.Except(listB).ToList();
Assertion.Assert(items.Count == samples, $"Expected {samples}.");
}
而且它真的很快
Except: 2.2ms
使用 Where
我遇到的一个建议是使用 Linq 的 Where 方法编写 "不在其中" 函数
public static void ValueNotInUsingWhere()
{
// force evaluation with ToList()
var items = listA.Where(a => !listB.Any(b => a == b)).ToList();
Assertion.Assert(items.Count == samples, $"Expected {samples}.");
}
我们可以立即开始看到性能下降：Where: 290.2ms
创建扩展方法
当我们创建一个扩展方法时，性能会进一步下降，这迫使我们使用 Equals 方法。 给定
public static void ValueNotInUsingEquals()
{
// force evaluation with ToList()
var items = listA.NotIn(listB).ToList();
Assertion.Assert(items.Count == samples, $"Expected {samples}.");
}
实现为
public static IEnumerable<T> NotIn<T>
(this IEnumerable<T> listA, IEnumerable<T> listB) where T : struct
{
var items = listA.Where(a => !listB.Any(b => a.Equals(b)));
return items;
}
性能变得更糟
NotIn with Equals: 426.5ms
但是，我将继续使用扩展方法，因为我们将在稍后讨论最终目标。
提供比较器
有趣的是，提供比较器可以提高性能。 给定
public static void ValueNotInUsingComparitor()
{
// force evaluation with ToList()
var items = listA.NotIn(listB, (a, b) => a == b).ToList();
Assertion.Assert(items.Count == samples, $"Expected {samples}.");
}
实现为
public static IEnumerable<T> NotIn<T>
(this IEnumerable<T> listA, IEnumerable<T> listB, Func<T, T, bool> comparitor)
{
var items = listA.Where(a => !listB.Any(b => comparitor(a, b)));
return items;
}
我们看到略有改善
NotIn with Comparitor: 348.4ms
添加选择器
现在让我们添加选择器，以从类的属性中提取我们要比较的值。 给定
public static void ValueNotInUsingSelectorAndComparitor()
{
// force evaluation with ToList()
var items = listOfA.NotIn(listOfB, a => a.Value, b => b.Value, (a, b) => a == b).ToList();
Assertion.Assert(items.Count == samples, $"Expected {samples}.");
}
实现为
public static IEnumerable<A> NotIn<A, B, Q>(this IEnumerable<A> source,
IEnumerable<B> target, Func<A, Q> sourceSelector, Func<B, Q> targetSelector,
Func<Q, Q, bool> comparitor)
{
var items = source.Where(s => !target.Any
(t => comparitor(sourceSelector(s), targetSelector(t))));
return items;
}
性能显著下降
NotIn with Selector and Comparitor: 711.1ms
使用 HashSet
如果我们使用 HashSet 作为列表 "B" 目标
public static void ValueNotInUsingHashedSelectorAndComparitor()
{
// force evaluation with ToList()
var items = listOfA.HashedNotIn(listOfB, a => a.Value,
b => b.Value, (a, b) => a == b).ToList();
Assertion.Assert(items.Count == samples, $"Expected {samples}.");
}
实现为
public static IEnumerable<A> HashedNotIn<A, B, Q>(this IEnumerable<A> source,
IEnumerable<B> target, Func<A, Q> sourceSelector, Func<B, Q> targetSelector,
Func<Q, Q, bool> comparitor)
{
var hashedTargets = new HashSet<Q>(target.Select(t => targetSelector(t)));
var items = source.Where(s => !hashedTargets.Any(t => comparitor(sourceSelector(s), t)));
return items;
}
我们实际上看到了略微的性能提升
HashedNotIn with Selector and Comparitor: 524.2ms
但这仍然远远低于 Except 方法的性能。
高性能的 A 列表中不在 B 列表中的项目
因此，在我的最终实现中，我可以使用选择器并使用 Except 方法，为给定选择器返回 A 中不在 B 中的实例。 使用
public static void ValueNotInUsingExceptSelector()
{
// force evaluation with ToList()
var items = listOfA.ExceptNotIn(listOfB, a => a.Value, b => b.Value).ToList();
Assertion.Assert(items.Count == samples, $"Expected {samples}.");
}
实现为
/// <summary>
/// Will only return a single entry of A when A1 and A2 select the same value.
/// </summary>
public static IEnumerable<A> ExceptNotIn<A, B, Q>(this IEnumerable<A> source,
IEnumerable<B> target, Func<A, Q> sourceSelector, Func<B, Q> targetSelector)
{
Dictionary<Q, A> dict = new Dictionary<Q, A>();
var evaldSource = source.Select(s =>
{
var val = sourceSelector(s);
dict[val] = s;
return val;
}).ToList();
var targets = target.Select(t => targetSelector(t));
var qitems = evaldSource.Except(targets);
var items = qitems.Select(q => dict[q]);
return items;
}
突然，我们获得了与使用值类型的 Except 方法相同的性能
ExceptNotIn with Selector and Comparitor: 1.4ms
考虑到创建字典和调用选择器所做的工作，这相当令人印象深刻。
这里的魔力在于我们
- 创建一个 "选择的源值" 映射到源实例的字典。
- 预先选择所有目标值。
- 使用给定值的
Except方法。 - 根据返回的值返回源实例。
正如评论所示，如果您有两个具有相同 "选择值" 的源实例，您将只会获得一个源实例。 我可以接受这一点，因为我通常知道我的源实例值是不同的。
结论
我能说什么呢？ 绝对有必要调查 Linq 在一个人使用 Linq 的上下文中的性能！
历史
- 2021 年 1 月 30 日：初始版本