Sorteringsnätverk

Ett enkelt sorteringsnätverk bestående av fyra ledningar och fem kontakter

Inom datavetenskap är komparatornätverk abstrakta enheter uppbyggda av ett fast antal "ledningar", bärande värden och komparatormoduler som kopplar ihop par av trådar och byter ut värdena på ledningarna om de inte är i önskad ordning . Sådana nätverk är vanligtvis utformade för att utföra sortering på fasta antal värden, i vilket fall de kallas sorteringsnätverk .

Sorteringsnätverk skiljer sig från generella jämförelsesorter genom att de inte klarar av att hantera godtyckligt stora indata, och genom att deras sekvens av jämförelser är inställd i förväg, oavsett resultatet av tidigare jämförelser. För att sortera större mängder insatsvaror måste nya sorteringsnät byggas upp. Detta oberoende av jämförelsesekvenser är användbart för parallell exekvering och för implementering i hårdvara . Trots enkelheten med att sortera nät är deras teori förvånansvärt djup och komplex. Sorteringsnätverk studerades först cirka 1954 av Armstrong, Nelson och O'Connor, som sedan patenterade idén.

Sorteringsnätverk kan implementeras antingen i hårdvara eller i mjukvara . Donald Knuth beskriver hur komparatorerna för binära heltal kan implementeras som enkla elektroniska tretillståndsenheter. Batcher föreslog 1968 att man skulle använda dem för att bygga omkopplingsnätverk för datorhårdvara, och ersätta både bussar och de snabbare men dyrare tvärstångsväxlarna . Sedan 2000-talet har sorteringsnät (särskilt bitonic mergesort ) använts av GPGPU -communityt för att konstruera sorteringsalgoritmer för att köras på grafiska bearbetningsenheter .

Introduktion

Demonstration av en komparator i ett sorteringsnätverk.

Ett sorteringsnätverk består av två typer av föremål: komparatorer och ledningar. Ledningarna är tänkta att löpa från vänster till höger och bära värden (en per tråd) som korsar nätverket samtidigt. Varje komparator ansluter två ledningar. När ett par värden, som går genom ett par trådar, stöter på en komparator, byter komparatorn värdena om och endast om den översta trådens värde är större eller lika med den nedre trådens värde.

I en formel, om den övre tråden bär x och den nedre tråden bär y , så bär trådarna efter att ha träffat en komparator $x'=\min(x,y)$ och $y'=\max(x,y)$ , så värdeparet sorteras. Ett nätverk av ledningar och komparatorer som korrekt sorterar alla möjliga indata i stigande ordning kallas ett sorteringsnätverk eller Kruskal-nav. Genom att reflektera nätverket är det också möjligt att sortera alla ingångar i fallande ordning.

Den fullständiga driften av ett enkelt sorteringsnätverk visas nedan. Det är uppenbart varför detta sorteringsnätverk kommer att sortera ingångarna korrekt; Observera att de fyra första komparatorerna kommer att "sänka" det största värdet till botten och "flyta" det minsta värdet till toppen. Den sista komparatorn sorterar ut de två mittersta ledningarna.

Djup och effektivitet

Effektiviteten hos ett sorteringsnätverk kan mätas genom dess totala storlek, det vill säga antalet komparatorer i nätverket, eller genom dess djup , definierat (informellt) som det största antalet komparatorer som något ingångsvärde kan stöta på på sin väg genom nätverket . Om man noterar att sorteringsnätverk kan utföra vissa jämförelser parallellt (representerade i den grafiska notationen av komparatorer som ligger på samma vertikala linje), och om man antar att alla jämförelser tar tidsenhet, kan man se att nätverkets djup är lika med antal tidssteg som krävs för att utföra det.

Insättnings- och Bubble-nätverk

Vi kan enkelt konstruera ett nätverk av vilken storlek som helst rekursivt med hjälp av principerna för infogning och urval. Om vi ​​antar att vi har ett sorteringsnätverk av storlek n , kan vi konstruera ett nätverk av storlek n + 1 genom att "infoga" ytterligare ett nummer i det redan sorterade subnätet (med principen bakom insättningssort ). Vi kan också åstadkomma samma sak genom att först "välja" det lägsta värdet från indata och sedan sortera de återstående värdena rekursivt (med principen bakom bubblesort ).

