Linq'包含'查询耗时太长

Question

我有这个问题:

var newComponents = from ic in importedComponents
                    where !existingComponents.Contains(ic)
                    select ic;

importedComponents并且existingComponents是类型的List<ImportedComponent>,并且仅存在于存储器中(不依赖于数据上下文).在这个例子中,importedComponents有超过6,100项,并existingComponents有511项.

这句话花了太长时间才完成(我不知道多久,我在20分钟后停止了剧本).我尝试了以下但没有提高执行速度:

var existingComponentIDs = from ec in existingComponents
                           select ec.ID;

var newComponents = from ic in importedComponents
                    where !existingComponentIDs.Contains(ic.ID)
                    select ic;

任何帮助都感激不尽.

Answer 1

问题是该算法的二次复杂性.将所有existingComponentID的ID放入HashSet并使用HashSet.Contains方法.与列表中的Contains/Any的O(N)相比,它具有O(1)查找成本.

该morelinq项目包含所有做的是,在一个方便的步骤的方法:ExceptBy.

Answer 2

您可以使用以下方法Except来获取设置的差异：

var existingComponentIDs = existingComponents.Select(c => c.ID); 
var importedComponentIDs = importedComponents.Select(c => c.ID);
var newComponentIDs = importedComponentIDs.Except(existingComponentIDs);
var newComponents = from ic in importedComponents
        join newID in newComponentIDs on ic.ID equals newID
        select ic;
foreach (var c in newComponents)
{ 
    // insert into database?
}

为什么 LINQ JOIN 比 WHERE 链接快得多？

简而言之：Join方法可以建立一个哈希表作为索引来快速将两个表压缩在一起