如何在C#中高效比较两个已排序的大型列表？

Question

我有两个通用列表，每个列表中有20,000和30,000个对象。

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. 姓名匹配但薪水不匹配的员工

在满足上述条件的情况下，比较这样大的数据列表最快的方法是什么？

- Santosh

---

你可以使用LINQ，它会有一点性能损耗，但正如@Jon所说的那样，这对你是否足够或你尝试过什么其他方法呢？ - Xtian Macedo

你的数据从哪里获取？如果你是从 SQL 填充列表，你可能想直接从 SQL 中进行比较，而不是从列表中比较。 - Gabriel GM

既然它们已经排序，简单的顺序遍历是O(n)，这速度太慢了吗？ - Daniel Fischer

-1 太宽泛了。如果问题是“我在Y时间内做X，我该如何改进？”我不会投票关闭（假设提供了X和Y）。 - Austin Salonen

Answer 1

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

- Elalfer

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

你可以使用 Where() 子句来过滤 Match 或 !Match。

- James Michael Hare

Answer 3

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

以下是一种具有O(n)复杂度、非常快速且非常简单的实现方式。
我相信这是合并算法的变体。

以下是思路：

1. 开始枚举这两个列表。
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;
                }

            }
        }
    }
}

- Scott Rippey

---

在使用算法之前，这两个列表都不应该排序吗？在这种情况下，您不能声称其复杂度为 O(n)。对于相同大小的列表，它至少为 O(n*ln(n)+n)。 - Elalfer

如何在C#中高效比较两个已排序的大型列表？我一直以为这些列表已经排序了。然而，他的评论“如果按名称排序可以提高速度”，可能表明这些列表并没有排序，或者可能表明列表的来源可以预先排序（例如，聚集索引）。所以我想这个问题有一些歧义。我会在我的答案中加上免责声明。 - Scott Rippey

Answer 4

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

但正如其他人所提到的，您应该根据您的项目要求进行衡量，因为性能往往是一个主观的事情。

- Tigran

Answer 5

你可以使用字典来创建一个

。

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

如果您从另一个列表中遍历查找值，这将为您提供接近O(1)的查找和接近O(n)的行为。

（我在这里假设ToDictionary是O(n)，这在直观实现时是有道理的，但我没有测试过是否确实如此）

这将成为非常简单的算法，我认为使用两个未排序的列表低于O(n)可能非常困难。

- Joachim Isaksson

---

你忘记了添加字典初始化复杂度。 - Elalfer

不确定log(n)是从哪里来的，只要哈希桶足够多，插入单个项基本上就是一个哈希计算和在计算出的索引处插入。 - Joachim Isaksson

是的，这就是为什么我从我的评论中删除了 log(n)。 - Elalfer