Usuwanie duplikatów z kolekcji .NET, rozważania

Tablice i listy bez powtarzających się elementów

Potrzeba tego wpisu pojawiła się nagle. Zaczynem okazało się pewne stwierdzenie które brzmiało mniej więcej tak: Po co pisać własne funkcje i metody, skoro jest już gotowa metoda rozszerzająca Distinct! Pisali ją ci od .NETa! Przecież nie napiszesz lepiej! Tam nie takie mózgi siedzą!. I prawdziwie, metody LINQ są napisane bardzo dobrze i mają szeroki wachlarz zastosowań. Ta uniwersalność ma jednak swoje konsekwencje. O tym jednak za chwilę. Tradycyjne wywołanie metody będzie wyglądało następująco:

var points = new Point[]{
    new Point(1,1),
    new Point(2,1),
    new Point(2,1)
};

Point[] result = points.Distinct().ToArray();

Point jest najprostszą strukturą zawierającą dwie właściwości: X i Y. Sama metoda Distinct jest prosta, ale pod spodem znajduje się jakiś mniej lub bardziej złożony algorytm. Jaki?

Sposób usuwania duplikatów przez implementację .NET

Gdybyśmy się bliżej przyjrzeli wnętrzom metody rozszerzającej Distinct dostrzeglibyśmy co następuje:

1. Utwórz pustą tablicę mieszającą (z haszowaniem).
2. Pobierz element z kolekcji wejściowej.
3.   Jeżeli nie znajduje się w tablicy mieszającej, dodaj do wyniku.
4. Jeżeli w kolekcji są elementy, skocz do 2.

Przekładając to na język .NET mielibyśmy coś takiego:

IEnumerable<TSource> DistinctIterator<TSource>(IEnumerable<TSource> source, IEqualityComparer<TSource> comparer)
{
    Set<TSource> set = new Set<TSource>(comparer);
    foreach (TSource current in source)
    {
        if (set.Add(current))
        {
            yield return current;
        }
    }
}

Ot i cała magia metody Distinct.

Algorytmicy wiedzą, że na dobór odpowiedniego algorytmu może mieć wpływ rodzaj danych i pewne założenia (zob. między innymi wpis Algorytm merge w praktyce). A gdybyśmy założyli, że elementy kolekcji są posortowane?

Usuwanie duplikatów w posortowanej kolekcji

Zdarza się, że kolekcja, z której zamierzamy usuwać powtarzające się elementy, jest już posortowana. Pozwala to na wykorzystanie nieco innego algorytmu. Skorzystam z pewnej właściwości posortowanej kolekcji - takie same elementy są obok siebie. Popatrzmy na jedną z możliwych implementacji wykorzystującej to założenie:

public static IEnumerable<T> OrderedDistinct<T>(this IEnumerable<T> source)
{
    IEnumerator<T> enumerator = source.GetEnumerator();
    if (enumerator.MoveNext())
    {
        var lastValue = enumerator.Current;
        yield return lastValue;

        while (enumerator.MoveNext())
        {
            T item = enumerator.Current;
            if (!item.Equals(lastValue))
                yield return item;
            lastValue = item;
        }
    }
}

Rozwiązanie, podobnie jak poprzednie, wbudowane, wykorzystuje słowo kluczowe yield. Zamiast wyszukiwać element w tablicy mieszającej, metoda wykonuje proste porównanie z elementem poprzednim. Warto pamiętać, że metoda musi być wywoływana na posortowanej tablicy - w przeciwnym razie duplikaty nie będą poprawnie usuwane.

Własny sposób porównywania elementów - IEqualityComparer.

O ile typy proste (takie jak int czy string) można łatwo uporządkować, o tyle obiekty jakiejś klasy mogą stwarzać problemy. Jak posortować osobę? Po nazwisku? Po numerze PESEL? Po dacie urodzenia? Nie ma jednej odpowiedzi. LINQ w takich sytuacjach przyjmuje obiekt klasy implementującej interfejs IEqualityComparer. I to właśnie ta klasa decyduje o sposobie sortowania obiektów. To dlatego postanowiłem napisać jeszcze jedną wersję metody usuwającej duplikaty:

public static IEnumerable<T> OrderedDistinct<T>(this IEnumerable<T> source, IEqualityComparer<T> comparer)
{
    IEnumerator<T> enumerator = source.GetEnumerator();
    if (enumerator.MoveNext())
    {
        var lastValue = enumerator.Current;
        yield return lastValue;

        while (enumerator.MoveNext())
        {
            T item = enumerator.Current;
            if (!comparer.Equals(item, lastValue))
                yield return item;
            lastValue = item;
        }
    }
}

