15

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

3 回答 3

9

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

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

简而言之，几乎可以肯定，您的代码中有更好的地方可以消磨时间；你已经拥有的很好。

要回答您的具体问题：

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

    是的。

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

    不，这不对。

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

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

  4. 也有内置的方法吗？

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

于 2013-09-14T17:07:29.457 回答
2

以下是对 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()
于 2013-12-13T16:11:13.143 回答
2

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

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。

于 2016-03-31T11:51:07.743 回答