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

本文关键字：是不同 包含重 IEnumerable 检查 是否 | 更新日期: 2023-09-27 18:31:23

有没有一种快速的内置方法来检查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;
}

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

您的第二个代码示例简短、简单、明显有效，即使不是完全完美的理想解决方案，显然也非常接近它。 这似乎是对您的特定问题完全可以接受的解决方案。

除非您在发现问题并完成性能测试后使用该特定解决方案会导致性能问题，否则我会保持原样。 鉴于我总体上看不到改进的空间很小，这似乎不太可能。 这不是一个足够冗长或复杂的解决方案，试图找到"更短"或更简洁的东西值得你花时间和精力。

简而言之，几乎可以肯定，你的代码中有更好的地方可以打发你的时间;你已经拥有的东西很好。

要回答您的具体问题：

  1. 但是，这看起来像是 O（2n） - 是吗？

    是的，它是。

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

    不，不是。

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

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

  4. 也有内置的方法吗？

    好吧，你展示了一个，它只是效率不高。 我想不出像您展示的那样有效的基于 LINQ 的整个解决方案。 我能想到的最好的是：data.Except(data).Any()。 与常规计数相比，这比您的独特计数要好一点，因为第二次迭代可能会短路（但不是第一次），但它也会迭代序列两次，并且仍然比非 LINQ 解决方案差，因此仍然不值得使用。

以下是对OP答案的可能改进：

public static IEnumerable<T> Duplicates<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))
            yield return item;
    }
}

您现在有一种可能有用的方法来获取实际的重复项目，您可以通过以下方式回答您的原始问题：

collection.Duplicates().Any()

只是对现有解决方案的补充：

public static bool ContainsDuplicates<T>(this IEnumerable<T> items)
{
    return ContainsDuplicates(items, EqualityComparer<T>.Default);
}
public static bool ContainsDuplicates<T>(this IEnumerable<T> items, IEqualityComparer<T> equalityComparer)
{
    var set = new HashSet<T>(equalityComparer);
    foreach (var item in items)
    {
        if (!set.Add(item))
            return true;
    }
    return false;
}

此版本允许您选择一个相等比较器，如果您想根据非默认规则比较项目，这可能会很有用。

例如，要不区分大小写地比较一组字符串，只需将其传递StringComparer.OrdinalIgnoreCase即可。

相关文章：