Metoda jest bardzo podobna do poprzedniej dlatego nie wymaga dodatkowego komentarza.

Wydajność: Które będzie szybsze?

Wiadomo, że dla małych kolekcji każdy algorytm będzie dobry. Ja postanowiłem wykonać test dla 10000 elementów. Nie jest to wartość mała, ale nie jest też specjalnie duża. Popatrzmy na testowy kod oraz otrzymane wyniki:

List<Point> largePoints = new List<Point>();
for (int i = 0; i < 10000; i++)
{
    largePoints.Add(new Point(i, i));
}
Stopwatch timer = new Stopwatch();

timer.Reset();
timer.Start();
var r1 = largePoints.Distinct().ToList();
timer.Stop();
Console.WriteLine(timer.ElapsedTicks);

timer.Reset();
timer.Start();
var r2 = largePoints.OrderedDistinct().ToList();
timer.Stop();
Console.WriteLine(timer.ElapsedTicks);

Przyznam się, że wyniki trochę mnie zaskoczyły. Spodziewałem się różnicy, ale nie aż takiej. Pierwsza metoda potrzebowała 5195814 jednostek czasu, druga natomiast: 5559. To o trzy rzędy wielkości mniej! Nawet zakładając duży błąd pomiaru nie zlikwidujemy przepaści dzielącej te dwa rozwiązania. Popatrzmy na prosty wykres:

Pokazane powyżej wyniki potwierdzają, że znajomość algorytmów, nawet podczas pisania w bardzo rozbudowanym i dopracowanym środowisku jest niezwykle przydatna. Więcej, dolny pasek jest praktycznie niewidoczny przy pasku górnym! Ale zaraz: skąd takie różnice?

Wyjaśnienie: Różnice w czasach wykonania

Jaka jest główna różnica pomiędzy rozwiązaniem wbudowanym a napisanym? Elementów jest tyle samo, przetwarzane są one w jednej pętli - wszystko niby podobne. Kod pierwszego rozwiązania jest nawet krótszy.

Wszystko to przez tablice mieszające. Przypisanie do zmiennej poprzedniego elementu to jedna instrukcja i jeden takt procesora, jeden prosty warunek też nie jest szczególnie kosztownyNie można wskazać liczby instrukcji, wszystko zależy od poprawności przewidywania skoków. Jeżeli w przetwarzaniu potokowym skok został dobrze przewidziany, jest dobrze. Źle przewidziany skok wymaga wycofania instrukcji z potoku i ponowienie ich. Mechanizm ten znany jest pod nazwą tablic BPT (ang. Branch Prediction Table).. Sprawdzenie istnienia tego elementu w tablicy mieszającej wymaga znacznie większej liczby operacji: wyliczenia funkcji haszującej, przedzielenia obiektu do kubełka, gdy liczba elementów w tablicy mieszającej przekroczy pewien próg należy taką tablicę rozszerzyć i ponownie przeliczyć wartości funkcji haszujących dla wszystkich elementów, które juz tam są. Aby przekonać się o złożoności tego algorytmu, swoją drogą bardzo przydatnego, można spróbować samemu zaimplementować takie rozwiązanie. Więcej o tablicach mieszających można poczytać w Introduction To Algorithms, MIT Press, 2001.

Podsumowanie

Wpis miał pokazać, że nawet najlepsze środowiska, same za nas pracy nie wykonają. Zdecydowana większość operacji na kliencie po stronie .NET to obróbka niewielkich kolekcji. W takim przypadku zwykła metoda Distinct jest wystarczająco szybka. Gdy kolekcje się zwiększają, zwiększa się również czas potrzebny na wykonanie prostych operacji. Doświadczają tego administratorzy baz danych, którzy codziennie pracują z gigabajtami danych, dla których kilkadziesiąt rekordów to nie tak znowu dużo. Specyfika SQL sprawia, że takie problemy rozwiązuje się nieco inaczej niż w .NET. W .NET, języku proceduralnym, na pierwszy front wysuwają się algorytmy. Specjalnie przygotowałem taki przykład, aby pokazać potencjał. Nie zawsze potrzeba aż takich optymalizacji i nie zawsze aż takie są możliwe. Wszystko zależy od sytuacji i pomysłowości.

Kategoria:AlgorytmyC#