sortowanie próbek

Samplesort to algorytm sortowania , który jest algorytmem dziel i zwyciężaj, często używanym w systemach przetwarzania równoległego. Konwencjonalne algorytmy sortowania typu „dziel i zwyciężaj” dzielą tablicę na podprzedziały lub segmenty. Wiadra są następnie sortowane pojedynczo, a następnie łączone razem. Jeśli jednak tablica jest rozłożona nierównomiernie, wydajność tych algorytmów sortowania może zostać znacznie ograniczona. Samplesort rozwiązuje ten problem, wybierając próbkę o rozmiarze $s$ z $n$ -sekwencja elementów i określenie zakresu przedziałów poprzez sortowanie próby i wybranie z wyniku $p -1 < s elementów.$ Te elementy (zwane rozdzielaczami) następnie dzielą tablicę na $p$ segmentów o mniej więcej równej wielkości. Sortowanie próbek jest opisane w artykule z 1970 r. „Samplesort: A Sampling Approach to Minimal Storage Tree Sorting”, autorstwa WD Frazer i AC McKellar.

Algorytm

Samplesort jest uogólnieniem sortowania szybkiego . Tam, gdzie quicksort dzieli swoje dane wejściowe na dwie części na każdym kroku, w oparciu o pojedynczą wartość zwaną przestawną, samplesort zamiast tego pobiera większą próbkę z danych wejściowych i odpowiednio dzieli dane na segmenty. Podobnie jak w przypadku sortowania szybkiego, rekurencyjnie sortuje zasobniki.

Aby opracować implementację sortowania próbek, należy określić liczbę segmentów $p$ . Kiedy to nastąpi, rzeczywisty algorytm działa w trzech fazach:

Próbka $p -1$ elementów z wejścia ( rozgałęźniki ). Sortuj te; każda para sąsiadujących rozdzielaczy definiuje następnie wiadro .
Zapętl dane, umieszczając każdy element w odpowiednim zasobniku. (Może to oznaczać: wyślij go do procesora w wieloprocesorowym ).
Posortuj każde z wiader.

Pełne posortowane dane wyjściowe to konkatenacja segmentów.

Powszechną strategią jest ustawienie $p$ równe liczbie dostępnych procesorów. Dane są następnie rozdzielane między procesory, które wykonują sortowanie zasobników przy użyciu innego, sekwencyjnego algorytmu sortowania.

Pseudo kod

Poniższe zestawienie przedstawia wyżej wspomniany trzyetapowy algorytm jako pseudokod i pokazuje, jak algorytm działa w zasadzie. Poniżej $A$ to nieposortowane dane, $k$ to współczynnik nadpróbkowania, omówiony później, a $p$ to liczba rozdzielaczy.

 ₀ function  sampleSort(A[1..n],  $k$  ,  $p$  ) // jeśli średni rozmiar zasobnika jest poniżej progu przełącz na np. sortowanie szybkie  if  n  /  k  < próg  then  smallSort(A) /* Krok 1 */ wybierz  S  = [  S ₁ , ...,  S _{(  p  −1)  k} ] losowo z // wybierz próbki posortuj  $S$  // posortuj próbkę [  s  ,  s ₁ , ..., s _{p  −1} ,   s _p ] <- [-∞,  S _k ,  S _{2  k} , ...,  S _{(  p  −1)  k} , ∞] // wybierz rozdzielacze /* Krok 2 */  dla każdego  a  w  A  znajdź  $j$  takie, że  s _{j  −1} <  a  <=  s _j umieść  $a$  w pojemniku  b _j /* Krok 3 i konkatenacja */  powrót  concatenate(sampleSort(  b ₁ ), ..., sampleSort(  b _k ))

Pseudokod różni się od oryginalnego algorytmu Frazera i McKellara. W pseudokodzie samplesort jest wywoływane rekurencyjnie. Frazer i McKellar wywołali samplesort tylko raz i użyli sortowania szybkiego we wszystkich kolejnych iteracjach.

