Hält die C # Distinct () -Methode die ursprüngliche Reihenfolge der Sequenz aufrecht?

Ich möchte Duplikate aus der Liste entfernen, ohne die Reihenfolge der eindeutigen Elemente in der Liste zu ändern.

Jon Skeet und andere haben vorgeschlagen, Folgendes zu verwenden

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

Entfernen von Duplikaten aus einer Liste C #

Entfernen Sie Duplikate aus einer Liste <T> in C #

Ist garantiert, dass die Reihenfolge der eindeutigen Elemente dieselbe ist wie zuvor? Wenn ja, geben Sie bitte eine Referenz an, die dies bestätigt, da ich in der Dokumentation nichts darauf finden konnte.

Es ist nicht garantiert, aber es ist die offensichtlichste Implementierung. Es wäre schwierig, sie auf Streaming-Weise zu implementieren (dh so, dass die Ergebnisse so schnell wie möglich zurückgegeben werden, nachdem so wenig wie möglich gelesen wurde), ohne sie in der richtigen Reihenfolge zurückzugeben.

Vielleicht möchten Sie meinen Blog-Beitrag über die Edulinq-Implementierung von Distinct () lesen .

Beachten Sie, dass , auch wenn dies für LINQ to Objects garantiert wurden (was ich persönlich denke , es sollte sein) , dass würde nicht gemein etwas für andere LINQ - Anbieter wie LINQ to SQL.

Die Höhe der Garantien, die in LINQ für Objekte bereitgestellt werden, ist manchmal etwas inkonsistent, IMO. Einige Optimierungen sind dokumentiert, andere nicht. Heck, einige der Dokumentation ist völlig falsch .

In .NET Framework 3.5 zeigt das Zerlegen der CIL der Linq-to-Objects-Implementierung von Distinct(), dass die Reihenfolge der Elemente beibehalten wird - dies ist jedoch kein dokumentiertes Verhalten.

Ich habe eine kleine Untersuchung mit Reflector durchgeführt. Nach dem Zerlegen von System.Core.dll, Version = 3.5.0.0 können Sie sehen, dass Distinct () eine Erweiterungsmethode ist, die folgendermaßen aussieht:

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);
    }
}

Interessant ist hier DistinctIterator, der IEnumerable und IEnumerator implementiert. Hier ist die vereinfachte Implementierung dieses IEnumerators (goto und lables entfernt):

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; }
    }
}

Wie Sie sehen können, erfolgt die Aufzählung in der von der Quelle angegebenen Reihenfolge (Liste, auf der wir aufrufen Distinct). Hashsetwird nur verwendet, um festzustellen, ob wir ein solches Element bereits zurückgegeben haben oder nicht. Wenn nicht, geben wir es zurück, andernfalls - fahren Sie mit der Aufzählung der Quelle fort.

Es ist also garantiert, dass Distinct()Elemente genau in derselben Reihenfolge zurückgegeben werden , die von der Sammlung bereitgestellt werden, auf die Distinct angewendet wurde.

Laut Dokumentation ist die Reihenfolge ungeordnet.

Ja , Enumerable.Distinct bewahrt die Ordnung. Unter der Annahme, dass die Methode faul ist, "wenn sie gesehen wird, ergeben sich unterschiedliche Werte, sobald sie gesehen werden", folgt sie automatisch. Denk darüber nach.

Die .NET-Referenzquelle bestätigt dies. Es gibt eine Teilsequenz zurück, das erste Element in jeder Äquivalenzklasse.

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

Die .NET Core-Implementierung ist ähnlich.

Frustrierend ist die Dokumentation für Enumerable.Distinct in diesem Punkt verwirrt:

Die Ergebnisfolge ist ungeordnet.

Ich kann mir nur vorstellen, dass sie bedeuten "die Ergebnissequenz ist nicht sortiert". Sie könnten Distinct implementieren, indem Sie jedes Element vorsortieren und dann mit dem vorherigen vergleichen. Dies wäre jedoch nicht faul, wie oben definiert.

