Transformacja Schwartza

W programowaniu komputerowym transformata Schwartza jest techniką stosowaną w celu poprawy wydajności sortowania listy elementów. Ten idiom jest odpowiedni dla sortowania opartego na porównaniach , gdy porządkowanie jest w rzeczywistości oparte na uporządkowaniu określonej właściwości (klucza ) elementów, gdzie obliczenie tej właściwości jest intensywną operacją, którą należy wykonać minimalną liczbę razy. Transformata Schwartza wyróżnia się tym, że nie używa nazwanych tablic tymczasowych.

Transformata Schwartza jest wersją idiomu Lispa znanego jako dekoruj-sortuj-niedekoruj , która pozwala uniknąć ponownego obliczania kluczy sortowania poprzez tymczasowe powiązanie ich z elementami wejściowymi. Podejście to jest podobne do zapamiętywania , które pozwala uniknąć powtarzania obliczeń klucza odpowiadającego określonej wartości wejściowej. Dla porównania, ten idiom zapewnia, że ​​klucz każdego elementu wejściowego jest obliczany dokładnie raz, co może nadal skutkować powtórzeniem niektórych obliczeń, jeśli dane wejściowe zawierają zduplikowane elementy.

Idiom został nazwany na cześć Randala L. Schwartza , który po raz pierwszy zademonstrował go w Perlu wkrótce po wydaniu Perla 5 w 1994 roku. Termin „transformacja Schwartza” odnosił się wyłącznie do programowania w Perlu przez wiele lat, ale później został przyjęty przez niektórzy użytkownicy innych języków , takich jak Python , aby odnieść się do podobnych idiomów w tych językach. Jednak algorytm ten był już używany w innych językach (bez konkretnej nazwy), zanim został spopularyzowany wśród społeczności Perla w postaci tego konkretnego idiomu autorstwa Schwartza. Termin „transformacja Schwartza” wskazuje na konkretny idiom, a nie ogólnie na algorytm.

Na przykład, aby posortować listę słów ("aaaa", "a", "aa") według długości słowa: najpierw zbuduj listę (["aaaa",4],["a",1],["aa ",2]), następnie posortuj według otrzymanych wartości liczbowych (["a",1],["aa",2],["aaaa",4]), następnie usuń liczby i otrzymasz ( „a”, „aa”, „aaaa”). Taki był ogólnie algorytm, więc nie liczy się jako transformacja. Aby uczynić to prawdziwą transformacją Schwartza, w Perlu należałoby to zrobić w następujący sposób:

     0 
                0  0  
                @sorted  =  map  {  $_  ->  [  ]  }  sort  {  $a  ->  [  1  ]  <=>  $b  ->  [  1  ]  lub  $a  ->  [  ]  cmp  $b  ->  [  ]  }  # Użyj porównania numerycznego , cofnij się do sortowania łańcuchowego na oryginalnej  mapie  {  [  $_  ,  length  (  $_  )]  }     
                # Oblicz długość napisu  @unsorted  ;

Idiom Perla

Ogólna postać transformaty Schwartza to:

     0 
                0  0 
               
                @sortowane  =  mapa  {  $_  ->  [  ]  }  sort  {  $a  ->  [  1  ]  cmp  $b  ->  [  1  ]  lub  $a  ->  [  ]  cmp  $b  ->  [  ]  }  mapa  {  [  $_  ,  foo  (  $_  )]  }  @nieposortowane  ;

Tutaj foo($_) reprezentuje wyrażenie, które bierze $_ (każdy element listy po kolei) i generuje odpowiednią wartość, która ma być porównana w jej miejsce.

Czytanie od prawej do lewej (lub od dołu do góry):

  • oryginalna lista @unsorted jest wprowadzana do operacji mapowania , która opakowuje każdy element w tablicę (odniesienie do anonimowej 2-elementowej) składającą się z siebie i obliczonej wartości, która określi porządek sortowania (lista pozycji staje się listą [pozycja , wartość]);
  • następnie lista list utworzonych przez map jest wprowadzana do sort , która sortuje ją według wcześniej obliczonych wartości (list of [item, value] ⇒ sorted list of [item, value]);
  • w końcu inna operacja na mapie rozpakowuje wartości (z anonimowej tablicy) użyte do sortowania, tworząc elementy oryginalnej listy w posortowanej kolejności (posortowana lista [pozycja, wartość] ⇒ posortowana lista pozycji).