Złożoność

Złożoność, podana w notacji Big O , dla równoległej implementacji z procesorami: ${\ displaystyle p}$

Znajdź rozdzielacze.

{\ Displaystyle O \ lewo ({\ Frac {n} {p}} + \ log (p) \ prawo)}

Wyślij do wiader.

{\ Displaystyle O (p)}

do odczytu wszystkich węzłów

{\ Displaystyle O (\ log (p))}

do nadawania

{\ displaystyle O \ lewo ({\ frac {n} {p}} \ log (p) \ prawo)}

dla wyszukiwania binarnego dla wszystkich kluczy

{\ Displaystyle O \ lewo ({\ frac {n} {p }}\right)}

, aby wysłać klucze do zasobnika

Sortuj wiadra.

{\ Displaystyle O \ lewo (c \ lewo ({\ Frac {n} {p}} \ prawej) \ prawej)}

gdzie jest

{\ Displaystyle c (n)}

złożoność podstawowej metody sortowania sekwencyjnego. Często

{\ Displaystyle c (n) = n \ log (n)}

.

Liczba porównań przeprowadzonych przez ten algorytm zbliża się do $informacyjnego$ sekwencji W eksperymentach przeprowadzonych przez Frazera i McKellara algorytm wymagał o 15% mniej porównań niż sortowanie szybkie.

Próbkowanie danych

Dane mogą być próbkowane różnymi metodami. Niektóre metody obejmują:

Wybierz równomiernie rozmieszczone próbki.
Wybierz losowo wybrane próbki.

Nadpróbkowanie

Współczynnik nadpróbkowania określa, ile razy więcej elementów danych należy pobrać jako próbki przed określeniem rozdzielaczy. Celem jest uzyskanie dobrej reprezentacji rozkładu danych. Jeśli wartości danych są szeroko rozłożone, ponieważ nie ma wielu zduplikowanych wartości, wystarczy mały współczynnik próbkowania. W innych przypadkach, gdy w rozkładzie występuje wiele duplikatów, konieczny będzie większy współczynnik nadpróbkowania. W idealnym przypadku, po kroku 2, każde wiadro zawiera ${\ displaystyle n/p}$ elementy. W tym przypadku sortowanie żadnego zasobnika nie zajmuje więcej czasu niż pozostałych, ponieważ wszystkie zasobniki są tej samej wielkości.

Po pobraniu $razy$ liczby próbek niż to konieczne, próbki są sortowane. Następnie rozdzielaczami używanymi jako granice kubełków są próbki w pozycji ${\ Displaystyle k, 2k, 3 k, \ kropki, (p-1) k}$ sekwencja próbek (wraz z $- \ infty$ $}$ Displaystyle jako lewe i prawe granice odpowiednio dla segmentów najbardziej wysuniętych na lewo i najbardziej na prawo). Zapewnia to lepszą heurystykę dla dobrych rozdzielaczy niż $rozdzielaczy$ .

Oszacowanie wielkości wiadra

Na podstawie otrzymanej wielkości próby można oszacować oczekiwaną wielkość koszyka, a zwłaszcza prawdopodobieństwo, że koszyk przekroczy określoną wielkość. Poniżej pokażemy, że dla współczynnika nadpróbkowania ${\ Displaystyle S \ in \ Theta \ lewo ({\ dfrac {\ log n} {\ epsilon ^ {2}}} \ prawo )}$ prawdopodobieństwo, że żadne wiadro nie ma więcej niż elementów jest większe niż ${\ Displaystyle (1+ \ epsilon) \ cdot {\ dfrac {n} {p}}}$ ${\ Displaystyle 1- {\ dfrac {1} {n}}}$ .

Aby $_$ wejściem Aby procesor mógł uzyskać więcej elementów niż ${\ Displaystyle (1 + \ epsilon) \ cdot n/p}$ , musi istnieć podsekwencja wprowadzania długości ${\ displaystyle (1+ \ epsilon) \ cdot n/p} , z których$ pobiera się maksymalnie $S próbek.$ $te$ prawdopodobieństwo . Można to przedstawić jako zmienną losową:

