logo标签列表

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

c#listlinqduplicateshashset
3

我知道stackoverflow上有大量关于这个主题的类似问题，但我却没有找到我想要的答案。这是我的需求。

我有一个长列表的字符串（很容易超过50,000甚至100,000项），我需要在其中找到重复的项目。但仅仅找到重复的项目不够；我真正想做的是遍历列表并在每个项目的末尾添加一个递增的索引，以指示该项目重复的次数。为了更好地说明这一点，让我举个例子。实际上，我的列表包含路径，所以这个例子大致类似于这种情况。

我原来的列表:

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 + "]");
    }
}

这段代码能够有效地给出所需的结果，但是如果我的列表包含了10万个元素，它会变得相当缓慢。因此，我查找了相关资料并了解到HashSet可能是一个更高效的替代方案。但是我不知道如何使用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，或者有更好的方法来完成我的目标？即使是指向正确方向的轻微提示也将是一大帮助。
最好是这样，但如果速度不太慢且列表不太多的话，我也会考虑其他选择。 - Sach
结果列表中元素的顺序是否重要？ - NineBerry
你不能使用 HashSet<string> 来存储原始列表，因为 HashSet<T> 不会存储重复项。 - itsme86
@Trioj 不，这正是我在第一个代码示例中展示的。它可以工作，但速度太慢了，所以我正在寻找可能更有效的替代方案。 - Sach
说实话，我不知道它会有多快--通常我不指望LINQ会非常迅速，但我猜测这比原始代码要快。目前我没有足够大的记录集来测试和验证。 - Trioj
显示剩余7条评论
7个回答
10

如果你追求速度，我认为最好的方法是使用 foreach 循环并计数 Dictionary<string, int>。它与 HashSet 具有相同的时间复杂度，并且比 LINQ 的 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 + "]");
    }
}
谢谢，让我也试一下并将其与另一种解决方案进行比较。 - Sach
我在116个列表上分别运行了三个答案，每个列表都运行了10次，并向maccettura、Ivan Stoev和Markus请教。平均时间以毫秒为单位如下： maccettura = 13819，Ivan Stoev = 13809，Markus = 12966。 因此，它们似乎都差不多。 - Sach
Markus的答案只是我的副本。那么LINQ GroupBy解决方案怎么样呢？正如我在答案中提到的，区别在于所使用的内存和GC压力——如果您有100K个唯一项，则GroupBy将额外分配100K个数组。 - Ivan Stoev
@IvanStoev @Sach 很有趣的是，这两种方法之间的差异几乎达到了一秒钟，尽管它们都使用了字典。我认为你的应该更快，因为你初始化了字典的大小。但我们的答案仍然存在差异。也许是我在我的方法中使用的序数字符串比较、迭代器或string.Format。 - Markus
@Markus请注意，上面的时间测量是快速而粗略的.NET DateTime值测量，匆忙完成，可能不是最准确的。因此，请在考虑这些值时注意这一点。 - Sach
4
您可以尝试这个方法，虽然我还没有进行性能测试：
List<string> originalList = new List<string>()
{
    @"AAA\BBB",
    @"AAA\CCC",
    @"AAA\CCC",
    @"BBB\XXX",
    @"BBB",
    @"BBB\XXX",
    @"BBB\XXX"
};
List<string> outputList = new List<string>();

foreach(var g in originalList.GroupBy(x => x).Select(x => x.ToList()))
{   
    var index = 1;  
    foreach(var item in g)
    {
        outputList.Add(string.Format("{0}[{1}]", item, index++));
    }
}

Fiddle here