Ett sorteringsnätverk konstruerat rekursivt som först sänker det största värdet till botten och sedan sorterar de återstående trådarna. Baserat på bubbelsortering

Ett sorteringsnätverk konstruerat rekursivt som först sorterar de första n ledningarna och sedan infogar det återstående värdet. Baserat på insättningssort

Strukturen för dessa två sorteringsnätverk är mycket lika. En konstruktion av de två olika varianterna, som kollapsar ihop komparatorer som kan utföras samtidigt visar att de i själva verket är identiska.

Bubbelsorteringsnätverk

Insättningssorteringsnätverk

När man tillåter parallella komparatorer är bubbelsortering och insättningssortering identiska

Insättningsnätverket (eller motsvarande bubbelnätverket) har ett djup på 2 n -3 , där n är antalet värden. Detta är bättre än O ( n log n ) -tiden som krävs av slumpmässiga maskiner, men det visar sig att det finns mycket effektivare sorteringsnätverk med ett djup på bara O (log ² n ) , som beskrivs nedan .

Noll-ett-principen

Även om det är lätt att bevisa giltigheten av vissa sorteringsnätverk (som insättning/bubbelsorterare), är det inte alltid så lätt. Det finns n ! permutationer av tal i ett n -trådsnätverk, och att testa dem alla skulle ta en betydande tid, speciellt när n är stort. Antalet testfall kan reduceras avsevärt, till 2 ⁿ , med den så kallade noll-ett-principen. Även om det fortfarande är exponentiellt är detta mindre än n ! för alla n ≥ 4 , och skillnaden växer ganska snabbt med ökande n .

Noll-ett-principen säger att om ett sorteringsnätverk korrekt kan sortera alla 2 ⁿ sekvenser av nollor och ettor, så är det också giltigt för godtyckligt ordnade ingångar. Detta minskar inte bara drastiskt antalet tester som behövs för att fastställa ett nätverks giltighet, det är till stor nytta för att skapa många konstruktioner av sorteringsnätverk också.

Principen kan bevisas genom att först observera följande faktum om komparatorer: när en monotont ökande funktion f appliceras på ingångarna, dvs x och y ersätts med f ( x ) och f ( y ) , då producerar komparatorn min( f ( x ), f ( y )) = f (min( x , y )) och max( f ( x ), f ( y )) = f (max( x , y )) . Genom induktion på nätverkets djup kan detta resultat utökas till ett lemma som säger att om nätverket transformerar sekvensen a ₁ , ..., a _n till b ₁ , ..., b _n , kommer det att transformera f ( a ₁ ), ..., f ( a _n ) till f ( b ₁ ), ..., f ( b _n ) . Antag att någon ingång a ₁ , ..., a _n innehåller två poster a _i < a _j , och nätverket byter felaktigt ut dessa i utgången. Då kommer den också felaktigt sortera f ( a ₁ ), ..., f ( a _n ) för funktionen

$f(x)={\begin{cases}1\ &{\mbox{if }}x>a_{i}\\0\ &{\mbox{annat.}}\end{cases}}$

Denna funktion är monoton, så vi har noll-ett-principen som kontrapositiv .

Bygga sorteringsnätverk

Olika algoritmer finns för att konstruera sorteringsnätverk med djup O (log ² n ) (därav storlek O ( n log ² n ) ) som Batcher odd-even mergesort , bitonic sort , Shell sort och Pairwise sorteringsnätverket . Dessa nätverk används ofta i praktiken.

Det är också möjligt att konstruera nätverk med djup O (log n ) (därav storlek O ( n log n ) ) med en konstruktion som kallas AKS-nätverket , efter dess upptäckare Ajtai , Komlós och Szemerédi . Även om det är en viktig teoretisk upptäckt, har AKS-nätverket mycket begränsad praktisk tillämpning på grund av den stora linjära konstanten som döljs av Big-O-notationen . Dessa beror delvis på en konstruktion av ett expanderdiagram .

En förenklad version av AKS-nätverket beskrevs av Paterson 1990, som noterade att "konstanterna som erhålls för djupbunden fortfarande förhindrar att konstruktionen är av praktiskt värde".

