Sieć sortująca

Prosta sieć sortująca składająca się z czterech przewodów i pięciu złączy

W informatyce sieci komparatorów to abstrakcyjne urządzenia zbudowane z ustalonej liczby „przewodów”, przenoszących wartości i modułów komparatorów, które łączą pary przewodów, zamieniając wartości na przewodach, jeśli nie są one w pożądanej kolejności . Takie sieci są zwykle zaprojektowane do wykonywania sortowania na ustalonych liczbach wartości, w takim przypadku nazywane są sieciami sortującymi .

Sieci sortowania różnią się od ogólnych sortowań porównań tym, że nie są w stanie obsłużyć dowolnie dużych danych wejściowych, a ich kolejność porównań jest ustalana z góry, niezależnie od wyniku poprzednich porównań. W celu sortowania większej ilości danych wejściowych konieczne jest zbudowanie nowych sieci sortujących. Ta niezależność sekwencji porównawczych jest przydatna do wykonywania równoległego i do implementacji sprzętowej . Pomimo prostoty siatek sortujących, ich teoria jest zaskakująco głęboka i złożona. Sieci sortowania zostały po raz pierwszy zbadane około 1954 roku przez Armstronga, Nelsona i O'Connora, którzy następnie opatentowali ten pomysł.

Sieci sortowania mogą być realizowane sprzętowo lub programowo . Donald Knuth opisuje, w jaki sposób komparatory binarnych liczb całkowitych można zaimplementować jako proste, trójstanowe urządzenia elektroniczne. Batcher w 1968 roku zasugerował użycie ich do budowy sieci przełączających dla sprzętu komputerowego, zastępując zarówno magistrale , jak i szybsze, ale droższe przełączniki poprzeczne . Od 2000 roku sieci sortujące (zwłaszcza bitoniczne mergesort ) są używane przez GPGPU społeczność do konstruowania algorytmów sortowania działających na procesorach graficznych .

Wstęp

Demonstracja komparatora w sieci sortującej.

Sieć sortownicza składa się z dwóch typów elementów: komparatorów i przewodów. Uważa się, że przewody biegną od lewej do prawej, przenosząc wartości (po jednym na przewód), które przechodzą przez sieć w tym samym czasie. Każdy komparator łączy dwa przewody. Kiedy para wartości, przechodząc przez parę przewodów, napotyka komparator, komparator zamienia wartości wtedy i tylko wtedy, gdy wartość górnego przewodu jest większa lub równa wartości dolnego przewodu.

We wzorze, jeśli górny przewód przenosi x , a dolny drut y , to po uderzeniu w komparator przewody przenoszą ${\ Displaystyle x'= \ min (x, y)}$ i ${\ Displaystyle y '= \ maks (x, y)}$ , odpowiednio, więc para wartości jest sortowana. Sieć przewodów i komparatorów, która prawidłowo sortuje wszystkie możliwe dane wejściowe w porządku rosnącym, nazywana jest siecią sortującą lub koncentratorem Kruskala. Odzwierciedlając sieć, możliwe jest również sortowanie wszystkich wejść w kolejności malejącej.

Poniżej przedstawiono pełne działanie prostej sieci sortującej. Jest oczywiste, dlaczego ta sieć sortująca będzie poprawnie sortować dane wejściowe; zauważ, że pierwsze cztery komparatory „zatopią” największą wartość na dole i „przeniosą” najmniejszą wartość na górę. Końcowy komparator porządkuje dwa środkowe przewody.

Głębia i skuteczność

Efektywność sieci sortującej można mierzyć jej całkowitym rozmiarem, czyli liczbą komparatorów w sieci, lub jej głębokością , zdefiniowaną (nieformalnie) jako największa liczba komparatorów, jaką dowolna wartość wejściowa może napotkać na swojej drodze przez sieć . Zauważając, że sieci sortujące mogą wykonywać pewne porównania równolegle (reprezentowane w notacji graficznej przez komparatory leżące na tej samej linii pionowej) i zakładając, że wszystkie porównania zajmą jednostkę czasu, można zauważyć, że głębokość sieci jest równa liczbę kroków czasowych wymaganych do jego wykonania.

Sieci wstawiania i bąbelków

Możemy łatwo zbudować rekurencyjnie sieć dowolnej wielkości, stosując zasady wstawiania i selekcji. Zakładając, że mamy sieć sortującą o rozmiarze n , możemy zbudować sieć o rozmiarze n + 1 , „wstawiając” dodatkową liczbę do już posortowanej podsieci (korzystając z zasady sortowania przez wstawianie ). To samo możemy osiągnąć, najpierw „wybierając” najniższą wartość z danych wejściowych, a następnie rekurencyjnie sortując pozostałe wartości (korzystając z zasady sortowania bąbelkowego ) .

