Distinct() 方法是否保持原始序列的顺序不变？

Question

我想从列表中删除重复项，但不改变列表中独特元素的顺序。

Jon Skeet和其他人建议使用以下方法：

list = list.Distinct().ToList();

参考：

• 如何从List<T>中删除重复项？
• 在C#中从List<T>中删除重复项

是否保证唯一元素的顺序与之前相同？如果是，请提供确认此点的参考资料，因为我在文档中找不到任何关于它的内容。

- Nitesh

---

@ColonelPanic - 官方文档链接在这里 https://msdn.microsoft.com/en-us/library/bb348436(v=vs.110).aspx 明确说明了 "Distinct() 方法返回一个无序的序列，其中不包含重复值"。 - Evk

@Evk，“无序序列”与“序列的原始顺序”不同。 - Nitesh

我认为“unordered”的意思是“没有特定的顺序”，这也意味着“不必按照原来的顺序”。 - Evk

我刚遇到了一个关于使用Oracle12 Entity Framework 6的distinct的问题。在我的情况下，我在linq语句中的distinct之前有orderby，结果顺序被打乱了。select().OrderBy().Distinct().ToList()无法正常工作，而select().OrderBy().Distinct().ToList()可以正常工作。 - Karl

@Karl，这两个表达式是一样的。 :) - pvgoran

Answer 1

虽然不能保证，但这是最明显的实现方法。如果以流式方式实现（即只读取尽可能少的内容，并在能够时立即返回结果），那么很难不按顺序返回结果。

您可能需要阅读我的博客文章，关于Edulinq实现Distinct()方法的内容。

请注意，即使对于LINQ to Objects，这种保证也不是一定的 （个人认为应该有这种保证），而对于其他LINQ提供程序（如LINQ to SQL），更是如此。

在我看来，LINQ to Objects提供的保证水平有时有点不一致。一些优化已记录在案，而其他一些则没有。有些文档甚至是错误的。

- Jon Skeet

---

我注意到，如果输入集合已知为排序，则 .Distinct() 可以以流方式操作（通过简单地跳过当前值，如果它与上一个值相同）。对于任何有限的、内存中的 IReadOnlyCollection<T>，这种方法也可以起作用，只需迭代一次即可检查它是否已经排序。我不相信 .Distinct() 检查 IOrderedEnumerable<T>，真是气死人了。尽管 Linq 已经存在了 13 年，但我很惊讶它没有更聪明地应用这些优化。 - Dai

如果List<T>有一个bool IsSorted属性，当List<T>.Sort()运行后为true，并且如果发生任何重新排序，则变为false，那将是很好的 - 这样.Distinct()可以进行优化。哦，好吧... - Dai

@Dai：这听起来一般是不可行的 - 只是因为某些东西被排序并不意味着相关对象内部的数据与排序时相同。 - Jon Skeet

@JonSkeet 抱歉，最近我一直在使用不可变类型，忘记了数据的可变性意味着我们无法拥有好东西。尽管在 C# 9.0 中，它仍然适用于记录类型。 - Dai

@Dai：对于非常特定的情况，这是可以的——我只是不希望或期望它成为List<T>的一部分。 - Jon Skeet

Answer 2

在.NET Framework 3.5中，反编译Linq-to-Objects实现的Distinct()方法的CIL代码显示其元素顺序得到保留 - 然而这不是官方文档记录的行为。

我使用了Reflector进行了一些调查。在反编译System.Core.dll，Version=3.5.0.0之后，你可以看到Distinct()是一个扩展方法，代码如下：

public static class Emunmerable
{
    public static IEnumerable<TSource> Distinct<TSource>(this IEnumerable<TSource> source)
    {
        if (source == null)
            throw new ArgumentNullException("source");

        return DistinctIterator<TSource>(source, null);
    }
}

这里有一个有趣的东西，叫做DistinctIterator，它实现了IEnumerable和IEnumerator。这是它的IEnumerator的简化实现（去掉了goto和labels）：

private sealed class DistinctIterator<TSource> : IEnumerable<TSource>, IEnumerable, IEnumerator<TSource>, IEnumerator, IDisposable
{
    private bool _enumeratingStarted;
    private IEnumerator<TSource> _sourceListEnumerator;
    public IEnumerable<TSource> _source;
    private HashSet<TSource> _hashSet;    
    private TSource _current;

