查找不在列表A中但在列表B中的人员的更快方法

html5 • • 问答

c#

今天我用它来获取不在列表 A 但在列表 B 中的人员列表。它有效，但似乎需要很长时间才能获得结果。有没有更快的方法来做同样的事情？

    var missingPeople = listofPersons.Where(p => allUsedPersons.All(p2 => p2.Id != p.Id)).ToList();

回答

  • 您当前的实现具有O( n * m ) 时间复杂度。

    • n的基数在哪里listofPersons。
    • m的基数在哪里allUsedPersons。
    • 因此，如果您有 500listofPersons和 200，allUsedPersons您的代码将接受 100,000 次检查。那不好。
      • 这是因为LINQ的公司Where将在每个项目上运行listofPersons了，里面你Where你有allUsedPersons.All，这将运行p2.Id != p.Id在每个项目检查allUsedPersons。

  • 相反，使用HashSet<T>建立一套已知值的O(n)时间-然后，您可以执行存在的检查O(1)时间。

    • 所以如果你有 500listofPersons和 200，allUsedPersons我下面的代码将只需要 500 次检查。
    • 100,000 与 500：找出差异。
HashSet<Int32> allPeopleIds = listofPersons.Select( p => p.Id ).ToHashSet();

List<Person> missingPeople = allUsedPersons
    .Where( p => !allPeopleIds.Contains( p.Id ) )
    .ToList();

在关系代数（或者是关系演算？）你在做什么被称为一个反连接和LINQ通过支持它Except的方法，但是你需要定义一个定制的比较作为LINQ的不还具有一种ExceptBy方法（但 MoreLinq 确实如此）。

以上是查找不在列表A中但在列表B中的人员的更快方法的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>