在C#中查找列表中重复项的最快方法

Question

我知道在这个问题上有很多类似的问题,但我找不到我想要的答案.这是我的要求.

我有很长的字符串列表(很容易超过50,000或甚至100K项目),我需要在其中找到重复的项目.但只是发现重复不会做; 我真正想要做的是浏览列表并在每个项目的末尾添加一个增量索引,以指示项目重复的次数.为了更好地说明,让我举一个例子.我的列表实际上包含路径,所以示例大致类似于.

我原来的清单:

AAA\BBB
AAA\CCC
AAA\CCC
BBB\XXX
BBB
BBB\XXX
BBB\XXX

我的调整后的列表添加了索引:

AAA\BBB[1]
AAA\CCC[1]
AAA\CCC[2]
BBB\XXX[1]
BBB[1]
BBB\XXX[2]
BBB\XXX[3]

首先,我使用Linq尝试了以下方法:

List<string> originalList = new List<string>();
List<string> duplicateItems = new List<string>();

// pathList is a simple List<string> that contains my paths.
foreach (string item in pathList)
{
    // Do some stuff here and pick 'item' only if it fits some criteria.
    if (IsValid(item))
    {
        originalList.Add(item);
        int occurences = originalList.Where(x => x.Equals(item)).Count();
        duplicateItems.Add(item + "[" + occurences + "]");
    }
}

这很好用,给了我想要的结果.问题是,由于我的列表可以包含100K项目,因此速度很慢.所以我环顾四周,了解到HashSet可能是一种可能更有效的替代方案.但我无法弄清楚如何使用它获得我想要的结果.

我想我可以试试这样的东西:

HashSet<string> originalList = new HashSet<string>();
List<string> duplicateItems = new List<string>();

foreach (string item in pathList)
{
    // Do some stuff here and pick 'item' only if it fits some criteria.
    if (IsValid(item))
    {
        if (!originalList.Add(item))
        {
            duplicateItems.Add(item + "[" + ??? + "]");
        }
    }
}

后来我可以为HashSet中的所有项添加"[1]",但是如何在将项目添加到我的重复列表时将索引设置为正确(由混淆的通用符号,上面标记为???)？我不能保留一个我可以传递给我的方法的引用int,因为可能有数百个不同的重复项,每个重复项的重复次数不同.

我还能使用HashSet,还是有更好的方法来实现我的目标？即使是正确方向的微小指针也会有很大的帮助.

Answer 1

既然你要求最快,那么最好的IMO就是使用foreach循环和计数Dictionary<string, int>.它具有与HashSetLINQ 相同的时间复杂度并且使用的内存要少得多GroupBy:

var counts = new Dictionary<string, int>(pathList.Count); // specify max capacity to avoid rehashing
foreach (string item in pathList)
{
    // Do some stuff here and pick 'item' only if it fits some criteria.
    if (IsValid(item))
    {
        int count;
        counts.TryGetValue(item, out count);
        counts[item] = ++count;
        duplicateItems.Add(item + "[" + count + "]");
    }
}