c# - 从 2 个集合中查找添加和删除的高效算法

Question

您好，我想实现一个有效的算法来处理以下情况:

假设我们有 2 个包含以下元素的列表:

来源:[a,b,c,d,e]新:[d,e,f,g]

现在我必须用新信息更新源代码。该算法应该能够发现“f”和“g”是新条目，“a”、“b”和“c”已被删除，并且“d”和“e”没有被修改。

涉及的操作是Source和New之间的set-intersect操作，反之亦然。我正在寻找一种在 C# 中针对任意未排序枚举实现的高效算法。

提前致谢

Answer 1

var added = New.Except(Source);
var removed = Source.Except(New);
var notModified = Source.Intersect(New);

如果您想采用一种“展示您的工作方式”的方法，我建议您将它们分别放入 HashSet 中，因为这样可以快速 Contains检查，与其他枚举相比。

编辑:

好吧，如果我们以牺牲表达效率为代价来追求总速度，那么有以下假设:

1. 我们有一个合理的可散列类型的项目(如果不是，但它们可以绝对排序，那么 SortedList 可能胜过散列集)。
2. 我们无法预测 Source 或 New 是否会更大(在示例中，与我的做法相反，这样做有一点优势，但我假设这只是数据中的偶然情况，并且我们必须以相同的可能性期待每一个。

那么我建议:

HashSet<T> removed = Source as HashSet<T> ?? new HashSet<T>(Source);
LinkedList<T> added = new LinkedList<T>();
LinkedList<T> notModified = new LinkedList<T>();
foreach(T item in New)
    if(removed.Remove(item))
        notModified.AddLast(item);
    else
        added.AddLast(item);

设置中removed我测试它是否已经是一个哈希集，以避免浪费时间构建一个新哈希集(我假设输入的类型为 IEnumerable<T> )。当然，这是一个破坏性的行为，所以我们无论如何都希望避免它。

另请注意，我在枚举哈希集时修改了它。这是 hashset 允许的，但在枚举器给出的保证之外，因此取决于实现。尽管如此，使用当前的框架实现。这样做比测试并添加到不同的已删除集合更有效。

我为其他两个集合选择了链表，因为它们往往在插入成本方面表现良好(不仅是 O(1)，而且与使用另一组相比更快的 O(1))。

现在，如果您想更进一步，如果您自己动手，可能可以在哈希集的实现中进行微优化。