快速检查IEnumerable <T>是否包含重复项(=不同)

Question

是否有快速内置方法来检查是否IEnumerable<string>只包含不同的字符串？

一开始我开始:

var enumAsArray = enum.ToArray();
if (enumAsArray.Length != enumAsArray.Distinct().Count())
    throw ...

但是,这看起来像是O(2n) - 是吗？ToArray()可能是O(1)？

这看起来更快:

var set = new HashSet<string>();
foreach (var str in enum)
{
    if (!set.Add(str))
        throw ...
}

这应该是O(n),但是,是否也有内置方式？

编辑:也许Distinct()在内部使用它？

---

解决方案: 在考虑了所有的评论和答案后,我为我的第二个解决方案编写了一个扩展方法,因为这似乎是最快的版本,也是最具可读性的:

public static bool ContainsDuplicates<T>(this IEnumerable<T> e)
{
    var set = new HashSet<T>();
    // ReSharper disable LoopCanBeConvertedToQuery
    foreach (var item in e)
    // ReSharper restore LoopCanBeConvertedToQuery
    {
        if (!set.Add(item))
            return true;
    }
    return false;
}

Answer 1

您的第二个代码示例简短,简单,明显有效,如果不是完全理想的解决方案,则显然非常接近它.对您的特定问题来说,这似乎是一个完全可以接受

除非您在注意到问题并完成性能测试后显示出使用该特定解决方案会导致性能问题,否则我将保留原样.鉴于我总体上看不到改善的空间,这似乎不太可能.这不是一个足够冗长或复杂的解决方案,试图找到"更短"或更简洁的东西是值得你的时间和精力.

简而言之,您的代码几乎肯定有更好的地方可以花时间; 你已经没事了.

回答您的具体问题:

1. 但是,这看起来像是O(2n) - 是吗？

   是的.

2. ToArray() 可能是O(1)？

   不,这不对.

3. 也许Distinct()在内部使用它？

   它确实使用了a HashSet,它看起来非常相似,但它只是忽略了重复的项目; 它不向调用者提供任何指示它刚刚传递了重复项.因此,您需要迭代整个序列两次以查看它是否删除了任何内容,而不是在遇到第一个副本时停止.这是总是迭代整个序列两次的东西和可能迭代整个序列一次的东西之间的差异,但是一旦确定答案就可以短路并停止.

4. 还有内置的方式吗？

   好吧,你展示了一个,它只是效率不高.我认为没有像你所展示的那样有效的基于LINQ的解决方案.我能想到的最好的是:data.Except(data).Any().这比普通计数要好一些,因为第二次迭代可以短路(但不是第一次),但它也会迭代序列两次,但仍然比非LINQ解决方案更差,所以它仍然没有值得使用.