Użycie anonimowych tablic gwarantuje, że pamięć zostanie odzyskana przez moduł wyrzucania elementów bezużytecznych Perla natychmiast po zakończeniu sortowania.

Analiza wydajności

Bez transformaty Schwartza sortowanie w powyższym przykładzie byłoby napisane w Perlu w następujący sposób:

         @sortowane  =  sort  {  foo  (  $ a  )  cmp  foo  (  $ b  )  }  @ nieposortowane  ;

obliczenie funkcji klucza (zwanej foo w powyższym przykładzie) jest drogie. Dzieje się tak, ponieważ kod w nawiasach jest oceniany za każdym razem, gdy trzeba porównać dwa elementy. Optymalne sortowanie porównawcze wykonuje O ( n log n ) porównań (gdzie n jest długością listy), z 2 wywołaniami foo przy każdym porównaniu, co skutkuje wywołaniami O ( n log n ) foo . Dla porównania, używając transformaty Schwartza, wykonujemy tylko 1 wywołanie foo na element na początkowym etapie mapy , co daje w sumie n wywołań foo .

Jeśli jednak funkcja foo jest stosunkowo prosta, to dodatkowy narzut związany z transformacją Schwartza może być nieuzasadniony.

Przykład

Na przykład, aby posortować listę plików według czasu ich modyfikacji , naiwne podejście może wyglądać następująco: 

 
  function  naiveCompare(plik a, plik b) {  return  Czas modyfikacji(a) < Czas modyfikacji(b) }  // Załóżmy, że sort(list, porównaniaPredicate) sortuje podaną listę przy użyciu  // porównania dwóch elementów.  sortedArray := sort(filesArray, naiveCompare)

O ile czasy modyfikacji nie są zapamiętywane dla każdego pliku, ta metoda wymaga ich ponownego obliczania za każdym razem, gdy plik jest porównywany podczas sortowania. Korzystając z transformaty Schwartza, czas modyfikacji jest obliczany tylko raz dla każdego pliku.

Transformacja Schwartza obejmuje opisany powyżej idiom funkcjonalny, który nie używa tablic tymczasowych.

Ten sam algorytm można napisać proceduralnie, aby lepiej zilustrować jego działanie, ale wymaga to użycia tablic tymczasowych i nie jest to transformata Schwartza. Poniższy przykładowy pseudokod implementuje algorytm w następujący sposób:

  dla każdego  pliku  w  filesArray wstaw tablicę(plik, czas modyfikacji(plik)) na końcu  funkcji transformowanej tablicy   simpleCompare(array a, array b) {  return  a[2] < b[2] } transformedArray := sort(transformedArray, simpleCompare)  for każdy  plik  w  transformowanej tablicy wstaw plik [1] na końcu sortedArray

Historia

Pierwszym znanym pojawieniem się online transformacji Schwartza jest post Randala Schwartza z 16 grudnia 1994 r . w wątku w grupie dyskusyjnej Comp.unix.shell Usenet , przesłany do comp.lang.perl. (Obecna wersja osi czasu Perla jest niepoprawna i odnosi się do późniejszej daty w 1995 r.) Wątek rozpoczął się od pytania o to, jak posortować listę wierszy według ich „ostatniego” słowa: 

adjn: Joshua Ng adktk: KaLap Timothy Kwong admg: Mahalingam Gobieramanan admn: Martha L. Nangalama

Schwartz odpowiedział:


  

      0 
         
        
     #!/usr/bin/perl  wymaga  5  ;  # Nowe funkcje, nowe błędy!  drukuj  mapę  {  $_  ->  [  ]  }  sortuj  {  $a  ->  [  1  ]  cmp  $b  ->  [  1  ]  }  map  {  [  $_  ,  /(\S+)$/  ]  }  <>  ;

Ten kod generuje wynik:

admg: Mahalingam Gobieramanan adktk: KaLap Timothy Kwong admln: Martha L. Nangalama adjn: Joshua Ng

Schwartz zauważył w poście, że „Speak [ing] with a seplenienie w Perlu”, co jest odniesieniem do pochodzenia idiomu Lisp .

Sam termin „transformacja Schwartza” został wymyślony przez Toma Christiansena w dodatkowej odpowiedzi. Późniejsze posty Christiansena jasno dały do ​​zrozumienia, że ​​nie zamierzał nazwać konstruktu , a jedynie odnieść się do niego z oryginalnego postu: jego próba ostatecznego nazwania go „Czarna transformacja” nie przyniosła skutku („Czarny” jest tutaj gra słów na „schwar [t] z”, co po niemiecku oznacza czarny).