{\ Displaystyle X_ {i}: = {\ rozpocząć {przypadki} 1 i {\ tekst {jeśli}} s_ {i} \ w \ lewo \ langle e_ {j}, \ kropki, e_ {j} + (1 +\epsilon )\cdot {\dfrac {n}{p}}\right\rangle \\0,&{\text{inaczej}}\end{przypadki}},X:=\sum _{i=0} ^{S\cdot p-1}X_{i}}

Dla oczekiwanej wartości ${\ displaystyle X_ {i}}$ posiada: X ja { \ displaystyle X_ {i}}

{\ Displaystyle E (X_ {i}) = P (X_ {i} = 1) = {\ dfrac {1 + \ epsilon} {p }}}

Zostanie to wykorzystane do oszacowania ${\ displaystyle P _ {\ tekst {niepowodzenie}}}$ :

{\ Displaystyle P (X <S) \ około P (X <( 1-\epsilon ^{2})S)=P(X<(1-\epsilon )E(X))}

Korzystając teraz z ograniczenia Chernoffa , można pokazać:

{\ Displaystyle P _ {\ tekst {niepowodzenie}} =n\cdot P(X<S)\równoważnik n\cdot \exp \left({\dfrac {-\epsilon ^{2}\cdot S}{2}}\right)\równoważnik n\cdot {\dfrac {1}{n^{2}}}{\text{dla}}S\geq {\dfrac {4}{\epsilon ^{2}}}\ln n}

Wiele identycznych kluczy

W przypadku wielu identycznych kluczy algorytm przechodzi przez wiele poziomów rekurencji, na których sekwencje są sortowane, ponieważ cała sekwencja składa się z identycznych kluczy. Można temu przeciwdziałać, wprowadzając koszyki równości. Elementy równe osi obrotu są sortowane do odpowiedniego zasobnika równości, który można zaimplementować tylko z jedną dodatkową gałęzią warunkową. Zasobniki równości nie są dalej sortowane. $występujące$ więcej niż prawdopodobnie staną się

Zastosowania w systemach równoległych

Przykład równoległego sortowania próbek na

3}

\

{ =

Sortowanie próbek jest często używane w systemach równoległych, w tym w systemach rozproszonych, takich jak masowe synchroniczne maszyny równoległe . Ze względu na zmienną liczbę rozdzielaczy (w przeciwieństwie do tylko jednej osi w Quicksort ), Samplesort jest bardzo dobrze przystosowany i intuicyjny do równoległości i skalowania. Ponadto Samplesort jest również bardziej wydajny pod względem pamięci podręcznej niż implementacje np. sortowania szybkiego.

Równoległość jest realizowana przez podzielenie sortowania dla każdego procesora lub węzła, gdzie liczba zasobników jest równa $procesorów$ . Sortowanie próbek jest wydajne w systemach równoległych, ponieważ każdy procesor otrzymuje w przybliżeniu ten sam rozmiar zasobnika ${\ displaystyle n/p}$ . Ponieważ zasobniki są sortowane jednocześnie, procesory zakończą sortowanie mniej więcej w tym samym czasie, dzięki czemu procesor nie będzie czekał na inne.

W systemach rozproszonych rozdzielacze są wybierane przez pobranie elementów na każdym procesorze, sortowanie wynikowych $displaystyle$ za pomocą algorytmu sortowania rozproszonego, pobranie każdego elementu i k $p$ $k}$ rozgłaszanie wyniku do wszystkich procesorów. To kosztuje ${\ Displaystyle T _ {\ tekst {sort}} (kp, p)}$ do sortowania ${\ displaystyle kp}$ elementy ${\ displaystyle p}$ $wybranych$ $p$ $\$ także p _ procesory.

