C# - 查找重复项时比较集合本身的最快方法

Question

public class TestObject
{
    string TestValue { get; set; }
    bool IsDuplicate { get; set; }
}

List<TestObject> testList = new List<TestObject>
{
    new TestObject { TestValue = "Matt" },
    new TestObject { TestValue = "Bob" },
    new TestObject { TestValue = "Alice" },
    new TestObject { TestValue = "Matt" },
    new TestObject { TestValue = "Claire" },
    new TestObject { TestValue = "Matt" }
};

假设testList实际上有数百万个对象。

如何最快地确保其中三个TestObjects中的两个具有TestValue为Matt，其IsDuplicate被设置为true？无论给定值的实例有多少个，只有一个实例应该在过程中以false的IsDuplicate出现。

我不反对通过线程来完成此操作。如果将其转换为另一种集合类型可以更快，则集合不必是列表。

我需要保留重复项并将其标记为重复项，而不是从集合中删除它们。

进一步说，这是一个更加复杂问题的简单表达方式。所讨论的对象已经有了一个序数，我可以使用它来对它们进行排序。

在精确字符串相等性匹配的初始重复项之后，我将不得不再次遍历集合，并使用一些模糊匹配逻辑重新尝试其余部分。在去重过程中，开始存在的集合不会改变，也不会在之后改变。

最终，原始集合将被写入文件，并标记可能的重复项。

- Bob Tway

---

我不确定是否适用于您的情况，但如果您只需要不同的TestObject实体，则请使用HashSet。它将为您提供最佳服务，因为它是专门用于包含特定类型唯一实例的。 - Anatolyevich

我也是这么想的@Anatolyevich，但它不允许集合包含重复项并标记重复项。我猜这就是OP想要的。 - Draken

@Nasreddine 匆忙地涂写了伪代码 :) 是的，我需要保留重复项并标记它们。 - Bob Tway

重复的含义是什么？这是否意味着您想保留顺序，并且顺序对集合的进一步处理很重要？在标记重复项后，集合会发生什么？您将如何处理这些重复项？您是否考虑过为重复检查单独使用HashSet，例如当您添加新项目时，检查它是否已经在HashSet中，如果是，则立即将其标记为重复项？ - Luaan

如果列表中有第三个“Matt”，会发生什么？ - dotNET

Answer 1

正如其他人提到的，这里正确的方法是使用 HashSet 类。

var hashSet = new HashSet<string>();

foreach (var obj in testList)
{
    if (!hashSet.Add(obj.TestValue))
    {
        obj.IsDuplicate = true;
    }
}

第一次将值添加到HashSet时，它会成功添加，并且HashSet.Add()方法返回true，因此您不需要对该项进行任何更改。当您尝试第二次添加它时，HashSet.Add()返回false，并将该项标记为重复项。

在运行完我们的标记重复项方法后，列表将处于以下状态：

Matt
Bob
Alice
Claire
Matt DUPLICATE

- Ivan Yurchenko

Answer 2

这可能相当高效：

foreach (var dupe in testList.GroupBy(x => x.TestValue).SelectMany(g => g.Skip(1)))
    dupe.IsDuplicate = true;

[编辑] 这种方法的速度只有上面被接受的答案的三分之一左右，因此应该使用那个答案。这个答案仅仅是学术上的兴趣。

- Matthew Watson

Answer 3

在构建TestValue集合时，我可能会检查重复项，以避免在数百万元素上循环两次。如果可能的话，我会使用Dictionary<string, List<TestValue>>。

Dictionary<string, List<TestValue>> myList = new Dictionary<string, List<TestValue>>();
while(NotEndOfData())
{
     TestValue obj = GetTestValue();
     if(myList.ContainsKey(obj.Name))
     {
         obj.IsDuplicate = true;
         myList[obj.Name].Add(obj);
     }
     else
     {
         obj.IsDuplicate = false;
         myList.Add(obj.Name, new List<TestValue>() { obj};
     }
}

- Steve

Answer 4

SortedSet<string> sorted = new SortedSet<string>();
for (int i = 0; i < testList.Count; i++)
  testList[i].IsDuplicate = !sorted.Add(testList[i].TestValue);

根据您在问题中的允许，我会将testList更改为数组，而不是列表，以使索引器更快。

- dotNET

Answer 5

由于您指出您有一个属性来保留项目的序数，我们可以使用该属性将排序顺序重置为标记项目为重复项后的原始顺序。

下面的代码是自解释的。但如果您需要进一步的解释，请告诉我。

我假设属性名称为SortOrder。请相应修改代码。

void MarkDuplicates()
{
    testList = testList.OrderBy(f => f.TestValue).ThenBy(f => f.SortOrder).ToList();
    for (int i = 1; i < testList.Count; i++) 
    {
        if (testList[i].TestValue == testList[i - 1].TestValue) testList[i].IsDuplicate = true;
    }
    testList = testList.OrderBy(f => f.SortOrder).ToList();
}

我不是性能专家。但您可以计时此处提供的各种解决方案并自行检查性能。

- Pradeep Kumar