Usuń duplikaty z listy <T> w C #

487

Czy ktoś ma szybką metodę usuwania duplikatów ogólnej listy w C #?

JC Grubbs
źródło
4
Czy zależy Ci na kolejności elementów w wyniku? Wyklucza to niektóre rozwiązania.
Pułkownik Panic
Jedno liniowe rozwiązanie:ICollection<MyClass> withoutDuplicates = new HashSet<MyClass>(inputList);
Harald Coppoolse

Odpowiedzi:

227

Być może powinieneś rozważyć użycie HashSet .

Z linku MSDN:

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
źródło
11
jego niewiarygodne szybkie ... 100 000 ciągów z List zajmuje 400s i 8 MB pamięci RAM, moje własne rozwiązanie zajmuje 2,5s i 28 MB, hashset zajmuje 0,1s !!! i 11 MB
pamięci
3
HashSet nie ma indeksu , dlatego nie zawsze można go używać. Raz muszę stworzyć ogromną listę bez duplikatów, a następnie użyć jej ListVieww trybie wirtualnym. Bardzo szybko było zrobić HashSet<>pierwszy, a następnie przekształcić go w List<>(dzięki czemu ListViewmożna uzyskać dostęp do przedmiotów według indeksu). List<>.Contains()jest zbyt wolny.
Sinatr
58
Pomógłby, gdyby istniał przykład użycia skrótu w tym konkretnym kontekście.
Nathan McKaskle
23
Jak można to uznać za odpowiedź? To jest link
mcont
2
HashSet jest świetny w większości przypadków. Ale jeśli masz obiekt taki jak DateTime, będzie on porównywany przez odniesienie, a nie według wartości, więc nadal będziesz mieć duplikaty.
Jason McKindly,
813

Jeśli używasz .Net 3+, możesz użyć Linq.

List<T> withDupes = LoadSomeData();
List<T> noDupes = withDupes.Distinct().ToList();
Factor Mystic
źródło
14
Ten kod zawiedzie, ponieważ funkcja .Distinct () zwraca wartość IEnumerable <T>. Musisz do niego dodać .ToList ().
ljs
Tego podejścia można użyć tylko w przypadku list o prostych wartościach.
Polaris,
20
Nie, działa z listami zawierającymi obiekty dowolnego typu. Ale będziesz musiał zastąpić domyślny moduł porównujący dla swojego typu. Tak jak: public override bool Equals (object obj) {...}
BaBu
1
Zawsze dobrym pomysłem jest zastąpienie ToString () i GetHashCode () w swoich klasach, aby tego rodzaju rzeczy działały.
B, 7
2
Możesz także użyć pakietu MoreLinQ Nuget, który ma metodę rozszerzenia .DistinctBy (). Całkiem przydatne.
yu_ominae
178

Co powiesz na:

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

W .net 3.5?

ljs
źródło
Czy to powiela listę?
darkgaze
1
@darkgaze tworzy tylko kolejną listę z unikalnymi wpisami. Więc wszelkie duplikaty zostaną usunięte, a ty zostaniesz z listą, w której każda pozycja ma inny obiekt.
hexagod
Czy to działa w przypadku listy elementów listy, w których kody pozycji są zduplikowane i musi uzyskać unikalną listę
venkat
90

Po prostu zainicjuj zestaw HashSet za pomocą listy tego samego typu:

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

Lub, jeśli chcesz zwrócić listę:

var noDupsList = new HashSet<T>(withDupes).ToList();
Nawet Mien
źródło
3
... a jeśli potrzebujesz List<T>wyniku, użyjnew HashSet<T>(withDupes).ToList()
Tim Schmelter
47

Posortuj, a następnie zaznacz dwa i dwa obok siebie, ponieważ duplikaty będą się zlepiać.

Coś takiego:

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

Uwagi:

  • Porównanie odbywa się od tyłu do przodu, aby uniknąć konieczności uciekania się do listy po każdym usunięciu
  • W tym przykładzie używa się teraz krotek wartości C # do wymiany, w razie potrzeby zastąp odpowiedni kod
  • Wynik końcowy nie jest już sortowany
Lasse V. Karlsen
źródło
1
Jeśli się nie mylę, większość wyżej wymienionych podejść to tylko abstrakcje tych rutynowych czynności, prawda? Przyjąłbym twoje podejście tutaj, Lasse, ponieważ tak wyobrażam sobie ruchy danych. Ale teraz interesują mnie różnice w wydajności między niektórymi sugestiami.
Ian Patrick Hughes,
7
Wdrażaj je i określaj czas, to jedyny sposób, aby się upewnić. Nawet notacja Big-O nie pomoże ci w rzeczywistych wskaźnikach wydajności, a jedynie w relacji do efektu wzrostu.
Lasse V. Karlsen
1
Podoba mi się to podejście, jest bardziej przenośne na inne języki.
Jerry Liang
10
Nie rób tego Jest bardzo wolny. RemoveAtjest bardzo kosztowną operacją naList
Clément
1
Clément ma rację. Sposobem na odzyskanie tego byłoby zawinięcie tego w metodę, która daje za pomocą modułu wyliczającego i zwraca tylko odrębne wartości. Alternatywnie możesz skopiować wartości do nowej tablicy lub listy.
JHubbard80,
33

