如何最好地确定IEnumerable<>是否具有唯一值

Question

我有很多代码，其中我会做这样的事情

bool GetIsUnique(IEnumerable<T> values)
{
    return values.Count() == values.Distinct().Count;
}

有没有更好、更快、更好的方法来做这件事？

- Gluip

---

笔误：您在方法体中将“Values”大写了，但是您的参数是小写。 - Chris Pfohl

Answer 1

我会将这个变成一个好用的扩展方法

public static bool IsUnique<T>(this IEnumerable<T> list)
{
    var hs = new HashSet<T>();
    return list.All(hs.Add);  
}

检查所有项目是否可以添加到 HashSet 中。

- Jamiec

---

不错的回答，虽然有点简洁 :) - SWeko

我不喜欢对 All 加入具有副作用的谓词。 - CodesInChaos

副作用并不重要。哈希集在方法退出后被丢弃了。 - Jamiec

但是...... All 的实现不会记忆结果。你真的在考虑 All 的恶意实现吗？天哪。 - Jamiec

“但是...... All 的实现并不会记忆结果本身是无关紧要的。按定义，实现是一个实现细节。问题是：All 的契约是否保证能够使用具有副作用的谓词进行工作。---尽管未来版本的linq-to-objects很可能不会破坏您的代码，但它已经不能与有序并行linq一起使用了。在我看来，像 linq 这样的函数式编程库中记忆化是一种有效的优化。因此，我认为这样的实现并不是恶意的。” - CodesInChaos

Answer 2

你的方法需要对序列进行两次迭代，这样做可能存在以下几个问题：

1. 对于任何长度较大的序列，迭代两次会比一次慢。
2. 有些序列在尝试多次迭代时会抛出异常；其他序列可能会返回不同的结果。
3. 你的方法使用了 Count，每次都需要迭代整个序列。只要发现有重复值，就可以立即退出，没有理由不这样做。

下面的方法只需要对序列进行一次迭代，并且在遇到任何重复值时就会立即退出：

bool GetIsUnique<T>(IEnumerable<T> values)
{
    var set = new HashSet<T>();

    foreach (T item in values)
    {
        if (!set.Add(item))
            return false;
    }
    return true;
}

- LukeH

Answer 3

我认为这取决于你想做什么，如果存在非唯一值。@Jamiec或@LukeH的答案都是很好的答案，对于纯速度来说可能是最好的，但无法告诉您问题所在。

您还可以考虑类似以下的内容：

var group = values.GroupBy(x => x);
return group.Any(g => g.Count() > 1);

单独使用时，它比HashSet实现更差。但是，如果你保留该组，你可以找到重复的元素。

var group = values.GroupBy(x => x);
return group.Where(g => g.Count() > 1);

或者

var group = values.GroupBy(x => x);
return group.Where(g => g.Count() > 1).Select(g => g.Key);

如果你只关心所有值是否唯一，我建议使用 HashSet。然而，如果你想保持对下一步操作的选择性，考虑使用 GroupBy。

- Mike Two

---

@digEmAll：使用GroupBy需要在开始测试重复项之前迭代整个序列，这可能在处理较长序列时成为一个问题。（HashSet<T>的实现只要找到第一个重复项就可以中断。） - LukeH

@LukeH - 是的，如果你只想回答“是否有重复项”的问题，那么HashSet始终会更快。我只是想指出，如果你要跟进“有哪些重复项？”或者“有多少个重复项？”这些问题，那么考虑使用GroupBy是值得的，因为你可以问它所有这些问题。 - Mike Two

@Mike：但是在初始查询中使用GroupBy并没有任何优势。每次使用它时，查询都将被重新评估，那么为什么不在初始测试中使用Intersect，然后在需要时使用GroupBy进行任何后续查询呢？ - LukeH

@LukeH：我们在我的当前项目中正在做类似的事情。对我们来说，其中一个重要成本是相等比较和GetHashCode调用。使用一次GroupBy调用，我们只需要为原始集合循环一次支付这个成本。我们所做的是调用GroupBy，Select具有多个元素的组，并在其上调用ToList。然后我们对具有重复项的组进行大量工作。并不是声称这在所有情况下都是正确的。只是试图提供一种替代方案和考虑它的原因。无论如何，性能都应该针对您实际的情况进行测量。 - Mike Two

@LukeH：当然，它会评估整个列表，所以速度会慢一些（除了最坏情况）...但正如Mike所说，如果您需要知道哪些是重复项，这是允许的（显然您需要保存查询）... - digEmAll

Answer 4

你需要对数据进行两次循环 - 一次用于计算数量，一次用于获取不同的数量。特别是当前两个项目相同时，会变得非常糟糕！可以尝试以下代码：

bool GetIsUnique<T>(IEnumerable<T> values)
{
    HashSet<T> hashSet = new HashSet<T>();
    foreach(var value in values)
    {
        if (hashSet.Contains(value))
        {
            return false;
        }
        hashSet.Add(value);
    }
    return true;
}

这个函数会在找到重复项后立即结束。显然，它的速度取决于哈希查找的速度，但是考虑到Distinct内部使用了一个集合，我仍然期望它会更快。

- MrKWatkins

---

你可以将 HashSet 的 Contains 和 Add 合并为一步来加快速度，不是吗？ - Stuart

是啊，现在你这么说我就明白了！我显然是在考虑字典而不是集合... - MrKWatkins

Answer 5

我很惊讶竟然还没有人测试过这个：

将问题中的Gluip版本与JamieC、LukeK和MrKWatkins进行比较，三个答案都比提问者的版本更好。

