La méthode Distinct() préserve-t-elle l'ordre original de la séquence?

Question

Je veux supprimer les doublons de la liste, sans changer l'ordre des éléments uniques dans la liste.

Jon Skeet et d'autres ont suggéré d'utiliser ce qui suit:

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

Référence:

• Comment supprimer les doublons d'une liste?
• Supprimer les doublons d'une liste en C#

Est-il garanti que l'ordre des éléments uniques sera le même qu'auparavant? Si oui, veuillez donner une référence qui le confirme car je n'ai rien trouvé à ce sujet dans la documentation.

Answer 1

Il n'est pas garanti, mais c'est la mise en œuvre la plus évidente. Ce serait difficile à mettre en œuvre de manière à diffuser (c'est-à-dire de sorte qu'il renvoie des résultats dès qu'il le peut, ayant lu aussi peu que possible) sans les renvoyer dans l'ordre.

Vous voudrez peut-être lire mon article de blog sur l'implémentation Edulinq de Distinct().

Remarquez que même si cela était garanti pour LINQ to Objects (ce que personnellement je pense qu'il devrait être), cela ne signifierait rien pour d'autres fournisseurs LINQ tels que LINQ to SQL.

Le niveau de garanties fournies dans LINQ to Objects est parfois un peu incohérent, à mon avis. Certaines optimisations sont documentées, d'autres non. En fait, une partie de la documentation est carrément fausse.

Answer 2

Dans le .NET Framework 3.5, en désassemblant le CIL de l'implémentation Linq-to-Objects de Distinct(), on constate que l'ordre des éléments est préservé - cependant, ce comportement n'est pas documenté.

J'ai mené une petite investigation avec Reflector. Après avoir désassemblé System.Core.dll, Version=3.5.0.0, on peut voir que Distinct() est une méthode d'extension, qui ressemble à ceci :

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

        return DistinctIterator(source, null);
    }
}

Donc, ce qui est intéressant ici, c'est DistinctIterator, qui implémente IEnumerable et IEnumerator. Voici une implementation simplifiée (avec les goto et les labels supprimés) de cet IEnumerator :

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

    private bool MoveNext()
    {
        if (!_enumeratingStarted)
        {
            _sourceListEnumerator = _source.GetEnumerator();
            _hashSet = new HashSet();
            _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.Current
    {
        get { return _current; }
    }

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

Comme vous pouvez le voir - l'énumération se fait dans l'ordre fourni par l'énumérable source (list, sur laquelle nous appelons Distinct). HashSet est utilisé uniquement pour déterminer si nous avons déjà retourné un tel élément ou non. Si ce n'est pas le cas, nous le retournons, sinon - nous continuons l'énumération sur la source.

Il est donc garanti que Distinct() retournera les éléments exactement dans le même ordre, qui ont été fournis par la collection sur laquelle Distinct a été appliqué.

Answer 3

Selon la documentation, la séquence est désordonnée.

Answer 4

Oui, Enumerable.Distinct préserve l'ordre. En supposant que la méthode soit paresseuse "produit des valeurs distinctes dès qu'elles sont vues", cela suit automatiquement. Pensez-y.

La source de référence .NET le confirme. Il renvoie une sous-séquence, le premier élément de chaque classe d'équivalence.

foreach (TSource élément dans la source)
    si (set.Add(élément)) yield return élément;

L'implémentation .NET Core est similaire.

De manière frustrante, la documentation pour Enumerable.Distinct est confuse sur ce point:

La séquence résultante n'est pas ordonnée.

Je ne peux imaginer qu'ils veulent dire "la séquence résultante n'est pas triée". Vous pourriez implémenter Distinct en triant préalablement puis en comparant chaque élément au précédent, mais cela ne serait pas paresseux tel que défini ci-dessus.

Answer 5

Un peu en retard pour la fête, mais personne n'a vraiment posté le meilleur code complet pour accomplir cela selon moi, donc laissez-moi offrir ceci (qui est essentiellement identique à ce que fait le Framework .NET avec Distinct())*:

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

Cela garantit l'ordre d'origine sans dépendre d'un comportement non documenté ou supposé. Je crois aussi que c'est plus efficace que d'utiliser plusieurs méthodes LINQ même si je suis ouvert à être corrigé ici.

(*) La source du Framework .NET utilise une classe interne Set, qui semble être substantiellement identique à HashSet.