    private bool MoveNext()
    {
        if (!_enumeratingStarted)
        {
            _sourceListEnumerator = _source.GetEnumerator();
            _hashSet = new HashSet<TSource>();
            _enumeratingStarted = true;
        }

        while(_sourceListEnumerator.MoveNext())
        {
            TSource element = _sourceListEnumerator.Current;

             if (!_hashSet.Add(element))
                 continue;

             _current = element;
             return true;
        }

        return false;
    }

    void IEnumerator.Reset()
    {
        throw new NotSupportedException();
    }

    TSource IEnumerator<TSource>.Current
    {
        get { return _current; }
    }

    object IEnumerator.Current
    {        
        get { return _current; }
    }
}

正如您所看到的-枚举将按照源可枚举对象（我们调用“Distinct”的列表）提供的顺序进行。 Hashset 仅用于确定我们是否已经返回这样的元素。 如果没有，则我们将返回它，否则-继续在源上枚举。

因此，可以保证Distinct()将以与应用了 Distinct 的集合提供的相同顺序返回元素。

- Sergey Berezovskiy

---

这个行为是否有充分的记录？ - abatishchev

链接的答案中包含对文档的引用，其中写道：“结果序列是无序的。” - mgronber

这个问题询问的是“保证”，而不是“常见实现”。（就像我已经说过的那样，如果在平台/版本之间实现发生变化，我会感到惊讶，但这并不能构成保证。） - LukeH

@lazyberezovsky说：“我来自C/C++，在那里很多东西是未定义的，经常会询问某些东西是否得到保证。此外，我正在Silverlight应用程序中使用Distinct()，该应用程序在Mac和Windows上都有，因此我们不能采用'通用实现'，必须得到保证。” - Nitesh

当人们谈论保证时，通常指的是可以信赖的有文档支持的行为。例如，GroupBy的文档确实指定了行为，但Distinct的文档没有。 - Jon Skeet

Answer 3

根据文档，该序列是无序的。

- mgronber

---

补充信息以找到它：在链接中，请参考“备注”部分。“结果序列是无序的。” - Curtis Yallop

链接指的是Enumerable.Distinct而不是.Distinct扩展方法。 - Ryan Williams

这些是扩展方法，可以在方法签名中看到。Enumerable类提供了一组静态方法，用于查询实现IEnumerable<T>的对象。 :-) - mgronber

Answer 4

是的，Enumerable.Distinct会保留顺序。假设方法是惰性的，“只要看到不同的值就产生”，它就会自动遵循。想一想。 .NET参考源代码证实了这一点。它返回一个子序列，每个等价类的第一个元素。

foreach (TSource element in source)
    if (set.Add(element)) yield return element;

.NET Core实现类似。

令人沮丧的是，Enumerable.Distinct的文档对此一点很困惑:

结果序列是无序的。

我只能想象他们的意思是“结果序列没有排序”。您可以通过预先排序然后将每个元素与前一个元素进行比较来实现Distinct，但这不符合以上定义中的惰性求值。

- Colonel Panic

---

来源并不是规范。你所发现的只是一种巧合，而且在下一个更新之后可能无效。 - H H

@HenkHolterman 一般来说，我同意，实现可能会改变。例如，.NET 4.5在Array.Sort后面更改了排序算法。然而，在这种特定情况下，任何明智的Enumerable.Distinct实现肯定是懒惰的（“只要看到不同的值就产生不同的值”），并且保留顺序的属性也遵循这个原则。惰性评估是LINQ to Objects的核心信条；放弃它是不可想象的。 - Colonel Panic

我见过在 .net 4.6 中使用的实现，其中调用 dbQuery.OrderBy(...).Distinct().ToList() 不按照 order by 谓词指定的顺序返回列表 - 移除 Distinct（恰巧是多余的）在我的情况下修复了该错误。 - Rowland Shaw

@RowlandShawMight Queryable与Enumerable不同。您应该检查生成的查询。 - Wouter

Answer 5

虽然有点晚，但我认为没有人真正发布了最佳完整代码来完成这个任务，所以让我提供这个（本质上与.NET Framework使用Distinct()方法完全相同）*：

    public static IEnumerable<T> DistinctOrdered<T>(this IEnumerable<T> items)
    {
        HashSet<T> returnedItems = new HashSet<T>();
        foreach (var item in items)
        {
            if (returnedItems.Add(item))
                yield return item;
        }                       
    }

这样做可以保证原始顺序，而不依赖于未记录或假定的行为。我认为这比使用多个LINQ方法更有效，但我也愿意在这里接受纠正。

(*) .NET Framework源代码使用内部的Set类，该类似乎与HashSet实现基本相同。

