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

487

Hat jemand eine schnelle Methode zum Deduplizieren einer generischen Liste in C #?

JC Grubbs
quelle
4
Interessiert Sie die Reihenfolge der Elemente im Ergebnis? Dies schließt einige Lösungen aus.
Colonel Panic
Eine einzeilige Lösung:ICollection<MyClass> withoutDuplicates = new HashSet<MyClass>(inputList);
Harald Coppoolse

Antworten:

227

Vielleicht sollten Sie ein HashSet verwenden .

Über den MSDN-Link:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        HashSet<int> evenNumbers = new HashSet<int>();
        HashSet<int> oddNumbers = new HashSet<int>();

        for (int i = 0; i < 5; i++)
        {
            // Populate numbers with just even numbers.
            evenNumbers.Add(i * 2);

            // Populate oddNumbers with just odd numbers.
            oddNumbers.Add((i * 2) + 1);
        }

        Console.Write("evenNumbers contains {0} elements: ", evenNumbers.Count);
        DisplaySet(evenNumbers);

        Console.Write("oddNumbers contains {0} elements: ", oddNumbers.Count);
        DisplaySet(oddNumbers);

        // Create a new HashSet populated with even numbers.
        HashSet<int> numbers = new HashSet<int>(evenNumbers);
        Console.WriteLine("numbers UnionWith oddNumbers...");
        numbers.UnionWith(oddNumbers);

        Console.Write("numbers contains {0} elements: ", numbers.Count);
        DisplaySet(numbers);
    }

    private static void DisplaySet(HashSet<int> set)
    {
        Console.Write("{");
        foreach (int i in set)
        {
            Console.Write(" {0}", i);
        }
        Console.WriteLine(" }");
    }
}

/* This example produces output similar to the following:
 * evenNumbers contains 5 elements: { 0 2 4 6 8 }
 * oddNumbers contains 5 elements: { 1 3 5 7 9 }
 * numbers UnionWith oddNumbers...
 * numbers contains 10 elements: { 0 2 4 6 8 1 3 5 7 9 }
 */
Jason Baker
quelle
11
Es ist unglaublich schnell ... 100.000 Strings mit List benötigen 400s und 8MB RAM, meine eigene Lösung dauert 2,5s und 28MB, Hashset dauert 0.1s !!! und 11 MB RAM
Sasjaq
3
HashSet hat keinen Index , daher ist es nicht immer möglich, ihn zu verwenden. Ich muss einmal eine riesige Liste ohne Duplikate erstellen und sie dann ListViewim virtuellen Modus verwenden. Es war superschnell, HashSet<>zuerst eine zu erstellen und sie dann in eine umzuwandeln List<>(so ListViewkann über den Index auf Elemente zugegriffen werden). List<>.Contains()ist zu langsam.
Sinatr
58
Wäre hilfreich, wenn es ein Beispiel für die Verwendung eines Hashsets in diesem speziellen Kontext gäbe.
Nathan McKaskle
23
Wie kann dies als Antwort angesehen werden? Es ist ein Link
mcont
2
HashSet ist in den meisten Fällen großartig. Wenn Sie jedoch ein Objekt wie DateTime haben, wird es nach Referenz und nicht nach Wert verglichen, sodass Sie immer noch Duplikate erhalten.
Jason McKindly
813

Wenn Sie .Net 3+ verwenden, können Sie Linq verwenden.

List<T> withDupes = LoadSomeData();
List<T> noDupes = withDupes.Distinct().ToList();
Faktor Mystic
quelle
14
Dieser Code schlägt fehl, da .Distinct () eine IEnumerable <T> zurückgibt. Sie müssen .ToList () hinzufügen.
ljs
Dieser Ansatz kann nur für Listen mit einfachen Werten verwendet werden.
Polaris
20
Nein, es funktioniert mit Listen, die Objekte jeglichen Typs enthalten. Sie müssen jedoch den Standardvergleicher für Ihren Typ überschreiben. Wie so: public override bool Equals (Objekt obj) {...}
BaBu
1
Es ist immer eine gute Idee, ToString () und GetHashCode () mit Ihren Klassen zu überschreiben, damit so etwas funktioniert.
B Sieben
2
Sie können auch das MoreLinQ Nuget-Paket verwenden, das die Erweiterungsmethode .DistinctBy () enthält. Ziemlich nützlich.
yu_ominae
178

