如何比较两个在C＃高效分选大名单？

Question

我有两个泛型列表在各列表20000-30000对象。

class Employee 
{ 
    string name; 
    double salary; 
} 

List<Employee> newEmployeeList = List<Employee>() {....} // contains 20,000 objects 
List<Employee> oldEmployeeList = List<Employee>() {....} // contains 30,000 objects 

列表也可以通过名字，如果它发展的速度进行排序。

我想比较这两个列表，找出

1. 员工的姓名和工资匹配
2. 员工，其名称匹配，但没有薪水

什么是比较的最快方法这样的大数据列表具有上述条件？

Answer 1

我会同时排序newEmployeeList和oldEmployeeList列表name - O(n*log(n))。然后你可以使用线性算法来搜索匹配。所以总数是O(n+n*log(n))如果两个列表都差不多大小。这应该是比O(n^2)“蛮力”算法快。

Answer 2

最快的一个可能的解决方案上分类列表是为了找到另一个列表中的项目使用的BinarySearch。

但作为mantioned别人，你应该衡量它针对您项目要求，往往表现往往是一个主观事情。

Answer 3

，如果你从一个循环比其他查找值，您可以创建使用

var lookupDictionary = list1.ToDictionary(x=>x.name); 

的字典，这些会给你接近O（1）查找和接近O（n）的行为名单。

（我在这里假设ToDictionary是O（n），这将使感有直接的实现，但我没有测试这是这种情况）

这将使一个非常简单的算法，并且我在考虑使用两个未排序的列表在O（n）之下很难。

Answer 4

我可能会建议将这两个列表存储在基于名称的Dictionary<string, Employee>开头，然后您可以迭代一个键并查找它们是否存在，以及工资是否匹配。这还可以节省后期对它们进行分类或将它们置于更有效的结构中的成本。

这是几乎为O（n） - 线性建立两个字典，线性要经过其他的按键和查找。由于O（N + M + N）降低到O（n）的

但，如果你必须使用List<T>持有其他原因的列表，你也可以使用Join() LINQ方法，并建立一个新的列表用Match场，告诉你他们是否是匹配或不匹配......

 var results = newEmpList.Join(
      oldEmpList, 
      n => n.Name, 
      o => o.Name, 
      (n, o) => new 
       { 
        Name = n.Name, 
        Salary = n.Salary, 
        Match = o.Salary == n.Salary 
       }); 

然后，您可以与Match或!Match一个Where()条款过滤此。

Answer 5

更新：我假设（通过您的问题的标题）2列表已经排序。也许他们存储在一个聚集索引或其他东西的数据库中。因此，这个答案依赖于这个假设。

这是一个具有O(n)复杂性的实现，并且速度也非常快，而且非常简单。
我相信这是Merge Algorithm的变种。

这里的想法：

1. 开始列举两个列表
2. 比较2个当前项目。
3. 如果它们匹配，请添加到结果中。
   如果第一个项目是“较小”，则推进第一个列表。
   如果第二项是“较小”，则推进第二项列表。

由于这两个列表已知是排序的，这将工作得很好。此实现假定name在每个列表中都是唯一的。

var comparer = StringComparer.OrdinalIgnoreCase; 
var namesAndSalaries = new List<Tuple<Employee, Employee>>(); 
var namesOnly = new List<Tuple<Employee, Employee>>(); 

// Create 2 iterators; one for old, one for new: 
using (IEnumerator<Employee> A = oldEmployeeList.GetEnumerator()) { 
    using (IEnumerator<Employee> B = newEmployeeList.GetEnumerator()) { 
     // Start enumerating both: 
     if (A.MoveNext() && B.MoveNext()) { 
      while (true) { 
       int compared = comparer.Compare(A.Current.name, B.Current.name); 
       if (compared == 0) { 
        // Names match 
        if (A.Current.salary == B.Current.salary) { 
         namesAndSalaries.Add(Tuple.Create(A.Current, B.Current)); 
        } else { 
         namesOnly.Add(Tuple.Create(A.Current, B.Current)); 
        } 
        if (!A.MoveNext() || !B.MoveNext()) break; 
       } else if (compared == -1) { 
        // Keep searching A 
        if (!A.MoveNext()) break; 
       } else { 
        // Keep searching B 
        if (!B.MoveNext()) break; 
       } 

      } 
     } 
    } 
}