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.