Wie wäre es mit:

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

In .net 3.5?

ljs
quelle
Dupliziert es die Liste?
Darkgaze
1
@darkgaze dies erstellt nur eine weitere Liste mit nur eindeutigen Einträgen. Duplikate werden also entfernt und Sie erhalten eine Liste, in der jede Position ein anderes Objekt hat.
Hexagod
Funktioniert dies für die Liste der Listenelemente, bei denen die
Elementcodes
90

Initialisieren Sie einfach ein HashSet mit einer Liste des gleichen Typs:

var noDupes = new HashSet<T>(withDupes);

Oder wenn Sie eine Liste zurückgeben möchten:

var noDupsList = new HashSet<T>(withDupes).ToList();
Sogar Mien
quelle
3
... und wenn Sie eine List<T>als Ergebnis benötigennew HashSet<T>(withDupes).ToList()
Tim Schmelter
47

Sortieren Sie es und überprüfen Sie zwei und zwei nebeneinander, da die Duplikate zusammenklumpen.

Etwas wie das:

list.Sort();
Int32 index = list.Count - 1;
while (index > 0)
{
    if (list[index] == list[index - 1])
    {
        if (index < list.Count - 1)
            (list[index], list[list.Count - 1]) = (list[list.Count - 1], list[index]);
        list.RemoveAt(list.Count - 1);
        index--;
    }
    else
        index--;
}

Anmerkungen:

  • Der Vergleich erfolgt von hinten nach vorne, um zu vermeiden, dass die Liste nach jedem Entfernen neu erstellt werden muss
  • In diesem Beispiel werden jetzt C # -Wert-Tupel für den Austausch verwendet. Ersetzen Sie diesen durch geeigneten Code, wenn Sie diesen nicht verwenden können
  • Das Endergebnis wird nicht mehr sortiert
Lasse V. Karlsen
quelle
1
Wenn ich mich nicht irre, sind die meisten der oben genannten Ansätze nur Abstraktionen dieser Routinen, oder? Ich hätte hier Ihren Ansatz gewählt, Lasse, weil ich mir mental vorstelle, wie ich mich durch Daten bewege. Aber jetzt interessieren mich Leistungsunterschiede zwischen einigen der Vorschläge.
Ian Patrick Hughes
7
Implementieren Sie sie und planen Sie sie, nur um sicherzugehen. Selbst die Big-O-Notation hilft Ihnen nicht bei den tatsächlichen Leistungsmetriken, sondern nur bei einer Beziehung mit Wachstumseffekten.
Lasse V. Karlsen
1
Ich mag diesen Ansatz, er ist portabler für andere Sprachen.
Jerry Liang
10
Tu das nicht. Es ist super langsam. RemoveAtist eine sehr kostspielige Operation an einemList
Clément
1
Clément hat recht. Eine Möglichkeit, dies zu beheben, besteht darin, dies in eine Methode zu verpacken, die mit einem Enumerator liefert und nur unterschiedliche Werte zurückgibt. Alternativ können Sie Werte in ein neues Array oder eine neue Liste kopieren.
JHubbard80
33

Ich benutze gerne diesen Befehl:

List<Store> myStoreList = Service.GetStoreListbyProvince(provinceId)
                                                 .GroupBy(s => s.City)
                                                 .Select(grp => grp.FirstOrDefault())
                                                 .OrderBy(s => s.City)
                                                 .ToList();

Ich habe diese Felder in meiner Liste: ID, Geschäftsname, Stadt, Postleitzahl Ich wollte eine Liste der Städte in einer Dropdown-Liste mit doppelten Werten anzeigen. Lösung: Nach Stadt gruppieren und dann die erste für die Liste auswählen.

Ich hoffe, es hilft :)

Eric
quelle
31

Es hat bei mir funktioniert. einfach benutzen

List<Type> liIDs = liIDs.Distinct().ToList<Type>();

