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

Par défaut, lorsque vous utilisez l'opérateur Linq Distinct, il utilise la méthode Equals, mais vous pouvez utiliser votre propre objet IEqualityComparer pour spécifier quand deux objets sont égaux en implémentant une logique personnalisée avec les méthodes GetHashCode et Equals. N'oubliez pas que :

GetHashCode ne doit pas effectuer de comparaison CPU lourde (par exemple, utilisez uniquement quelques vérifications de base évidentes) et il est utilisé en premier pour déterminer si deux objets sont sûrement différents (si des codes de hachage différents sont renvoyés) ou potentiellement les mêmes (même code de hachage). Dans ce dernier cas, lorsque deux objets ont le même code de hachage, le framework passera à la vérification en utilisant la méthode Equals pour prendre une décision finale sur l'égalité des objets donnés.

Après avoir les classes MyType et MyTypeEqualityComparer, suivez le code ci-dessous pour garantir que la séquence maintient son ordre :

var cmp = new MyTypeEqualityComparer();
var lst = new List();
// ajoutez des éléments à lst
var q = lst.Distinct(cmp);

Dans la bibliothèque sci suivante, j'ai implémenté une méthode d'extension pour garantir que l'ensemble de Vector3D maintienne l'ordre lors de l'utilisation d'une méthode d'extension spécifique DistinctKeepOrder:

le code pertinent suit :

/// 
/// classe de support pour l'extension DistinctKeepOrder
/// 
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
{
    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);
    }
}

En résumé, Vector3DWithOrder encapsule le type et un entier d'ordre, tandis que Vector3DWithOrderEqualityComparer encapsule le comparateur de type d'origine.

et voici la méthode d'aide pour garantir le maintien de l'ordre :

/// 
/// récupère les éléments distincts de l'ensemble de vecteurs donné en veillant à maintenir l'ordre donné
///         
public static IEnumerable DistinctKeepOrder(this IEnumerable 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);
}

Remarque : des recherches supplémentaires pourraient permettre de trouver un moyen plus général (utilisation d'interfaces) et optimisé (sans encapsuler l'objet).

Answer 2

Cela dépend fortement de votre fournisseur Linq. Sur Linq2Objects, vous pouvez rester sur le code source interne de Distinct, ce qui laisse supposer que l'ordre original est préservé.

Cependant, pour d'autres fournisseurs qui se résolvent en une sorte de SQL par exemple, ce n'est pas forcément le cas, car une instruction ORDER BY vient généralement après toute agrégation (comme Distinct). Donc si votre code est le suivant :

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

cela se traduit par quelque chose de similaire à ce qui suit en SQL:

SELECT * FROM mytable GROUP BY mycol ORDER BY anothercol;

Cela groupe d'abord vos données et les trie ensuite. Maintenant, vous êtes coincé dans la logique de DBMS sur la façon d'exécuter cela. Sur certains DBMS, cela n'est même pas autorisé. Imaginez les données suivantes :

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

lors de l'exécution de myArr.OrderBy(x => x.anothercol).GroupBy(x => x.mycol) nous assumons le résultat suivant :

mycol anothercol
1     1
2     1

Mais le DBMS peut agréger la colonne anothercol de telle sorte que la valeur de la première ligne soit toujours utilisée, ce qui donne les données suivantes :

mycol anothercol
1    2
2    1

qui après le tri donnera ceci :

mycol anothercol
2    1
1    2

C'est similaire à ce qui suit :

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

ce qui est l'ordre complètement inverse de ce que vous attendiez.

Vous voyez que le plan d'exécution peut varier en fonction du fournisseur sous-jacent. C'est pourquoi il n'y a aucune garantie à ce sujet dans la documentation.