如何在C#中有效地比较两个排序后的大列表

本文关键字：排序 两个 列表 有效地 比较 | 更新日期: 2023-09-27 18:19:55

我有两个通用列表，每个列表中有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. 姓名匹配但工资不匹配的员工

将如此大的数据列表与上述条件进行比较，最快的方法是什么？

如何在C#中有效地比较两个排序后的大列表

我会按照name-O(n*log(n))对newEmployeeList和oldEmployeeList列表进行排序。然后您可以使用线性算法来搜索匹配项。因此，如果两个列表的大小大致相同，则总数将为O(n+n*log(n))。这应该比O(n^2)的"暴力"算法更快。

我可能建议将这两个列表存储在基于名称的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()子句对此进行筛选。

更新：我假设（根据问题的标题）这两个列表已经排序。也许它们存储在带有聚集索引的数据库中。因此，这个答案依赖于这一假设。

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

想法如下：

  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;
                }
            }
        }
    }
}

排序列表中最快的解决方案之一是使用BinarySearch在另一个列表中查找项目。

但与其他人一样，你应该根据你的项目需求来衡量它，因为性能往往是主观的事情。

您可以使用创建字典

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

如果您在另一个列表上查找循环中的值，这将提供接近O（1）的查找和接近O（n）的行为。

（我在这里假设ToDictionary是O（n），这对于直接实现来说是有意义的，但我还没有测试过这种情况）

这将产生一个非常直接的算法，我认为在O（n）以下使用两个未排序的列表是非常困难的。

相关文章：