Sieć sortująca zbudowana rekurencyjnie, która najpierw opada największą wartość na dół, a następnie sortuje pozostałe przewody. Na podstawie sortowania bąbelkowego

Sieć sortująca zbudowana rekurencyjnie, która najpierw sortuje pierwsze n przewodów, a następnie wstawia pozostałą wartość. Na podstawie sortowania przez wstawianie

Struktura tych dwóch sieci sortowania jest bardzo podobna. Konstrukcja dwóch różnych wariantów, która łączy ze sobą komparatory, które można wykonać jednocześnie, pokazuje, że w rzeczywistości są one identyczne.

Sieć sortowania bąbelków

Sieć sortowania przez wstawianie

Przy uwzględnieniu komparatorów równoległych sortowanie bąbelkowe i sortowanie przez wstawianie są identyczne

Sieć wstawiania (lub równoważnie sieć bąbelkowa) ma głębokość 2 n - 3 , gdzie n jest liczbą wartości. Jest to lepsze niż O ( n log n ) potrzebny maszynom o swobodnym dostępie , ale okazuje się , że istnieją znacznie wydajniejsze sieci sortujące o głębokości zaledwie O ( log ² n ) , jak opisano poniżej .

Zasada zero-jedynkowa

Chociaż łatwo jest udowodnić słuszność niektórych sieci sortujących (takich jak sortownik wstawiania/bąbelkowy), nie zawsze jest to takie proste. jest n ! permutacji liczb w sieci n -przewodowej, a przetestowanie ich wszystkich zajęłoby znaczną ilość czasu, zwłaszcza gdy n jest duże. Liczbę przypadków testowych można znacznie zmniejszyć, do 2 ⁿ , stosując tzw. zasadę zero-jedynkową. Chociaż nadal jest wykładniczy, jest mniejszy niż n ! dla wszystkich n ≥ 4 , a różnica rośnie dość szybko wraz ze wzrostem n .

Zasada zero-jedynkowa stwierdza, że ​​jeśli sieć sortująca może poprawnie posortować wszystkie 2 ⁿ sekwencji zer i jedynek, to jest ona również ważna dla dowolnych uporządkowanych danych wejściowych. To nie tylko drastycznie zmniejsza liczbę testów potrzebnych do ustalenia ważności sieci, ale jest również bardzo przydatne w tworzeniu wielu konstrukcji sieci sortujących.

Zasadę można udowodnić, obserwując najpierw następujący fakt dotyczący komparatorów: kiedy monotonicznie rosnąca funkcja f jest stosowana do wejść, tj. x i y są zastępowane przez f ( x ) i f ( y ) , to komparator daje min( fa ( x ), fa ( y )) = fa (min( x , y )) i max ( fa ( x ), fa ( y )) = fa (max ( x , y )) . Przez indukcję po głębokości sieci wynik ten można rozszerzyć do lematu stwierdzającego, że jeśli sieć przekształci ciąg a ₁ , ..., a _n w b ₁ , ..., b _n , to przekształci f ( za ₁ ), ..., fa ( za _n ) w fa ( b ₁ ), ..., fa ( b _n ) . Załóżmy, że jakieś wejście a ₁ , ..., a _n zawiera dwa elementy a _i < a _j , a sieć niepoprawnie zamienia je miejscami na wyjściu. Wtedy również nieprawidłowo posortuje f ( a ₁ ), ..., f ( a _n ) dla funkcji

${\ Displaystyle f (x) = {\ rozpocząć {przypadki} 1 \ & {\ mbox {jeśli}} x> a_ {i} \\ 0 \ & {\ mbox {w przeciwnym razie.}} \ koniec {przypadków}}}$

Ta funkcja jest monotoniczna, więc mamy zasadę zero-jedynkową jako przeciwstawną .

Konstruowanie sieci sortowania

Istnieją różne algorytmy do konstruowania sieci sortowania o głębokości O (log ² n ) (stąd rozmiar O ( n log ² n ) ), takie jak Batcher nieparzyste-parzyste scalanie , sortowanie bitoniczne , sortowanie Shell i sieć sortowania parami . Sieci te są często wykorzystywane w praktyce.

Możliwe jest również konstruowanie sieci o głębokości O (log n ) (stąd rozmiar O ( n log n ) ) przy użyciu konstrukcji zwanej siecią AKS , od nazwiska jej odkrywców Ajtai , Komlós i Szemerédi . Chociaż jest to ważne odkrycie teoretyczne, sieć AKS ma bardzo ograniczone zastosowanie praktyczne ze względu na dużą stałą liniową ukrytą w notacji Big-O . Wynika to częściowo z konstrukcji grafu ekspandera .

Uproszczona wersja sieci AKS została opisana przez Patersona w 1990 roku, który zauważył, że „stałe uzyskane dla głębokości ograniczonej nadal uniemożliwiają konstrukcji wartość praktyczną”.