Porównanie z innymi językami

Niektóre inne języki zapewniają wygodny interfejs do tej samej optymalizacji, co transformata Schwartza:

  • W Pythonie 2.4 i nowszych zarówno funkcja sorted() , jak i metoda list.sort() na miejscu przyjmują parametr key= , który pozwala użytkownikowi podać „funkcję klucza” (jak foo w powyższych przykładach). W Pythonie 3 i nowszych użycie funkcji key jest jedynym sposobem na określenie niestandardowej kolejności sortowania (wcześniej obsługiwana funkcja cmp= usunięto parametr, który umożliwiał użytkownikowi udostępnienie „funkcji porównania”). Przed Pythonem 2.4 programiści używali pochodzącego z lispa idiomu dekoruj-sortuj-niedekoruj (DSU), zwykle poprzez zawijanie obiektów w krotkę (klucz sortowania, obiekt).
  • W Ruby 1.8.6 i nowszych klasa abstrakcyjna Enumerable (która zawiera Array s) zawiera metodę sort_by , która pozwala określić „funkcję klucza” (jak foo w powyższych przykładach) jako blok kodu.
  • W D 2 i wyższych dostępna jest funkcja sortowania według Schwartza . Może wymagać mniej danych tymczasowych i być szybszy niż idiom Perla lub idiom dekoruj-sortuj-niedekoruj obecny w Pythonie i Lispie. Dzieje się tak, ponieważ sortowanie odbywa się w miejscu i tworzona jest tylko minimalna ilość dodatkowych danych (jedna tablica przekształconych elementów).
  • Podstawowa funkcja sortowania Racket akceptuje argument #:key key z funkcją, która wyodrębnia klucz, oraz dodatkowe #:cache-keys? żąda, aby wynikowe wartości były buforowane podczas sortowania. Na przykład wygodnym sposobem przetasowania listy jest ( sort l < #:key ( λ ( _ ) ( random )) #:cache-keys? #t ) .
  • W PHP 5.3 i nowszych transformację można zaimplementować za pomocą array_walk , np. w celu obejścia ograniczeń niestabilnych algorytmów sortowania w PHP. 
       

            
    
       sortowanie_liczb_przestrzeni  (  tablica  &  $a  )  :  nieważna  {  spacer_po  tablicy  (  $a  ,  funkcja  (  &  $v  ,  $k  )  {  $v  =  tablica  (  $v  ,  $k  );  });  sortuj  (  $a  );  array_walk  (  $a  ,  funkcja  (  &  $v  ,  $_  )     0 
 {  $v  =  $v  [  ];  });  }
  • W Elixir metody Enum.sort_by /2 i Enum.sort_by/3 pozwalają użytkownikom na wykonanie transformacji Schwartza dla dowolnego modułu, który implementuje protokół Enumerable .
  • W Raku należy podać lambda porównawczą, która wymaga tylko 1 argumentu, aby wykonać transformację Schwartza pod maską: 
     @a  .  sort  ( {  $^a  .  Str  } )  # lub krócej: @a.sort(*.Str)
    sortowałby według reprezentacji łańcuchowej za pomocą transformacji Schwartza,
       @a  .  sortuj  ( {  $^a  .  Str  cmp  $^b  .  Str  } )
    zrobiłby to samo, konwertując elementy do porównania tuż przed każdym porównaniem.
  • W Rust , nieco myląco, metoda slice::sort_by_key *nie* wykonuje transformacji Schwartza, ponieważ nie przydziela dodatkowej pamięci dla klucza, wywołuje funkcję klucza dla każdej wartości dla każdego porównania. Metoda slice::sort_by_cached_key obliczy klucze raz dla każdego elementu.
  1. Bibliografia   _ Ascher, David, wyd. (2002). „2.3 Sortowanie z gwarancją stabilności sortowania” . Książka kucharska Pythona . O'Reilly & Associates. P. 43 . ISBN 0-596-00167-3 . Ten idiom jest również znany jako „transformata Schwartza”, przez analogię do pokrewnego idiomu Perla.
  2. ^ „Jak / sortowanie / dekorowanie Sortuj undecorate” .
  3. ^ „Klasy Ruby-doc Core-API” . Źródło 14 września 2011 r .

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Schwartzian_transform&oldid=1104240745 ”