Flashsort
Flashsort är en distributionssorteringsalgoritm som visar linjär beräkningskomplexitet O ( n ) för enhetligt fördelade datamängder och relativt lite extra minnesbehov. Originalverket publicerades 1998 av Karl-Dietrich Neubert.
Begrepp
Flashsort är en effektiv implementering av histogramsortering på plats , i sig en typ av hinksortering . Den tilldelar vart och ett av de n inmatningselementen till en av m hinkar , omarrangerar effektivt inmatningen för att placera hinkarna i rätt ordning och sorterar sedan varje hink. Den ursprungliga algoritmen sorterar en inmatningsmatris A enligt följande:
- Använd ett första pass över inmatningen eller a priori -kunskap, hitta minsta och maximala sorteringsnycklar.
- Dela upp intervallet [ A min , A max ] linjärt i m hinkar.
- Gör ett pass över inmatningen och räkna antalet element A i som faller i varje hink. (Neubert kallar hinkarna för "klasser" och tilldelningen av element till deras hinkar för "klassificering".)
- Konvertera antalet element i varje hink till en prefixsumma , där L b är antalet element A i i hink b eller mindre. ( 0 L = 0 och L m = n .)
- Ordna om ingången till alla element i varje hink b lagras i positionerna A i där Lb −1 . < i ≤ L b
- Sortera varje hink med hjälp av instickssortering .
Steg 1–3 och 6 är gemensamma för alla skopsorter och kan förbättras med tekniker som är generiska för skopsortering. Speciellt är målet att hinkarna ska vara ungefär lika stora ( n / m element vardera), med det idealiska är uppdelningen i m kvantiler . Medan den grundläggande algoritmen är en linjär interpolationssort , om ingångsfördelningen är känd för att vara olikformig, kommer en icke-linjär division att närmare approximera detta ideal. På samma sätt kan den slutliga sorteringen använda vilken som helst av ett antal tekniker, inklusive en rekursiv blixtsortering.
Det som utmärker flashsortering är steg 5: en effektiv O ( n ) in-place algoritm för att samla elementen i varje hink tillsammans i korrekt relativ ordning med hjälp av endast m ord med extra minne.
Minneseffektiv implementering
Flashsort-omläggningsfasen fungerar i cykler . Element börjar med "oklassificerade", flyttas sedan till rätt hink och anses vara "klassificerade". Den grundläggande proceduren är att välja ett oklassificerat element, hitta dess rätta hink, byta ut det mot ett oklassificerat element där (vilket måste finnas, eftersom vi räknade storleken på varje hink i förväg), markera det som klassificerat och sedan upprepa med nyss bytt oklassificerat element. Så småningom byts elementet ut med sig självt och cykeln slutar.
Detaljerna är lätta att förstå med två (ordstora) variabler per hink. Den smarta delen är elimineringen av en av dessa variabler, vilket gör att dubbelt så många hinkar kan användas och därför hälften så mycket tid spenderas på den slutliga . O ( n2 ) -sortering
För att förstå det med två variabler per hink, anta att det finns två arrayer med m ytterligare ord: K b är den (fasta) övre gränsen för hink b (och 0 K = 0 ), medan L b är ett (rörligt) index till hink b , så Kb −1 . ≤ L b ≤ K b
Vi upprätthåller slinginvarianten att varje hink delas med suffix −1 < i ≤ Lb har ännu Lb i klassificerat ett oklassificerat prefix ( Ai Ai för ( Kb Lb inte < i ≤ K b flyttats till sina målhinkar) och ett för är alla i rätt hink och kommer inte att flyttas igen). Inledningsvis L b = K b och alla element är oklassificerade. Allt eftersom sorteringen fortskrider, = . Kb −1 minskas för Lb tills Lb hink alla b och alla element klassificeras i rätt
Varje omgång börjar med att hitta den första ofullständigt klassificerade hinken c (som har K c −1 < L c ) och ta det första oklassificerade elementet i den hinken A i där i = K c −1 + 1 . (Neubert kallar detta "cykelledaren".) Kopiera A i till en temporär variabel t och upprepa:
- Beräkna hinken b som t tillhör.
- Låt j = L b vara platsen där t kommer att lagras.
- Byt ut t med A j , dvs lagra t i A j samtidigt som man hämtar det tidigare värdet A j förskjutet därigenom.
- Minska L b för att återspegla det faktum att A j nu är korrekt klassificerad.
- Om j ≠ i , starta om denna loop med den nya t .
- Om j = i , är denna omgång över och hitta ett nytt första oklassificerat element A i .
- När det inte finns fler oklassificerade element är fördelningen i hinkar klar.
När det implementeras med två variabler per hink på detta sätt är valet av varje omgångs startpunkt i i själva verket godtyckligt; alla oklassificerade element kan användas som cykelledare. Det enda kravet är att cykelledarna kan hittas effektivt.
Även om den föregående beskrivningen använder K för att hitta cykelledarna, är det faktiskt möjligt att klara sig utan det, vilket gör att hela m -ordsuppsättningen kan elimineras. (När distributionen är klar kan hinkgränserna hittas i L .)
Antag att vi har klassificerat alla element upp till i −1 , och överväger A i som en potentiell ny cykelledare. Det är lätt att beräkna dess målskopa b . Genom slinginvarianten klassificeras den om Lb . < i ≤ K b , och oklassificerad om i är utanför det intervallet Den första olikheten är lätt att testa, men den andra tycks kräva värdet K b .
Det visar sig att induktionshypotesen att alla element upp till i −1 är klassificerade innebär att i ≤ K b , så det är inte nödvändigt att testa den andra olikheten.
Tänk på skopan c vilken position i hamnar i. Det vill säga K c −1 < i ≤ K c . Genom induktionshypotesen klassificeras alla element under i , som inkluderar alla hinkar upp till K c −1 < i , fullständigt. Dvs inga element som hör hemma i dessa hinkar finns kvar i resten av arrayen. Därför är det inte möjligt att b < c .
Det enda kvarvarande fallet är b ≥ c , vilket innebär K b ≥ K c ≥ i , QED
Genom att införliva detta börjar flashsort-distributionsalgoritmen med L som beskrivits ovan och i = 1 . Fortsätt sedan:
- Om i > n är distributionen komplett.
- Givet A i , beräkna den hink b som den tillhör.
- Om i ≤ Lb . är A i oklassificerad Kopiera den en temporär variabel t och:
- Låt j = L b vara platsen där t kommer att lagras.
- Byt ut t med A j , dvs lagra t i A j samtidigt som man hämtar det tidigare värdet A j förskjutet därigenom.
- Minska L b för att återspegla det faktum att A j nu är korrekt klassificerad.
- Om j ≠ i , beräkna hinken b som t tillhör och starta om denna (inre) loop med den nya t .
- A i är nu korrekt klassificerat. Öka i och starta om den (yttre) slingan.
Samtidigt som det sparar minne har Flashsort nackdelen att den räknar om hinken för många redan klassificerade element. Detta görs redan två gånger per element (en gång under bucket-counting-fasen och en andra gång när varje element flyttas), men att söka efter det första oklassificerade elementet kräver en tredje beräkning för de flesta element. Detta kan bli dyrt om hinkar tilldelas med en mer komplex formel än enkel linjär interpolation. En variant minskar antalet beräkningar från nästan 3 n till högst 2 n + m − 1 genom att ta det sista oklassificerade elementet i en oavslutad hink som cykelledare:
- Behåll en variabel c som identifierar den första ofullständigt klassificerade hinken. Låt c = 1 till att börja med, och när c > m är fördelningen komplett.
- Låt i = L c . Om i = Lc . −1 , öka c och starta om denna loop ( 0 L = 0. )
- Beräkna hink b som A i tillhör.
- Om b < c så är L c = K c −1 och vi är klara med hink c . Öka c och starta om denna loop.
- Om b = c är klassificeringen trivial. Minska L c och starta om denna loop.
- Om b > c är A i oklassificerad. Utför samma klassificeringsslinga som föregående fall och starta sedan om denna loop.
De flesta element har sina hinkar beräknade endast två gånger, förutom det sista elementet i varje hink, som används för att detektera färdigställandet av följande hink. En liten ytterligare minskning kan uppnås genom att upprätthålla en räkning av oklassificerade element och stoppa när den når noll.
Prestanda
De enda extra minneskraven är hjälpvektorn L för lagring av hinkgränser och det konstanta antalet andra variabler som används. Vidare flyttas varje element (via en temporär buffert, så två flyttoperationer) endast en gång. Denna minneseffektivitet kommer dock med nackdelen att arrayen nås slumpmässigt, så det går inte att dra fördel av en datacache som är mindre än hela arrayen.
Som med alla typer av skopor beror prestanda kritiskt på balansen i skopor. I det ideala fallet med en balanserad datamängd kommer varje hink att ha ungefär samma storlek. Om antalet m hinkar är linjärt i inmatningsstorleken n , har varje hink en konstant storlek, så att sortera en enda hink med en O ( n 2 ) algoritm som insättningssortering har komplexiteten O (1 2 ) = O (1) . Körtiden för de sista insättningssorterna är därför m ⋅ O(1) = O ( m ) = O ( n ) .
Genom att välja ett värde för m , antalet hinkar, byts bort tid som går åt till att klassificera element (hög m ) och tid som spenderas i det sista insättningssorteringssteget (låg m ). Till exempel, om m väljs proportionellt mot √ n , så är körtiden för de slutliga infogningssorteringarna därför m ⋅ O( √ n 2 ) = O ( n 3/2 ) .
I de värsta scenarierna där nästan alla element finns i ett fåtal hinkar, begränsas algoritmens komplexitet av prestandan hos den slutliga hinksorteringsmetoden, så att den försämras till O ( n 2 ) . Variationer av algoritmen förbättrar värsta tänkbara prestanda genom att använda bättre presterande sorter som quicksort eller rekursiv flashsort på hinkar som överskrider en viss storleksgräns.
För m = 0,1 n med likformigt fördelade slumpmässiga data är flashsort snabbare än heapsort för alla n och snabbare än quicksort för n > 80 . Det blir ungefär dubbelt så snabbt som quicksort vid n = 10000 . Observera att dessa mätningar gjordes i slutet av 1990-talet, då minneshierarkierna var mycket mindre beroende av cachelagring.
På grund av in situ -permutationen som flashsort utför i sin klassificeringsprocess är flashsort inte stabil . Om stabilitet krävs är det möjligt att använda en andra array så att element kan klassificeras sekventiellt. Men i detta fall kommer algoritmen att kräva O ( n ) ytterligare minne.
Se även
- Interpolationssökning , med fördelningen av objekt för sökning istället för sortering
externa länkar
- Implementeringar av randomiserad sortering på stora parallella maskiner (1992)
- Implementering av parallella algoritmer (1992)
- Visualisering av Flashsort