Nowsza konstrukcja zwana zygzakowatą siecią sortującą o rozmiarze O ( n log n ) została odkryta przez Goodricha w 2014 roku. Chociaż jej rozmiar jest znacznie mniejszy niż w przypadku sieci AKS, jej głębokość O ( n log n ) sprawia, że ​​nie nadaje się do implementacja równoległa.

Optymalne sieci sortowania

Dla małej, ustalonej liczby wejść n , można zbudować optymalne sieci sortujące, albo o minimalnej głębokości (dla maksymalnie równoległego wykonania), albo o minimalnej wielkości (liczba komparatorów). Sieci te można wykorzystać do zwiększenia wydajności większych sieci sortujących, wynikających z rekurencyjnych konstrukcji np. Batchera, poprzez wczesne zatrzymanie rekurencji i wstawienie optymalnych sieci jako przypadków bazowych. Poniższa tabela podsumowuje wyniki optymalności dla małych sieci, dla których znana jest optymalna głębokość:

N	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
Głębokość	0	1	3	3	5	5	6	6	7	7	8	8	9	9	9	9	10
Rozmiar, górna granica	0	1	3	5	9	12	16	19	25	29	35	39	45	51	56	60	71
Rozmiar, dolna granica (jeśli jest inna)													43	47	51	55	60

W przypadku większych sieci nie jest obecnie znana ani optymalna głębokość, ani optymalny rozmiar. Dotychczas znane granice przedstawia poniższa tabela:

N	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32
Głębokość, górna granica	11	11	11	12	12	12	12	13	13	14	14	14	14	14	14
Głębokość, dolna granica	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10
Rozmiar, górna granica	77	85	91	99	107	114	120	131	139	148	155	165	172	180	185
Rozmiar, dolna granica	65	70	75	80	85	90	95	100	105	110	115	120	125	130	135

Pierwszych szesnaście sieci optymalnych pod względem głębokości jest wymienionych w Knuth's Art of Computer Programming i istnieje od wydania z 1973 roku; jednakże, podczas gdy optymalność pierwszej ósemki została ustalona przez Floyda i Knutha w latach 60. XX wieku, właściwość ta została udowodniona dla ostatniej szóstki dopiero w 2014 r. (przypadki dziewiąty i dziesiąty zostały rozstrzygnięte w 1991 r.).

Dla jednego do dwunastu wejść znane są minimalne (tj. optymalne pod względem wielkości) sieci sortowania, a dla wyższych wartości dolne granice ich rozmiarów S ( n ) można wyprowadzić indukcyjnie, korzystając z lematu Van Voorhisa (s. 240): S ( n ) ≥ S ( n - 1) + ⌈log ₂ n ⌉ . Pierwsze dziesięć optymalnych sieci jest znanych od 1969 roku, przy czym pierwszych osiem jest ponownie znanych jako optymalne od czasu prac Floyda i Knutha, ale optymalność przypadków n = 9 i n = 10 rozwiązanie trwało do 2014 roku. Optymalność najmniejszych znanych sieci sortowania dla n = 11 i n = 12 została rozwiązana w 2020 roku.

Niektóre prace nad zaprojektowaniem optymalnej sieci sortowania zostały wykonane przy użyciu algorytmów genetycznych : D. Knuth wspomina, że ​​najmniejszą znaną sieć sortowania dla n = 13 odkrył Hugues Juillé w 1995 r. „Poprzez symulację ewolucyjnego procesu hodowli genetycznej” (s. 226) oraz że sieci sortowania o minimalnej głębokości dla n = 9 i n = 11 zostały znalezione przez Lorena Schwieberta w 2001 r. „za pomocą metod genetycznych” (s. 229).

Złożoność testowania sieci sortujących

O ile P=NP , problem testowania, czy kandydująca sieć jest siecią sortującą, prawdopodobnie pozostanie trudny dla sieci o dużych rozmiarach, ponieważ problem jest współ-NP -kompletny.

• Anioł, O.; Holroyd, AE; Romik D.; Virag, B. (2007). „Sieci losowego sortowania” . Postępy w matematyce . 215 (2): 839–868. arXiv : matematyka/0609538 . doi : 10.1016/j.aim.2007.05.019 .

Linki zewnętrzne

• Lista najmniejszych sieci sortujących dla podanej liczby wejść
• Sieci sortowania
• ROZDZIAŁ 28: SIECI SORTOWANIA
• Sieci sortowania
• Narzędzie do generowania i tworzenia wykresów sieci sortowania
• Sieci sortujące i algorytm END
• Lipton, Richard J .; Regan, Ken (24 kwietnia 2014). „Galaktyczne sieci sortowania” . Zaginiony list Gödla i P=NP .
• Sortowanie ważności sieci