Lubię używać tego polecenia:

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

Mam na liście następujące pola: Id, StoreName, City, PostalCode Chciałem wyświetlić listę miast w menu, które ma zduplikowane wartości. rozwiązanie: Grupuj według miasta, a następnie wybierz pierwszą z listy.

Mam nadzieję, że to pomoże :)

Eric
źródło
31

To zadziałało dla mnie. po prostu użyj

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

Zamień „Type” na żądany typ, np. Int.

Hossein Sarshar
źródło
1
Wyróżnia się w Linq, a nie System.Collections.Generic, jak podano na stronie MSDN.
Almo
5
Ta odpowiedź (2012) wydaje się być taka sama jak dwie inne odpowiedzi na tej stronie z 2008 roku?
Jon Schneider
23

Jak powiedział kronoz w .Net 3.5, możesz używać Distinct().

W .Net 2 możesz to naśladować:

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

Można to wykorzystać do deduplikacji dowolnej kolekcji i zwróci wartości w oryginalnej kolejności.

Zazwyczaj filtrowanie kolekcji jest znacznie szybsze (tak jak w przypadku Distinct()tej i tej próbki), niż usuwanie jej z niej.

Keith
źródło
Problem z tym podejściem polega jednak na tym, że jest on O (N ^ 2), w przeciwieństwie do hashsetu. Ale przynajmniej jest oczywiste, co robi.
Tamas Czinege
1
@DrJokepu - właściwie nie zdawałem sobie sprawy z tego, że HashSetkonstruktor się poświęcił, co czyni go lepszym w większości przypadków. Zachowałoby to jednak porządek sortowania, czego HashSetnie robi.
Keith
1
HashSet <T> został wprowadzony w 3.5
thorn̈
1
@ cierń naprawdę? Tak trudno nadążyć. W takim przypadku można po prostu użyć Dictionary<T, object>zamiast wymienić .Containsz .ContainsKeyi .Add(item)z.Add(item, null)
Keitha
@ Keith, zgodnie z moim testowaniem HashSetzachowuje porządek, podczas gdy Distinct()nie.
Dennis T - Przywróć Monikę--
13

Metoda rozszerzenia może być dobrym sposobem ... coś takiego:

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

A potem zadzwoń w ten sposób, na przykład:

List<int> myFilteredList = unfilteredList.Deduplicate();
Geoff Taylor
źródło
11

