列表 A 中存在但列表 B 中不存在的性能项
3.91/5 (8投票s)
列表 A 中存在但列表 B 中不存在的性能项。
目录
引言
在阅读了一些 Stack Overflow 上关于如何在 List A 中查找不在 List B 中的元素，以及一些解决方案的性能问题（并在现实生活中遇到了这些性能问题）的帖子后，我决定研究如何创建一个高性能的 “not in” 方法，以满足我的需求，即我不比较简单的值类型，而是比较不同类中的一个属性（或多个属性）。
请注意，我忽略了整个“覆盖 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 扩展方法，它非常非常快。因此，给定一个简单的值列表，我们可以获得 list A 中不在 list 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 方法编写 “not in” 函数
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 方法的性能。
一个高性能的 List A 不在 List B 中
因此，在我的最终实现中，我可以使用选择器并使用 Except 方法，为给定的选择器返回不在 B 中的 A 实例。使用
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 日：初始版本