Dzięki wynikowym rozdzielaczom każdy procesor umieszcza własne dane wejściowe w lokalnych zasobnikach. To zajmuje ${\ Displaystyle {\ mathcal {O}} (n / p \ log p)}$ z wyszukiwaniem binarnym . Następnie lokalne zasobniki są redystrybuowane do procesorów. Procesor pobiera lokalne zasobniki $.$ procesorów i sortuje $je$ Dystrybucja przyjmuje ${\ Displaystyle T _ {\ tekst {od wszystkich do wszystkich}} (N, p)}$ czas, gdzie ${\ Displaystyle N}$ to rozmiar największego wiadra. Sortowanie lokalne trwa ${\ Displaystyle T _ {\ text {localsort}} (N)}$ .

Eksperymenty przeprowadzone na początku lat 90. na superkomputerach Connection Machine wykazały, że samplesort jest szczególnie dobry w sortowaniu dużych zestawów danych na tych maszynach, ponieważ wiąże się z niewielkim obciążeniem komunikacyjnym między procesorami. W najnowszych procesorach graficznych algorytm może być mniej skuteczny niż jego alternatywy. ^{[ potrzebne źródło ]}

Wydajna implementacja Samplesort

Animowany przykład Super Skalarnego Sortowania Próbek. W każdym kroku porównywane liczby są oznaczane na niebiesko, a liczby, które w inny sposób są odczytywane lub zapisywane, są oznaczane na czerwono.

Jak opisano powyżej, algorytm sortowania próbek rozdziela elementy zgodnie z wybranymi rozdzielaczami. Efektywną strategię implementacji zaproponowano w artykule „Super Skalarne Sortowanie Próbek”. Implementacja zaproponowana w artykule wykorzystuje dwie tablice o rozmiarze $oryginalna$ tablica zawierająca dane wejściowe i tablica tymczasowa) do wydajnej implementacji. W związku z tym ta wersja implementacji nie jest algorytmem w miejscu.

W każdym kroku rekurencji dane są kopiowane do innej tablicy w sposób podzielony na partycje. Jeśli dane znajdują się w tablicy tymczasowej w ostatnim kroku rekurencji, dane są kopiowane z powrotem do oryginalnej tablicy.

Określanie kubełków

W algorytmie sortowania opartym na porównaniach operacja porównania jest częścią o największym znaczeniu dla wydajności. W Samplesort odpowiada to określeniu segmentu dla każdego elementu. To wymaga $.$ elementu

Superskalarne sortowanie próbek wykorzystuje zrównoważone drzewo wyszukiwania, które jest niejawnie przechowywane w tablicy $t$ . Korzeń jest przechowywany w 0, lewy następnik jest przechowywany w ${\ Displaystyle$ $t_ {2i}},$ a prawy następnik jest przechowywany w $displaystyle t_{2i+1}}$ . Biorąc pod uwagę drzewo wyszukiwania $t$ , algorytm oblicza liczbę wiadra $j$ elementu ${\ displaystyle a_ {i}}$ w następujący sposób (zakładając, że ${\ displaystyle a_ {i}> t_ {j}}$ ma wartość 1, jeśli jest to prawda , a 0 w przeciwnym razie):

 j  := 1 powtórz logarytm ₂ (  p  ) razy  j  := 2  jot  + (  a  >  t _jot )  j  :=  j  -  p  + 1

Ponieważ liczba zasobników $k$ jest znana w czasie kompilacji, kompilator może rozwinąć tę pętlę. Operacja porównania jest realizowana za pomocą predykowanych instrukcji . Dzięki temu nie występują błędne przewidywania gałęzi , które znacząco spowalniałyby operację porównywania.

Partycjonowanie

W celu wydajnego podziału elementów algorytm musi z góry znać rozmiary zasobników. Aby podzielić elementy sekwencji i umieścić je w tablicy, musimy wcześniej znać rozmiar wiader. Naiwny algorytm mógłby policzyć liczbę elementów każdego segmentu. Następnie elementy można było wstawić do drugiej tablicy we właściwym miejscu. Korzystając z tego, należy dwukrotnie określić kubełek dla każdego elementu (jeden raz, aby policzyć elementy w kubełku, a drugi raz, aby je wstawić).