1
是的，这看起来更接近我的预期。 - Trioj
1
让我试一下并回报。 - Sach
2
是的，我确实需要递增计数。 我尝试了@maccettura的解决方案，它运行得非常好；一个包含76131个项目的列表在不到1秒的时间内完成，而Linq则需要更长的时间。 - Sach
1
不错。我喜欢这个根据需求实现的方案。 - Trioj
1
我在116个列表上分别运行了三个答案，每个列表都运行了10次，并向maccettura、Ivan Stoev和Markus请教。平均时间以毫秒为单位如下： maccettura = 13819，Ivan Stoev = 13809，Markus = 12966。 因此，它们似乎都差不多。 - Sach
显示剩余2条评论
1
这个是什么意思？
    static IEnumerable<string> MyCounter(IEnumerable<string> data)
    {
        var myDic = new Dictionary<string, int>();
        foreach (var d in data)
        {
            if (!myDic.ContainsKey(d))
                myDic[d] = 1;
            else
                myDic[d] = myDic[d] + 1 ;
            yield return d +"[" + myDic[d] + "]";
        }
    }
谢谢。他的例子是基于1的，对吧？ - Jonathan Nappee
我不知道当时在想什么，抱歉，哈哈。 - maccettura
1
您可以遍历列表并使用字典来获取计数，如下所示：
private int GetCount(IDictionary<string, int> counts, string item)
{
  int count;
  if (!counts.TryGetValue(item, out count))
    count = 0;
  count++;
  counts[item] = count;
  return count;
}

private IEnumerable<string> GetItems(IEnumerable<string> items)
{
  // Initialize dict for counts with appropriate comparison
  var counts = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);
  foreach(var item in items)
    yield return string.Format("{0}[{1}]", item, GetCount(counts, item));
}
我在116个列表上每个运行了10次，然后向maccettura、Ivan Stoev和Markus展示了三个答案。平均计算出来的毫秒数如下： maccettura = 13819，Ivan Stoev = 13809，Markus = 12966。 因此，它们看起来都差不多。 - Sach
0
使用 HashSet
注意: Dump() 是 LinqPad 方法，用于将结果打印到屏幕上 - 根据需要进行替换。
void Main()
{
    var list = new List<string> {"hello", "doctor", "name", "continue", "yesterday", "tomorrow", "HELLO"};
    
    //case-insensitive string compare
    list.HasDuplicates(StringComparer.OrdinalIgnoreCase).Dump();

    //case-sensitive string compare
    list.HasDuplicates().Dump();

    //integer compare
    var list2 = new List<int> { 1,2,3,4,5,2 };
    list2.HasDuplicates().Dump();
}

public static class Test
{
    public static bool HasDuplicates<T>(this IList<T> list, StringComparer stringComparer = null)
    {
        if (typeof(T) == typeof(string))
        {
            var hash = new HashSet<string>(list.Count, stringComparer);
            foreach (var val in list) if (!hash.Add(val?.ToString())) break;
            return hash.Count != list.Count;
        }
        else
        {
            var hash = new HashSet<T>(list.Count);
            foreach (var val in list) if (!hash.Add(val)) break;
            return hash.Count != list.Count;
        }
    }
}

/*

output:

True
False
True
*/
他们不是要求一个方法，而是最快的方法。新的答案应该与现有答案进行比较，否则它就不能回答问题。 - Gert Arnold
0
你可以使用Group()将字符串组合在一起，然后使用值和计数的组合来投影这些组。
给定你的字符串列表：
var listOfStrings;
var grouped = listOfStrings.GroupBy(x => x);
var groupedCount = grouped.Select(x => new {key = x.Key, count = group.Count()});
这不会给每个元素一个总计数吗？而不是像 OP 想要的增量计数？ - maccettura
是的，我在我的实现中也错过了那个。 - Trioj
0

您可以使用这个简洁而精准的代码：

public static void Main()
{
    var originalList  = new List<string>()
    {
        @"AAA\BBB",
        @"AAA\CCC",
        @"AAA\CCC",
        @"BBB\XXX",
        @"BBB",
        @"BBB\XXX",
        @"BBB\XXX"
    };

    var outputList = originalList.GroupBy(x => x).SelectMany(x => x.Select((y, i) => string.Format("{0}[{1}]", y, i + 1)));     

    Console.WriteLine(string.Join("\n", outputList));
}
那么这是“最快的方式”吗？ - Gert Arnold
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接