En nyare konstruktion som kallas O ( n log n zig -zag-sorteringsnätverket av storlek O ( n log n ) upptäcktes av Goodrich 2014. Även om dess storlek är mycket mindre än AKS-nätverk, gör dess djup ) den olämplig för en parallell implementering.

Optimala sorteringsnätverk

För små, fasta antal ingångar n kan optimala sorteringsnätverk konstrueras, med antingen minimalt djup (för maximalt parallellt utförande) eller minimal storlek (antal komparatorer) . Dessa nätverk kan användas för att öka prestandan hos större sorteringsnätverk som är ett resultat av de rekursiva konstruktionerna av t.ex. Batcher, genom att stoppa rekursionen tidigt och sätta in optimala nät som basfall. Följande tabell sammanfattar optimalitetsresultaten för små nätverk för vilka det optimala djupet är känt:

n	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
Djup	0	1	3	3	5	5	6	6	7	7	8	8	9	9	9	9	10
Storlek, övre gräns	0	1	3	5	9	12	16	19	25	29	35	39	45	51	56	60	71
Storlek, nedre gräns (om olika)													43	47	51	55	60

För större nätverk är varken det optimala djupet eller den optimala storleken kända för närvarande. De hittills kända gränserna anges i tabellen nedan:

n	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32
Djup, övre gräns	11	11	11	12	12	12	12	13	13	14	14	14	14	14	14
Djup, nedre gräns	10	10	10	10	10	10	10	10	10	10	10	10	10	10	10
Storlek, övre gräns	77	85	91	99	107	114	120	131	139	148	155	165	172	180	185
Storlek, nedre gräns	65	70	75	80	85	90	95	100	105	110	115	120	125	130	135

De första sexton djupoptimala nätverken är listade i Knuths Art of Computer Programming , och har varit det sedan 1973 års upplaga; Men även om optimaliteten för de första åtta fastställdes av Floyd och Knuth på 1960-talet, bevisades inte denna egenskap för de sista sex förrän 2014 (ärendena nio och tio avgjordes 1991).

För en till tolv ingångar är minimala (dvs. storleksoptimala) sorteringsnätverk kända, och för högre värden kan lägre gränser för deras storlekar S ( n ) härledas induktivt med hjälp av ett lemma beroende på Van Voorhis (s. 240): S ( n ) ≥ S ( n − 1) + ⌈log ₂ n ⌉ . De första tio optimala nätverken har varit kända sedan 1969, med de första åtta återigen kända som optimala sedan Floyd och Knuths arbete, men optimaliteten av fallen n = 9 och n = 10 tog till 2014 för att lösas. Optimaliteten för de minsta kända sorteringsnätverken för n = 11 och n = 12 löstes 2020.

En del arbete med att utforma optimalt sorteringsnätverk har gjorts med hjälp av genetiska algoritmer : D. Knuth nämner att det minsta kända sorteringsnätverket för n = 13 hittades av Hugues Juillé 1995 "genom att simulera en evolutionär process av genetisk avel" (s. 226) , och att minsta djupsorteringsnätverk för n = 9 och n = 11 hittades av Loren Schwiebert 2001 "med genetiska metoder" (s. 229).

Komplexiteten i att testa sorteringsnätverk

Om inte P=NP kommer problemet med att testa om ett kandidatnätverk är ett sorteringsnätverk sannolikt förbli svårt för nätverk av stora storlekar, på grund av att problemet är co-NP -komplett.

• Angel, O.; Holroyd, AE; Romik, D.; Virág, B. (2007). "Slumpmässiga sorteringsnätverk" . Framsteg i matematik . 215 (2): 839–868. arXiv : math/0609538 . doi : 10.1016/j.aim.2007.05.019 .

externa länkar

• Lista över minsta sorteringsnätverk för givet antal ingångar
• Sorteringsnätverk
• KAPITEL 28: SORTERING AV NÄTVERK
• Sorteringsnätverk
• Verktyg för att skapa och grafiska sorteringsnätverk
• Sortering av nätverk och END-algoritmen
• Lipton, Richard J .; Regan, Ken (24 april 2014). "Galaktiska sorteringsnätverk" . Gödels förlorade brev och P=NP .
• Giltighet för sorteringsnätverk