Aby uniknąć tego podwojenia porównań, superskalarne sortowanie próbek wykorzystuje dodatkową tablicę $wyrocznią$ ), która przypisuje każdy indeks elementów do wiadra. Najpierw algorytm określa zawartość, $o$ a następnie umieszcza elementy w wiadrze określonym przez $\ displaystyle o}$ . Tablica wiąże się również z kosztami miejsca do przechowywania, ale ponieważ musi tylko przechowywać $o {\ displaystyle o$ ${\ displaystyle n \ cdot \ log k}$ bitów, koszt ten jest niewielki w porównaniu z przestrzenią tablicy wejściowej.

Sortowanie próbek na miejscu

Kluczową wadą wydajnej implementacji Samplesort pokazanej powyżej jest to, że nie jest ona na miejscu i wymaga drugiej tymczasowej tablicy o takim samym rozmiarze jak sekwencja wejściowa podczas sortowania. Wydajne implementacje np. szybkiego sortowania są na miejscu, dzięki czemu zajmują mniej miejsca. Jednak Samplesort można również zaimplementować w miejscu.

Algorytm w miejscu jest podzielony na cztery fazy:

Próbkowanie , które jest równoważne próbkowaniu w wyżej wymienionej wydajnej implementacji.
Klasyfikacja lokalna na każdym procesorze, która grupuje dane wejściowe w bloki w taki sposób, że wszystkie elementy w każdym bloku należą do tego samego zasobnika, ale zasobniki niekoniecznie są ciągłe w pamięci.
Permutacja bloków ustawia bloki w globalnie poprawnej kolejności.
Czyszczenie przesuwa niektóre elementy na krawędziach wiader.

Oczywistą wadą tego algorytmu jest to, że odczytuje i zapisuje każdy element dwukrotnie, raz w fazie klasyfikacji i raz w fazie permutacji bloków. Jednak algorytm działa do trzech razy szybciej niż inni najnowocześniejsi konkurenci działający na miejscu i do 1,5 razy szybciej niż inni najnowocześniejsi konkurenci sekwencyjni. Ponieważ próbkowanie zostało już omówione powyżej, trzy późniejsze etapy zostaną bardziej szczegółowo omówione poniżej.

Klasyfikacja lokalna

W pierwszym kroku tablica wejściowa jest dzielona na $.$ bloków o równej wielkości, po jednym dla każdego procesora Każdy procesor dodatkowo przydziela ${\ displaystyle k}$ bufory o takim samym rozmiarze jak bloki, po jednym dla każdego zasobnika. Następnie każdy procesor skanuje swój pasek i przenosi elementy do bufora odpowiedniego zasobnika. Jeśli bufor jest pełny, bufor jest zapisywany na pasku procesorów, zaczynając od przodu. Zawsze jest co najmniej jeden rozmiar bufora pustej pamięci, ponieważ aby bufor został zapisany (tzn. bufor jest pełny), trzeba było przeskanować co najmniej cały rozmiar bufora zawierający więcej elementów niż elementy zapisane z powrotem. Zatem każdy pełny blok zawiera elementy tego samego segmentu. Podczas skanowania śledzony jest rozmiar każdego wiadra.

Zablokuj permutację

Najpierw wykonywana jest operacja sumy przedrostków, która oblicza granice przedziałów. Ponieważ jednak w tej fazie przesuwane są tylko pełne bloki, granice są zaokrąglane w górę do wielokrotności rozmiaru bloku i przydzielany jest pojedynczy bufor przepełnienia. Przed rozpoczęciem permutacji bloków niektóre puste bloki mogą wymagać przesunięcia na koniec wiadra. $i}$ wskaźnik zapisu $jest$ ustawiany na początek podtablicy wiadra każdego wiadra i wskaźnik odczytu $} }$ jest ustawiony na ostatni niepusty blok w podtablicy zasobnika ${\ displaystyle b_ {i}}$ dla każdego zasobnika.

