jak usunąć puste ciągi z listy, a następnie usunąć zduplikowane wartości z listy


82

Powiedzmy, że mam listę niektórych wartości kolumn pochodzących z tabeli, jak usunąć puste ciągi i zduplikowane wartości. Zobacz poniższy kod:

List<string> dtList = dtReportsList.AsEnumerable().Select(dr => dr.Field<string>("column1")).ToList();

Właśnie to zakodowałem, ale kod Amirama jest o wiele bardziej elegancki, więc wybiorę odpowiedź tutaj, jak to zrobiłem:

DataTable dtReportsList = someclass.GetReportsList();

        if (dtReportsList.Rows.Count > 0)
       { 
           List<string> dtList = dtReportsList.AsEnumerable().Select(dr => dr.Field<string>("column1")).ToList();
           dtList.RemoveAll(x=>x == "");
           dtList = dtList.Distinct().ToList();         

           rcboModule.DataSource = dtList;
           rcboModule.DataBind();               
           rcboModule.Items.Insert(0, new RadComboBoxItem("All", "All"));
       }

Zrozum, że RemoveAll () mutuje dtList; każdy usuwany element wymusza na liście zmianę kolejności elementów w wyższych indeksach w używanej tablicy bazowej. Szybciej byłoby je po prostu pominąć, tak jak robi to Amiram w swojej metodzie Where.
— KeithS

Odpowiedzi:


201
dtList  = dtList.Where(s => !string.IsNullOrWhiteSpace(s)).Distinct().ToList()

Założyłem, że pusty łańcuch i białe znaki są jak null. Jeśli nie, możesz użyć IsNullOrEmpty(zezwalaj na białe znaki) lubs != null


Jeszcze jedna rzecz; deduplikacja za pomocą Distinct () jest stosunkowo nieefektywna, ponieważ metoda musi zakładać najgorszy przypadek.
— KeithS

@KeithS Jakie twierdzenia wiemy o tych danych, a które Distinctnie pozwalają na ich optymalizację?
— Servy

Możemy posortować listę, a następnie stwierdzić, że jest posortowana, dzięki czemu algorytm deduplikacji będzie liniowy; zobacz moją odpowiedź.
— KeithS

9

Odpowiedź Amirama jest poprawna, ale Distinct (), jak zaimplementowano, jest operacją N 2 ; dla każdego elementu na liście algorytm porównuje go ze wszystkimi już przetworzonymi elementami i zwraca go, jeśli jest unikalny, lub ignoruje go, jeśli nie. Możemy zrobić lepiej.

Posortowana lista może być deduped w czasie liniowym; jeśli bieżący element jest równy poprzedniemu, zignoruj ​​go, w przeciwnym razie zwróć. Sortowanie to NlogN, więc nawet posortowanie kolekcji daje pewne korzyści:

public static IEnumerable<T> SortAndDedupe<T>(this IEnumerable<T> input)
{
   var toDedupe = input.OrderBy(x=>x);

   T prev;
   foreach(var element in toDedupe)
   {
      if(element == prev) continue;

      yield return element;
      prev = element;      
   }
}

//Usage
dtList  = dtList.Where(s => !string.IsNullOrWhitespace(s)).SortAndDedupe().ToList();

Zwraca te same elementy; są po prostu sortowane.


Świetny. Jeśli się nie mylę, iterując elementy, faktycznie wykonujesz porządkowanie. Czy możesz wymyślić sposób, aby uczynić swoją metodę „leniwą”?
— Amiram Korach

Niestety, większość sortowań wymaga znajomości całej kolekcji do sortowania; ostatni element może być pierwszym, który należy zwrócić. Dlatego wszystkie elementy danych wejściowych muszą zostać ocenione, aby wygenerować pierwszy element wyniku. Jedynym rodzajem, o którym mogę pomyśleć, który mógłby zostać przerwany po znalezieniu następnego elementu jego wyniku, jest wariant SelectionSort, iw tym przypadku jesteśmy z powrotem na początku.
— KeithS

Poza tym, w naszym przypadku wynikiem całej operacji jest lista, wymagająca na początek „gorliwego” wykonania. Gdybyśmy chcieli pracować z nim jako IEnumerable i odroczyć jego wykonanie, moglibyśmy wziąć mięso funkcji i umieścić je w ukrytej klasie iteratora, która implementuje IEnumerable.
— KeithS

Distinctużywa haszowania i powinno być bliżej O (N) niż O (N ^ 2). źródło
— Risky Martin

… Cóż, niech będzie cholera, rzeczywiście; System.Linq.Set to wewnętrzna implementacja z hashtagiem używana przez Distinct, która byłaby bliska czasu dostępu O (1), zakładając, że implementacja GetHashCode () twoich elementów jest wydajna i tworzy równomiernie rozłożony hash (domyślna implementacja zrobiłaby to) . Jednak hashtable mają problemy z pamięcią; Podstawowa implementacja .NET wykorzystuje dwie tablice, jedną z liczb całkowitych, a drugą z połączonych elementów, z których każda w najlepszym przypadku jest równa liczbie elementów w zestawie, aw najgorszym jest dwukrotnie większa.
— KeithS

1

Rozwiązanie Amirama Koracha jest rzeczywiście uporządkowane. Oto alternatywa dla wszechstronności.

var count = dtList.Count;
// Perform a reverse tracking.
for (var i = count - 1; i > -1; i--)
{
    if (dtList[i]==string.Empty) dtList.RemoveAt(i);
}
// Keep only the unique list items.
dtList = dtList.Distinct().ToList();

4
Chociaż to zadziała, klauzula Where jest szybsza, ponieważ nie musi modyfikować kolekcji wejściowej. Minimalizujesz liczbę „przesunięć”, które należy wykonać podczas usuwania elementów z listy, ale Where nie usuwa niczego z danych wejściowych; po prostu pomija niepasujące elementy.
— KeithS

0

Aby uprościć rozwiązanie Amirama Koracha :

dtList.RemoveAll(s => string.IsNullOrWhiteSpace(s))

Nie ma potrzeby używania Distinct () lub ToList ()

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.