- Emperor Eto

---

不要紧，因为顺序将由提供的可枚举对象决定。 HashSet 只是告诉我们该项是否已被返回，如果是，则跳过它。 - Emperor Eto

Answer 6

这在很大程度上取决于您的linq提供程序。对于Linq2Objects，您可以保留Distinct的内部源代码，这使人们认为原始顺序得以保留。

然而，对于其他解析为某种SQL的提供程序，情况并非如此，因为ORDER BY语句通常出现在任何聚合之后（例如Distinct）。所以如果您的代码是这样的：

myArray.OrderBy(x => anothercol).GroupBy(x => y.mycol);

这段文本翻译成 SQL 后类似于以下内容：

SELECT * FROM mytable GROUP BY mycol ORDER BY anothercol;

这显然首先对数据进行分组，然后再进行排序。现在你被困在DBMS自己的逻辑中如何执行它。在某些DBMS上，甚至不允许这样做。想象以下数据：

mycol anothercol
1     2
1     1
1     3
2     1
2     3

执行 myArr.OrderBy(x => x.anothercol).GroupBy(x => x.mycol) 时，我们假设以下结果：

mycol anothercol
1     1
2     1

但是数据库管理系统可能会聚合另一个列，以便始终使用第一行的值，导致以下数据：

mycol anothercol
1    2
2    1

这句话的翻译是：“下订单后，将会得到以下结果：”。同时需要保留HTML标签，不做解释。

mycol anothercol
2    1
1    2

这与以下内容类似：

SELECT mycol, First(anothercol) from mytable group by mycol order by anothercol;

这与您预期的完全相反。

您会发现执行计划可能因底层提供程序而异。这就是为什么文档中没有关于此的保证。

- MakePeaceGreatAgain

Answer 7

默认情况下，使用Distinct linq运算符使用Equals方法，但您可以使用自己的IEqualityComparer对象来指定两个对象何时相等，并实现GetHashCode和Equals方法以使用自定义逻辑。请记住：GetHashCode不应使用重度CPU比较（例如，仅使用一些明显的基本检查），它被用作首先声明两个对象是否肯定不同（如果返回不同的哈希码）或可能相同（相同的哈希码）。在后一种情况下，当两个对象具有相同的哈希码时，框架将使用Equals方法作为关于给定对象相等性的最终决策。在您拥有MyType和MyTypeEqualityComparer类之后，请遵循以下代码以确保顺序保持不变：

var cmp = new MyTypeEqualityComparer();
var lst = new List<MyType>();
// add some to lst
var q = lst.Distinct(cmp);

在跟进的sci library中，我实现了一个扩展方法来确保Vector3D集合在使用特定扩展方法DistinctKeepOrder时保持顺序：

相关代码如下：

/// <summary>
/// support class for DistinctKeepOrder extension
/// </summary>
public class Vector3DWithOrder
{
    public int Order { get; private set; }
    public Vector3D Vector { get; private set; }
    public Vector3DWithOrder(Vector3D v, int order)
    {
        Vector = v;
        Order = order;
    }
}

public class Vector3DWithOrderEqualityComparer : IEqualityComparer<Vector3DWithOrder>
{
    Vector3DEqualityComparer cmp;

    public Vector3DWithOrderEqualityComparer(Vector3DEqualityComparer _cmp)
    {
        cmp = _cmp;
    }

    public bool Equals(Vector3DWithOrder x, Vector3DWithOrder y)
    {
        return cmp.Equals(x.Vector, y.Vector);
    }

    public int GetHashCode(Vector3DWithOrder obj)
    {
        return cmp.GetHashCode(obj.Vector);
    }
}

简而言之，Vector3DWithOrder 封装了类型和一个顺序整数，而 Vector3DWithOrderEqualityComparer 封装了原始类型比较器。

以下是确保顺序维护的方法帮助程序。

/// <summary>
/// retrieve distinct of given vector set ensuring to maintain given order
/// </summary>        
public static IEnumerable<Vector3D> DistinctKeepOrder(this IEnumerable<Vector3D> vectors, Vector3DEqualityComparer cmp)
{
    var ocmp = new Vector3DWithOrderEqualityComparer(cmp);

    return vectors
        .Select((w, i) => new Vector3DWithOrder(w, i))
        .Distinct(ocmp)
        .OrderBy(w => w.Order)
        .Select(w => w.Vector);
}

注意：进一步的研究可能会找到更通用（使用接口）和优化的方式（不封装对象）。

- Lorenzo Delana