Transformacja Schwartza

Transformacja Schwartza (ang. Schwartzian Transform) – idiom programistyczny wykorzystywany w informatyce do zwiększenia wydajności procesu sortowania listy elementów. Idiom ten jest odpowiedni do sortowania opartego na porównywaniu elementów listy, gdy porządkowanie listy odbywa się w oparciu o pewną właściwość (klucz) sortowanych elementów, a obliczanie tej właściwości jest mocno obciążające dla komputera, stąd operacja obliczania wartości klucza powinna być wykonywana minimalną liczbę razy. Wyróżniającą cechą Transformacji Schwartza jest to, że nie używa ona nazwanych tablic tymczasowych.

Idiom ten został nazwany od jego twórcy i popularyzatora – Randala L. Schwartza, który jako pierwszy, w grudniu 1994 r., niedługo po ukazaniu się języka programowania Perl w wersji 5. na grupie dyskusyjnej Usenet zademonstrował jego użycie. Nazwa „Transformacja Schwartza” od momentu jej powstania przez wiele lat stosowana była wyłącznie w odniesieniu do języka programowania Perl, później jednak została przyjęta również w innych językach, takich jak np. Python w odniesieniu do podobnych idiomów programistycznych stosowanych przez ich użytkowników. Termin „Transformacja Schwartza” wskazuje konkretny idiom, a nie algorytm w ogólności.

Transformacja Schwartza jest wersją idiomu z języka programowania Lisp znanego jako decorate-sort-undecorate, który unika ponownego obliczania kluczy sortujących przez tymczasowe kojarzenie ich z elementami wejściowymi. Podstawową ideą transformacji Schwartza jest: weź listę do posortowania i utwórz drugą, tymczasową listę zawierającą zarówno wartość oryginalną, jak i wartość transformowaną – element używany do właściwego sortowania. Po posortowaniu, element tymczasowy zostaje usunięty, pozostawiając posortowaną listę z elementami z oryginalnej, wyjściowej listy.

Przykład 1.

Zakładając, że lista słów następującej postaci ("aaaa", "a", "aa") powinna zostać posortowana według długości słowa, w pierwszym kroku należy zbudować nową, tymczasową listę (["aaaa",4], ["a",1], ["aa",2]), następnie tak utworzoną listę należy posortować zgodnie z wartością numeryczną (klucz) odpowiadającą długości słowa, tak że powstała po sortowaniu lista przyjmie postać (["a",1], ["aa",2], ["aaaa",4]). Po usunięciu liczb otrzymuje się ostatecznie posortowaną listę zgodnie z długością słów w niej występujących ("a", "aa", "aaaa"). Aby ten ogólny algorytm przedstawić w Perlu jako transformację Schwartza należy napisać poniższy kod:

@sorted = map  { $_->[0] }             # wyodrębnienie oryginalnych elementów listy
          sort { $a->[1] <=> $b->[1] } # porównanie numeryczne po kluczu
          map  { [$_, length($_)] }    # obliczenie długości łańcucha (wyrazu)
          @unsorted;

Przykład 2.

Należy posortować pliki w danym katalogu według rozmiaru od wartości największej do najmniejszej. Jedną z metod w języku programowania Perl jest poniższy kod.

opendir(my $dh, '.') || die;
@names = readdir $dh;

@sorted_files = sort { -s $b <=> -s $a } @names;

Ten najprostszy sposób posiada jednocześnie największą wadę tego rozwiązania – sprawdzanie rozmiaru każdego pliku wykonywane jest wiele razy, co przy dużej ilości plików może mieć niekorzystny wpływ na wydajność systemu dyskowego i operacji wejścia-wyjścia. Średnia złożoność obliczeniowa funkcji sort w tej metodzie sortowania jest rzędu O(n log n), w najgorszym przypadku O(n²). Zatem sposób ten jest efektywny dla elementów o niewielkiej liczebności. Pewnym rozwiązaniem tego problemu jest wykonanie obliczenia rozmiarów plików przed wykonaniem sortowania. W takim przypadku należy użyć dodatkowej tablicy do przechowania obliczonych wyników.

@temp = map { [$_, -s $_] } @names;
@sorted_files = sort {  $b->[1] <=> $a->[1] } @temp;

Zastosowanie permanentnej tablicy @temp powoduje zajęcie pewnego obszaru w pamięci operacyjnej w trakcie działania całego programu. Dodatkowo, jeżeli użytkownik zamiast sortowania po rozmiarze pliku potrzebować będzie listy plików posortowanych według daty ostatniej modyfikacji, potrzebne będzie utworzenie nowej struktury tablicowej.

Aby rozwiązać powyższe problemy należy zastosować transformację Schwartza, wykorzystując poniższy kod.

@sorted_names = 
    map  { $_->[0] }                # wyodrębnienie oryginalnej listy
    sort { $b->[1] <=> $a->[1] }    # sortowanie (w odwrotnej kolejności)
    map  { [ $_, -s $_ ] }          # obliczanie rozmiaru pliku
    @names;

Idiom w Perlu

Klasyczna Transformacja Schwartza w uproszczeniu posiada następującą postać:

map {} sort {} map {}

Postać kanoniczna TS występuje w poniższej postaci:

@sorted = map  { $_->[0] }
          sort { $a->[1] cmp $b->[1] }
          map  { [$_, foo($_)] }
          @unsorted;

Gdzie foo($_) reprezentuje wyrażenie, które przyjmuje zmienną $_ (po kolei każdy element listy) i tworzy odpowiadającą tej zmiennej wartość, która jest porównywana w jej zastępstwie.

Użycie anonimowej, tymczasowej tablicy gwarantuje, że niezwłocznie po wykonaniu sortowania pamięć zostanie zwolniona przez algorytm garbage collector w Perlu.

Linki zewnętrzne

• "Sorting with the Schwartzian Transform" – artykuł opublikowany przez autora (ang.)