在这三个答案中，它们都相当可比，但在大多数情况下，JamieC的速度略快。

当数据没有重复项或重复出现在IEnumerable的末尾时，大小或算法没有明显差异。

当数据在中间附近或开头有重复项时，与其他三个版本相比，原始问题中的Gluip版本表现出了它的缓慢。

检查集合的时间似乎随集合大小呈线性增长，这意味着没有任何算法适用于大或小的集合。

以下是一个测试程序，它可以输出CSV文件，您可以将其加载到电子表格程序中进行排序和图形化显示：

测试程序:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AreUniqueTest
{
class Program
{
    const int Iterations = 1000;

    enum DupeLocation
    {
        None,
        Early,
        Center,
        Late,
    }

    enum SetSize
    {
        Tiny= 10,
        Small = 100,
        Medium = 1000,
        Large = 10000,
        Huge = 100000,
    }

    static void Main()
    {
        Dictionary<string, Func<IEnumerable<int>, bool>> functions = new Dictionary<string, Func<IEnumerable<int>, bool>>
        {
            {"Gluip", GetIsUniqueGluip},
            {"LukeH", GetIsUniqueLukeH },
            {"Jamiec", GetIsUniqueJamiec },
            {"MrKWatkins", GetIsUniqueMrKWatkins }
        };

        var output = new StringBuilder();

        Console.WriteLine("Function,SetSize,DupeLocation,TotalTicks,AverageTicks");
        output.AppendLine("Function,SetSize,DupeLocation,TotalTicks,AverageTicks");

        foreach (SetSize size in Enum.GetValues(typeof(SetSize)))
        {
            var sizevalue = (int) size;
            foreach (DupeLocation location in Enum.GetValues(typeof(DupeLocation)))
            {
                var data = CreateTestData((int)size, location);
                foreach (string functionKey in functions.Keys)
                {
                    var ticks = RunSet(functions[functionKey], data, Iterations);
                    var avg = ticks / Iterations;
                    Console.WriteLine($"{functionKey},{sizevalue},{location},{ticks},{avg}");
                    output.AppendLine($"{functionKey},{sizevalue},{location},{ticks},{avg}");
                }
            }
        }

        File.WriteAllText("output.csv", output.ToString());
        Process.Start("output.csv");
    }

    static long RunSet<T>(Func<IEnumerable<T>, bool> getIsUnique, IEnumerable<T> values, int iterations)
    {
        var stopwatch = new Stopwatch();
        stopwatch.Start();
        for (var i = 0; i < iterations; i++)
        {
            getIsUnique.Invoke(values);
        }
        stopwatch.Stop();
        return stopwatch.ElapsedTicks;
    }

    static bool GetIsUniqueLukeH<T>(IEnumerable<T> values)
    {
        var set = new HashSet<T>();

        foreach (T item in values)
        {
            if (!set.Add(item))
                return false;
        }
        return true;
    }

    static bool GetIsUniqueGluip<T>(IEnumerable<T> values)
    {
        return values.Count() == values.Distinct().Count();
    }

    static bool GetIsUniqueJamiec<T>(IEnumerable<T> list)
    {
        var hs = new HashSet<T>();
        return list.All(hs.Add);
    }

    static bool GetIsUniqueMrKWatkins<T>(IEnumerable<T> values)
    {
        HashSet<T> hashSet = new HashSet<T>();
        foreach (var value in values)
        {
            if (hashSet.Contains(value))
            {
                return false;
            }
            hashSet.Add(value);
        }
        return true;
    }

    static int[] CreateTestData(int size, DupeLocation location)
    {
        var result = new int[size];
        Parallel.For(0, size, i => { result[i] = i; });
        return SetDupe(result, location);
    }

    static int[] SetDupe(int[] values, DupeLocation location)
    {
        switch (location)
        {
            case DupeLocation.Early:
                values[1] = values[0];
                break;
            case DupeLocation.Center:
                var midpoint = values.Length / 2;
                values[midpoint] = values[midpoint + 1];
                break;
            case DupeLocation.Late:
                values[values.Length - 1] = values[values.Length - 2];
                break;
            // case DupeLocation.None: // do nothing.
        }
        return values;
    }
}
}

- William Leader

---

为了自己的目的，我想要检查唯一性以验证输入，所以几乎每次调用代码时，都期望得到不包含重复项的集合。99.99%以上的时间内，对于我的使用情况来说并没有性能上的好处。实际上，我选择使用.Count() == .Distinct().Count() 并加上注释，因为这样最清晰地传达了代码的意图。 - William Leader

Answer 6

如果存在，找到第一个重复项的快速方法是：

public static bool TryFindFirstDuplicate<T>(this IEnumerable<T> source, out T duplicate)
{
    var set = new HashSet<T>();
    foreach (var item in source)
    {
        if (!set.Add(item))
        {
            duplicate = item;
            return true;
        }
    }
    duplicate = default(T);
    return false;
}

- Drew Noakes

Answer 7

两个基本规则：

1. 阅读和理解最简单的方式几乎总是编写某些内容的最佳方式。那段代码易于阅读，所以我认为你可以放心使用。
2. 性能（“更快”）仅在你能证明这是减慢程序速度的方法，或者如果你正在构建其他人将可以访问但无法访问源代码的库时才应该关注它。

其他方法将更快（当发现重复值并返回false时将会短路），但如果是我的代码，我仍然会坚持使用您的版本。

- Chris Pfohl

---

首要规则应该是“正确性比可读性或性能更重要”; 如果您的代码有问题，那么它的美观或性能就无关紧要了。问题中的代码（理论上）存在问题，因为并非所有序列都支持多次迭代。 - LukeH