基于嵌套列表中包含的id元素比较两个泛型列表的最有效方法(c#)

Question

我有两个通用的项目列表，每个列表包含供应商列表和他们的id:

List<ExisitingItems>
List<Suppliers>
List <PotentialMatches>
List<Suppliers>
Suppliers
SupplierId
Name

我需要根据每个项目中嵌套的供应商id和名称将现有项目列表与潜在匹配项列表进行比较。

我目前将这两个列表与期望的结果进行比较，如下所示:

foreach (var potentialMatch in _potentialMatches)
{
foreach (var supplier in potentialMatch.Suppliers)
{
var match = ExistingItems.Find
(e => e.Suppliers.Any
(s => s.SupplierId == supplier.SupplierItemId && s.Name == supplier.Name));
//Do stuff with match
}
}

但是，当处理大量记录>500k时，效率不高，执行速度很慢。

如何更有效地执行相同类型的比较?

Answer 1

您当前的算法似乎是O(n*m*s*s)，其中n =现有项目的数量，m =潜在匹配的数量，s=每个existingItem/PotentialMatch的供应商的平均数量。您可以通过使用哈希集来匹配供应商，从而将运行时间减少到O(n*m*s)。

一个通用的版本看起来像这样

public static IEnumerable<(T1, T2)> SetJoin<T1, T2, TKey>(
IEnumerable<T1> t1s,
IEnumerable<T2> t2s,
Func<T1, IEnumerable<TKey>> t1Key,
Func<T2, IEnumerable<TKey>> t2Key) where TKey : IEquatable<TKey>
{
foreach (var t1 in t1s)
{
var t1Keys = new HashSet<TKey>(t1Key(t1));
foreach (var t2 in t2s)
{
// t2Key(t2) would be called many times, 
// might be worth pre-computing it for each t2.
if (t2Key(t2).Any(t1Keys.Contains))
{
yield return (t1, t2);
}
}    
}
}

并命名为

SetJoin<ExistingItems, PotentialMatches, int>(
existingItems, 
potentialMatches,
e=> e.Suppliers.Select(s => s.Id),
p => p.Suppliers.Select(s => s.Id))

同样，虽然linq产生的代码紧凑而美观，但如果性能很重要，使用常规循环编写等效逻辑通常会更快。