Ersetzen Sie "Typ" durch Ihren gewünschten Typ, z. B. int.

Hossein Sarshar
quelle
1
Distinct ist in Linq, nicht in System.Collections.Generic, wie auf der MSDN-Seite angegeben.
Almo
5
Diese Antwort (2012) scheint die gleiche zu sein wie zwei andere Antworten auf dieser Seite, die aus dem Jahr 2008 stammen.
Jon Schneider
23

Wie kronoz in .Net 3.5 sagte, können Sie verwenden Distinct() .

In .Net 2 können Sie es nachahmen:

public IEnumerable<T> DedupCollection<T> (IEnumerable<T> input) 
{
    var passedValues = new HashSet<T>();

    // Relatively simple dupe check alg used as example
    foreach(T item in input)
        if(passedValues.Add(item)) // True if item is new
            yield return item;
}

Dies kann zum Deduplizieren einer Sammlung verwendet werden und gibt die Werte in der ursprünglichen Reihenfolge zurück.

Normalerweise ist es viel schneller, eine Sammlung zu filtern (wie beides Distinct()und dieses Beispiel), als Elemente daraus zu entfernen.

Keith
quelle
Das Problem bei diesem Ansatz ist jedoch, dass es im Gegensatz zu einem Hashset O (N ^ 2) -isch ist. Aber zumindest ist es offensichtlich, was es tut.
Tamas Czinege
1
@DrJokepu - eigentlich habe ich nicht HashSetbemerkt, dass der Konstruktor dedupiert hat, was es für die meisten Umstände besser macht. Dies würde jedoch die Sortierreihenfolge beibehalten, was a HashSetnicht tut.
Keith
1
HashSet <T> wurde in 3.5 eingeführt
THORN
1
@ Dorn wirklich? So schwer den Überblick zu behalten. In diesem Fall könnten Sie nur verwenden Dictionary<T, object>stattdessen ersetzen .Containsmit .ContainsKeyund .Add(item)mit.Add(item, null)
Keith
@Keith, gemäß meinen Tests HashSetbleibt die Ordnung erhalten, während Distinct()dies nicht der Fall ist.
Dennis T - Reinstate Monica -
13

Eine Erweiterungsmethode könnte ein guter Weg sein ... so etwas:

public static List<T> Deduplicate<T>(this List<T> listToDeduplicate)
{
    return listToDeduplicate.Distinct().ToList();
}

Und dann rufen Sie zum Beispiel so an:

List<int> myFilteredList = unfilteredList.Deduplicate();
Geoff Taylor
quelle
11