W Javie (zakładam, że C # jest mniej więcej identyczny):

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

Jeśli naprawdę chcesz zmutować oryginalną listę:

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

Aby zachować porządek, po prostu zamień HashSet na LinkedHashSet.

Tom Hawtin - tackline
źródło
5
w języku C # byłoby to: List <T> noDupes = nowa lista <T> (nowy HashSet <T> (lista)); list.Clear (); list.AddRange (noDupes);
smohamed
W języku C # łatwiej jest w ten sposób: var noDupes = new HashSet<T>(list); list.Clear(); list.AddRange(noDupes);:)
nawfal
10

Spowoduje to rozróżnienie (elementy bez powielania elementów) i ponowne przekonwertowanie go na listę:

List<type> myNoneDuplicateValue = listValueWithDuplicate.Distinct().ToList();
Alfred Udah
źródło
9

Użyj metody Union Linq .

Uwaga: To rozwiązanie nie wymaga znajomości Linq, poza tym, że istnieje.

Kod

Zacznij od dodania następujących elementów na początku pliku zajęć:

using System.Linq;

Teraz możesz użyć następujących poleceń, aby usunąć duplikaty z obiektu o nazwie obj1:

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

Uwaga: Zmień nazwę obj1na nazwę swojego obiektu.

Jak to działa

  1. Polecenie Union wyświetla jeden z każdego wpisu dwóch obiektów źródłowych. Ponieważ obj1 jest oboma obiektami źródłowymi, redukuje obj1 do jednego z każdego wpisu.

  2. ToList()Zwraca nową listę. Jest to konieczne, ponieważ polecenia Linq, takie jak Unionzwraca wynik jako wynik IEnumerable zamiast modyfikować oryginalną Listę lub zwracać nową Listę.

WonderWorker
źródło
7

Jako metoda pomocnicza (bez Linq):

public static List<T> Distinct<T>(this List<T> list)
{
    return (new HashSet<T>(list)).ToList();
}
Dotacja
źródło
Myślę, że Distinct jest już zajęty. Poza tym (jeśli zmienisz nazwę metody) powinna działać.
Andreas Reiff,
6

Jeśli nie dbają o porządek można po prostu wsadzić elementy do HashSet, jeśli nie chcesz, aby utrzymać porządek można zrobić coś takiego:

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

Lub sposób Linq:

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

Edit:HashSet metoda jest O(N)czas i O(N)miejsce podczas sortowania a następnie podejmowania wyjątkowy (jak sugeruje @ lassevk i innych) jest O(N*lgN)czas i O(1)przestrzeń, więc to nie jest tak oczywiste dla mnie (jak to było na pierwszy rzut oka), że sposób sortowania jest gorszy (moja przepraszam za tymczasowe głosowanie w dół ...)

Motti
źródło
6

Oto metoda rozszerzenia służąca do usuwania sąsiadujących duplikatów na miejscu. Najpierw wywołaj Sort () i przekaż ten sam IComparer. Powinno to być bardziej wydajne niż wersja Lasse V. Karlsena, która wielokrotnie wywołuje RemoveAt (co powoduje wiele ruchów pamięci bloków).

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
źródło
5

Instalując pakiet MoreLINQ za pośrednictwem Nuget, możesz łatwo odróżnić listę obiektów według właściwości

IEnumerable<Catalogue> distinctCatalogues = catalogues.DistinctBy(c => c.CatalogueCode); 
dush88c
źródło
3

Łatwiej może być po prostu upewnienie się, że duplikaty nie zostaną dodane do listy.

if(items.IndexOf(new_item) < 0) 
    items.add(new_item)
Chris
źródło
1
Obecnie robię to w ten sposób, ale im więcej wpisów, tym dłużej trwa sprawdzanie duplikatów.
Robert Strauch
Mam tutaj ten sam problem. Używam tej List<T>.Containsmetody za każdym razem, ale z ponad 1 000 000 wpisów. Ten proces spowalnia moją aplikację. List<T>.Distinct().ToList<T>()Zamiast tego używam pierwszego.
RPDeshaies
Ta metoda jest bardzo powolna
darkgaze
3

Możesz użyć Union

obj2 = obj1.Union(obj1).ToList();
flagamba
źródło
7
Wyjaśnienie, dlaczego miałoby to zadziałać, zdecydowanie poprawiłoby tę odpowiedź
Igor B
2

Kolejny sposób w .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
źródło
2

Istnieje wiele sposobów rozwiązania - problem duplikatów na liście, poniżej jest jednym z nich:

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

Pozdrawiam Ravi Ganesan

Ravi Ganesan
źródło
2

Oto proste rozwiązanie, które nie wymaga trudnego do odczytania LINQ ani żadnego wcześniejszego sortowania listy.

   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.
źródło
Dzięki tej metodzie masz większą kontrolę nad zduplikowanymi elementami. Co więcej, jeśli masz bazę danych do aktualizacji. W przypadku innerIndex, dlaczego nie zaczynać od outerIndex + 1 zamiast zaczynać od początku za każdym razem?
Nolmë Informatique
2

Odpowiedź Davida J. jest dobrą metodą, nie wymaga dodatkowych obiektów, sortowania itp. Można ją jednak ulepszyć:

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

Tak więc zewnętrzna pętla znajduje się u góry na dole dla całej listy, ale wewnętrzna pętla jest na dole „aż do osiągnięcia pozycji zewnętrznej pętli”.

Zewnętrzna pętla zapewnia, że ​​cała lista jest przetwarzana, wewnętrzna pętla znajduje rzeczywiste duplikaty, mogą się one zdarzyć tylko w części, której zewnętrzna pętla jeszcze nie przetworzyła.

Lub jeśli nie chcesz robić oddolnej pętli wewnętrznej, możesz rozpocząć pętlę wewnętrzną od outerIndex + 1.

Gość
źródło
2

Wszystkie odpowiedzi kopiują listy, tworzą nową listę, używają wolnych funkcji lub są po prostu boleśnie powolne.

Według mnie jest to najszybsza i najtańsza metoda, jaką znam (wspierana przez bardzo doświadczonego programistę specjalizującego się w optymalizacji fizyki w czasie rzeczywistym).

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

Ostateczny koszt to:

nlogn + n + nlogn = n + 2nlogn = O (nlogn), co jest całkiem miłe.

Uwaga na temat RemoveRange: Ponieważ nie możemy ustawić liczby na liście i uniknąć korzystania z funkcji Usuń, nie znam dokładnie szybkości tej operacji, ale myślę, że jest to najszybszy sposób.

Darkgaze
źródło
2

Jeśli masz zajęcia holownicze Producti Customerchcemy usunąć zduplikowane elementy z ich listy

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

}

Musisz zdefiniować klasę ogólną w poniższym formularzu

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

następnie możesz usunąć zduplikowane elementy z listy.

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

ten kod usunąć zduplikowane pozycje wg Idjeśli chcesz usunąć duplikaty przez inne właściwości, można zmienić nameof(YourClass.DuplicateProperty) sam nameof(Customer.CustomerName)potem usunąć duplikaty przez CustomerNameProperty.

Reza Jenabi
źródło
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
źródło
1

Prosta intuicyjna implementacja:

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
źródło
Ta metoda jest również powolna. Tworzy nową listę.
darkgaze