$o$ pracę, każdemu procesorowi przypisuje się inny podstawowy zasobnik blok. W każdym kroku, jeśli oba bufory wymiany są puste, procesor zmniejsza wskaźnik odczytu $i$ blok w ${\ displaystyle$ i umieszcza go w jednym ze swoich buforów wymiany. Po określeniu $}$ docelowego bloku poprzez sklasyfikowanie pierwszego elementu bloku, zwiększa on wskaźnik zapisu, odczytuje b re $}$ blok $i$ blok w docelowym Jeśli ${\ displaystyle w_ {cel}> r_ {cel}}$ bufory wymiany są znowu puste. W przeciwnym razie blok pozostający w buforach wymiany musi zostać wstawiony do docelowego zasobnika.

Jeśli wszystkie bloki w podtablicy głównego zasobnika procesora znajdują się we właściwym zasobniku, następny zasobnik jest wybierany jako zasobnik podstawowy. Jeśli procesor raz wybierze wszystkie zasobniki jako zasobnik podstawowy, procesor jest zakończony.

Posprzątać

Ponieważ w fazie permutacji bloków przesunięto tylko całe bloki, niektóre elementy mogą nadal być nieprawidłowo rozmieszczone wokół granic segmentów. Ponieważ w tablicy musi być wystarczająco dużo miejsca dla każdego elementu, te nieprawidłowo umieszczone elementy można przenieść do pustych miejsc od lewej do prawej, na koniec uwzględniając bufor przepełnienia.

Zobacz też

Linki zewnętrzne

Sortowanie próbek i pochodne Frazera i McKellara:

Przystosowany do użytku na komputerach równoległych:

Algorytmy sortowania
Teoria	Teoria złożoności obliczeniowej Notacja dużego O Całkowite zamówienie Listy Zastąpienie Stabilność Sortowanie porównawcze Sortowanie adaptacyjne Sieć sortująca Sortowanie liczb całkowitych Sortowanie X + Y Model transdychotomiczny Sortowanie kwantowe
Rodzaje wymiany	Sortowanie bąbelkowe Rodzaj shakera do koktajli Sortowanie nieparzyste-parzyste Sortowanie grzebieniowe Gatunek gnoma Sortowanie proporcjonalne Szybkie sortowanie Powolne sortowanie Stooge sort Bogosort
Sortowanie przez wybór	Sortowanie przez wybór sortowanie Sortowanie gładkie Sortowanie drzewa kartezjańskiego Sortowanie turniejowe Sortowanie cykliczne Sortowanie według słabej sterty
Sortowanie przez wstawianie	Sortowanie przez wstawianie sortowanie skorup sortowanie Sortowanie drzew Sortowanie w bibliotece Sortowanie cierpliwości
Scal sortowania	Sortuj przez scalanie Kaskadowe sortowanie przez scalanie Oscylacyjne sortowanie przez scalanie Sortowanie przez scalanie polifazowe
Sortowanie dystrybucji	Rodzaj amerykańskiej flagi Sortowanie koralików Sortowanie kubełkowe sortowanie seryjne Sortowanie liczące Sortowanie interpolacyjne Rodzaj przegródek Sortowanie mapy zbliżeniowej Sortowanie według radixa sortowanie błyskawiczne
Sortowania równoległe	Sortownik bitoniczny Batcher nieparzyste-parzyste scalanie Sieć sortowania parami sortowanie próbek
Rodzaje hybrydowe	Sortowanie przez scalanie bloków Sortowanie według Kirkpatricka-Reischa Timsort Introsort sortowanie Sortowanie przez wstawianie
Inny	Sortowanie topologiczne Porządek przedtopologiczny Sortowanie naleśników Rodzaj spaghetti