In Java (ich nehme an, C # ist mehr oder weniger identisch):

list = new ArrayList<T>(new HashSet<T>(list))

Wenn Sie die ursprüngliche Liste wirklich mutieren wollten:

List<T> noDupes = new ArrayList<T>(new HashSet<T>(list));
list.clear();
list.addAll(noDupes);

Um die Ordnung zu erhalten, ersetzen Sie einfach HashSet durch LinkedHashSet.

Tom Hawtin - Tackline
quelle
5
in C # wäre es: Liste <T> noDupes = neue Liste <T> (neues HashSet <T> (Liste)); list.Clear (); list.AddRange (noDupes);
Smohamed
In C # ist es einfacher so: var noDupes = new HashSet<T>(list); list.Clear(); list.AddRange(noDupes);:)
Nawfal
10

Dies nimmt verschiedene (die Elemente ohne doppelte Elemente) und konvertiert es wieder in eine Liste:

List<type> myNoneDuplicateValue = listValueWithDuplicate.Distinct().ToList();
Alfred Udah
quelle
9

Verwenden Sie die Union- Methode von Linq .

Hinweis: Diese Lösung erfordert keine Kenntnisse von Linq, abgesehen davon, dass sie vorhanden ist.

Code

Fügen Sie zunächst Folgendes oben in Ihre Klassendatei ein:

using System.Linq;

Jetzt können Sie Folgendes verwenden, um Duplikate aus einem Objekt mit dem Namen zu entfernen obj1:

obj1 = obj1.Union(obj1).ToList();

Hinweis: Benennen Sie obj1in den Namen Ihres Objekts um.

Wie es funktioniert

  1. Der Befehl Union listet jeweils einen Eintrag von zwei Quellobjekten auf. Da obj1 beide Quellobjekte sind, reduziert dies obj1 auf einen von jedem Eintrag.

  2. Das ToList()gibt eine neue Liste zurück. Dies ist erforderlich, da Linq-Befehle wie Uniondas Ergebnis als IEnumerable-Ergebnis zurückgeben, anstatt die ursprüngliche Liste zu ändern oder eine neue Liste zurückzugeben.

WonderWorker
quelle
7

Als Hilfsmethode (ohne Linq):

public static List<T> Distinct<T>(this List<T> list)
{
    return (new HashSet<T>(list)).ToList();
}
Gewähren
quelle
Ich denke, Distinct ist bereits vergeben. Abgesehen davon (wenn Sie die Methode umbenennen) sollte es funktionieren.
Andreas Reiff
6

Wenn Sie nicht über die Bestellung kümmern können Sie nur die Einzelteile in einen Schub HashSet, wenn Sie tun , um die Bestellung erhalten wollen Sie etwas tun können:

var unique = new List<T>();
var hs = new HashSet<T>();
foreach (T t in list)
    if (hs.Add(t))
        unique.Add(t);

Oder der Linq-Weg:

var hs = new HashSet<T>();
list.All( x =>  hs.Add(x) );

Bearbeiten: Die HashSetMethode ist O(N)Zeit und O(N)Raum beim Sortieren und dann einzigartig zu machen (wie von @ lassevk und anderen vorgeschlagen) ist O(N*lgN)Zeit und O(1)Raum, daher ist mir (wie auf den ersten Blick) nicht so klar, dass die Sortierweise minderwertig ist (meine Entschuldigung für die vorübergehende Abstimmung ...)

Motti
quelle
6

Hier ist eine Erweiterungsmethode zum Entfernen benachbarter Duplikate vor Ort. Rufen Sie zuerst Sort () auf und übergeben Sie denselben IComparer. Dies sollte effizienter sein als die Version von Lasse V. Karlsen, die RemoveAt wiederholt aufruft (was zu mehreren Blockspeicherverschiebungen führt).

public static void RemoveAdjacentDuplicates<T>(this List<T> List, IComparer<T> Comparer)
{
    int NumUnique = 0;
    for (int i = 0; i < List.Count; i++)
        if ((i == 0) || (Comparer.Compare(List[NumUnique - 1], List[i]) != 0))
            List[NumUnique++] = List[i];
    List.RemoveRange(NumUnique, List.Count - NumUnique);
}
Gary
quelle
5

Wenn Sie das MoreLINQ- Paket über Nuget installieren, können Sie die Objektliste leicht anhand einer Eigenschaft unterscheiden

IEnumerable<Catalogue> distinctCatalogues = catalogues.DistinctBy(c => c.CatalogueCode); 
dush88c
quelle
3

Es könnte einfacher sein, einfach sicherzustellen, dass der Liste keine Duplikate hinzugefügt werden.

if(items.IndexOf(new_item) < 0) 
    items.add(new_item)
Chris
quelle
1
Ich mache es momentan so, aber je mehr Einträge Sie haben, desto länger dauert die Prüfung auf Duplikate.
Robert Strauch
Ich habe hier das gleiche Problem. Ich verwende die List<T>.ContainsMethode jedes Mal, aber mit mehr als 1.000.000 Einträgen. Dieser Prozess verlangsamt meine Bewerbung. Ich benutze List<T>.Distinct().ToList<T>()stattdessen eine erste.
RPDeshaies
Diese Methode ist sehr langsam
Darkgaze
3

Sie können Union verwenden

obj2 = obj1.Union(obj1).ToList();
Flagamba
quelle
7
Erklärung, warum es funktionieren würde, würde diese Antwort definitiv verbessern
Igor B
2

Ein anderer Weg in .Net 2.0

    static void Main(string[] args)
    {
        List<string> alpha = new List<string>();

        for(char a = 'a'; a <= 'd'; a++)
        {
            alpha.Add(a.ToString());
            alpha.Add(a.ToString());
        }

        Console.WriteLine("Data :");
        alpha.ForEach(delegate(string t) { Console.WriteLine(t); });

        alpha.ForEach(delegate (string v)
                          {
                              if (alpha.FindAll(delegate(string t) { return t == v; }).Count > 1)
                                  alpha.Remove(v);
                          });

        Console.WriteLine("Unique Result :");
        alpha.ForEach(delegate(string t) { Console.WriteLine(t);});
        Console.ReadKey();
    }
Bhasin
quelle
2

Es gibt viele Möglichkeiten, das Problem zu lösen. Das Problem mit den Duplikaten in der folgenden Liste ist eine davon:

List<Container> containerList = LoadContainer();//Assume it has duplicates
List<Container> filteredList = new  List<Container>();
foreach (var container in containerList)
{ 
  Container duplicateContainer = containerList.Find(delegate(Container checkContainer)
  { return (checkContainer.UniqueId == container.UniqueId); });
   //Assume 'UniqueId' is the property of the Container class on which u r making a search

    if(!containerList.Contains(duplicateContainer) //Add object when not found in the new class object
      {
        filteredList.Add(container);
       }
  }

Prost Ravi Ganesan

Ravi Ganesan
quelle
2

Hier ist eine einfache Lösung, die keinen schwer lesbaren LINQ oder eine vorherige Sortierung der Liste erfordert.

   private static void CheckForDuplicateItems(List<string> items)
    {
        if (items == null ||
            items.Count == 0)
            return;

        for (int outerIndex = 0; outerIndex < items.Count; outerIndex++)
        {
            for (int innerIndex = 0; innerIndex < items.Count; innerIndex++)
            {
                if (innerIndex == outerIndex) continue;
                if (items[outerIndex].Equals(items[innerIndex]))
                {
                    // Duplicate Found
                }
            }
        }
    }
David J.
quelle
Mit dieser Methode haben Sie mehr Kontrolle über doppelte Elemente. Noch mehr, wenn Sie eine Datenbank aktualisieren müssen. Warum nicht für den innerIndex von OuterIndex + 1 ausgehen, sondern jedes Mal von vorne beginnen?
Nolmë Informatique
2

Die Antwort von David J. ist eine gute Methode, die keine zusätzlichen Objekte, Sortierungen usw. erfordert. Sie kann jedoch verbessert werden:

for (int innerIndex = items.Count - 1; innerIndex > outerIndex ; innerIndex--)

Die äußere Schleife geht also für die gesamte Liste nach oben, die innere Schleife nach unten, "bis die Position der äußeren Schleife erreicht ist".

Die äußere Schleife stellt sicher, dass die gesamte Liste verarbeitet wird, die innere Schleife findet die tatsächlichen Duplikate. Diese können nur in dem Teil auftreten, den die äußere Schleife noch nicht verarbeitet hat.

Oder wenn Sie für die innere Schleife nicht von unten nach oben arbeiten möchten, kann die innere Schleife bei OuterIndex + 1 beginnen.

Gast
quelle
2

Alle Antworten kopieren Listen oder erstellen eine neue Liste oder verwenden langsame Funktionen oder sind nur schmerzhaft langsam.

Nach meinem Verständnis ist dies die schnellste und billigste Methode, die ich kenne (auch unterstützt von einem sehr erfahrenen Programmierer, der auf Echtzeit-Physikoptimierung spezialisiert ist).

// Duplicates will be noticed after a sort O(nLogn)
list.Sort();

// Store the current and last items. Current item declaration is not really needed, and probably optimized by the compiler, but in case it's not...
int lastItem = -1;
int currItem = -1;

int size = list.Count;

// Store the index pointing to the last item we want to keep in the list
int last = size - 1;

// Travel the items from last to first O(n)
for (int i = last; i >= 0; --i)
{
    currItem = list[i];

    // If this item was the same as the previous one, we don't want it
    if (currItem == lastItem)
    {
        // Overwrite last in current place. It is a swap but we don't need the last
       list[i] = list[last];

        // Reduce the last index, we don't want that one anymore
        last--;
    }

    // A new item, we store it and continue
    else
        lastItem = currItem;
}

// We now have an unsorted list with the duplicates at the end.

// Remove the last items just once
list.RemoveRange(last + 1, size - last - 1);

// Sort again O(n logn)
list.Sort();

Die endgültigen Kosten betragen:

nlogn + n + nlogn = n + 2nlogn = O (nlogn), was ziemlich nett ist.

Hinweis zu RemoveRange: Da wir die Anzahl der Listen nicht festlegen und die Verwendung der Remove-Funktionen vermeiden können, weiß ich nicht genau, wie schnell dieser Vorgang ausgeführt wird, aber ich denke, dies ist der schnellste Weg.

darkgaze
quelle
2

Wenn Sie zwei Klassen haben Productund Customerwir doppelte Elemente aus ihrer Liste entfernen möchten

public class Product
{
    public int Id { get; set; }
    public string ProductName { get; set; }
}

public class Customer
{
    public int Id { get; set; }
    public string CustomerName { get; set; }

}

Sie müssen eine generische Klasse im folgenden Formular definieren

public class ItemEqualityComparer<T> : IEqualityComparer<T> where T : class
{
    private readonly PropertyInfo _propertyInfo;

    public ItemEqualityComparer(string keyItem)
    {
        _propertyInfo = typeof(T).GetProperty(keyItem, BindingFlags.GetProperty | BindingFlags.Instance | BindingFlags.Public);
    }

    public bool Equals(T x, T y)
    {
        var xValue = _propertyInfo?.GetValue(x, null);
        var yValue = _propertyInfo?.GetValue(y, null);
        return xValue != null && yValue != null && xValue.Equals(yValue);
    }

    public int GetHashCode(T obj)
    {
        var propertyValue = _propertyInfo.GetValue(obj, null);
        return propertyValue == null ? 0 : propertyValue.GetHashCode();
    }
}

Anschließend können Sie doppelte Elemente in Ihrer Liste entfernen.

var products = new List<Product>
            {
                new Product{ProductName = "product 1" ,Id = 1,},
                new Product{ProductName = "product 2" ,Id = 2,},
                new Product{ProductName = "product 2" ,Id = 4,},
                new Product{ProductName = "product 2" ,Id = 4,},
            };
var productList = products.Distinct(new ItemEqualityComparer<Product>(nameof(Product.Id))).ToList();

var customers = new List<Customer>
            {
                new Customer{CustomerName = "Customer 1" ,Id = 5,},
                new Customer{CustomerName = "Customer 2" ,Id = 5,},
                new Customer{CustomerName = "Customer 2" ,Id = 5,},
                new Customer{CustomerName = "Customer 2" ,Id = 5,},
            };
var customerList = customers.Distinct(new ItemEqualityComparer<Customer>(nameof(Customer.Id))).ToList();

dieser Code entfernen doppelte Elemente durch , Idwenn Sie doppelte Elemente von anderer Eigenschaft wollen entfernen, können Sie ändern , nameof(YourClass.DuplicateProperty) gleichen nameof(Customer.CustomerName)dann doppelte Elemente durch Entfernen der CustomerNameImmobilie.

Reza Jenabi
quelle
1
  public static void RemoveDuplicates<T>(IList<T> list )
  {
     if (list == null)
     {
        return;
     }
     int i = 1;
     while(i<list.Count)
     {
        int j = 0;
        bool remove = false;
        while (j < i && !remove)
        {
           if (list[i].Equals(list[j]))
           {
              remove = true;
           }
           j++;
        }
        if (remove)
        {
           list.RemoveAt(i);
        }
        else
        {
           i++;
        }
     }  
  }
Paul Richards
quelle
1

Eine einfache intuitive Implementierung:

public static List<PointF> RemoveDuplicates(List<PointF> listPoints)
{
    List<PointF> result = new List<PointF>();

    for (int i = 0; i < listPoints.Count; i++)
    {
        if (!result.Contains(listPoints[i]))
            result.Add(listPoints[i]);
        }

        return result;
    }
Moctar Haiz
quelle
Diese Methode ist ebenfalls langsam. Erstellt eine neue Liste.
Darkgaze