Wenn Sie den Distinct linq-Operator verwenden, wird standardmäßig die Equals-Methode verwendet. Sie können jedoch mit Ihrem eigenen IEqualityComparer<T>Objekt angeben, wann zwei Objekte mit einer benutzerdefinierten Logikimplementierung GetHashCodeund Equals-methode gleich sind. Erinnere dich daran:

GetHashCodesollte keinen starken CPU-Vergleich verwenden (z. B. nur einige offensichtliche grundlegende Überprüfungen verwenden) und als erstes angeben, ob zwei Objekte sicher unterschiedlich sind (wenn unterschiedliche Hash-Codes zurückgegeben werden) oder möglicherweise gleich (gleicher Hash-Code). In diesem letzten Fall, wenn zwei Objekte denselben Hashcode haben, prüft das Framework mithilfe der Equals-Methode als endgültige Entscheidung über die Gleichheit bestimmter Objekte.

Nachdem Sie MyTypeund eine MyTypeEqualityComparerKlasse Code befolgt haben, stellen Sie nicht sicher, dass die Sequenz ihre Reihenfolge beibehält:

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

In der folgenden Sci-Bibliothek habe ich eine Erweiterungsmethode implementiert, um sicherzustellen, dass das Vector3D-Set die Reihenfolge beibehält, wenn eine bestimmte Erweiterungsmethode verwendet wird DistinctKeepOrder:

relevanter Code folgt:

/// <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);
    }
}

Kurz gesagt, Vector3DWithOrderkapseln Sie den Typ und eine Ordnungszahl, während der Vector3DWithOrderEqualityComparerursprüngliche Typvergleicher gekapselt wird.

und dies ist der Methodenhelfer, um die Aufrechterhaltung der Ordnung sicherzustellen

/// <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);
}

Hinweis : Weitere Untersuchungen könnten es ermöglichen, einen allgemeineren (Verwendung von Schnittstellen) und optimierten Weg zu finden (ohne das Objekt zu kapseln).

Dies hängt stark von Ihrem Linq-Anbieter ab. Bei Linq2Objects können Sie den internen Quellcode für Distinctbeibehalten, wodurch davon ausgegangen wird, dass die ursprüngliche Reihenfolge erhalten bleibt.

Bei anderen Anbietern, die sich beispielsweise auf eine Art von SQL auflösen, ist dies jedoch nicht unbedingt der Fall, da eine ORDER BYAnweisung normalerweise nach einer Aggregation (z. B. Distinct) erfolgt. Wenn Ihr Code also folgendermaßen lautet:

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

Dies wird in SQL in etwas Ähnliches übersetzt:

SELECT * FROM mytable GROUP BY mycol ORDER BY anothercol;

Dies gruppiert offensichtlich zuerst Ihre Daten und sortiert sie anschließend. Jetzt bleiben Sie bei der DBMS-eigenen Logik, wie das ausgeführt werden soll. Bei einigen DBMS ist dies nicht einmal erlaubt. Stellen Sie sich folgende Daten vor:

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

Bei der Ausführung myArr.OrderBy(x => x.anothercol).GroupBy(x => x.mycol)gehen wir von folgendem Ergebnis aus:

mycol anothercol
1     1
2     1

Das DBMS kann jedoch eine andere Spalte zusammenfassen, sodass immer der Wert der ersten Zeile verwendet wird, was zu den folgenden Daten führt:

mycol anothercol
1    2
2    1

was nach der Bestellung dazu führt:

mycol anothercol
2    1
1    2

Dies ähnelt dem Folgenden:

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

Das ist die völlig umgekehrte Reihenfolge als erwartet.

Sie sehen, dass der Ausführungsplan je nach dem zugrunde liegenden Anbieter variieren kann. Aus diesem Grund gibt es in den Dokumenten keine Garantie dafür.