The Art of Machinery

En hvilken som helst ordentlig algoritmebog vil forklare, hvor hurtige sorteringsalgoritmer som quicksort og heapsort er, men det kræver ikke vanvittig matematik at bevise, at de er så asymptotisk hurtige, som man overhovedet kan blive.

En pedantisk note om notation

De fleste dataloger bruger big-O notation til at betyde “asymptotisk lige, op til en konstant skaleringsfaktor”, hvilket ikke helt er det samme som det betyder for andre matematikere. Beklager, jeg bruger big-O som i lærebøger i datalogi, men jeg blander det i det mindste ikke sammen med andre matematiske notationer.

Sammenligningsbaseret sortering

Lad os se på det særlige tilfælde af algoritmer, der sammenligner værdier to ad gangen (som quicksort og heapsort, og de fleste andre populære algoritmer). Idéerne kan senere udvides til alle sorteringsalgoritmer.

Et simpelt tælleargument for det værste tilfælde

Sæt, at du har et array med fire elementer, der alle er forskellige, i tilfældig rækkefølge. Kan man sortere det ved kun at sammenligne et enkelt par af elementerne? Naturligvis ikke, men her er en god grund til at bevise, at du ikke kan: For at sortere arrayet er du pr. definition nødt til at omarrangere elementerne for at bringe dem i orden. Med andre ord skal du vide, hvilken permutation der er brug for. Hvor mange mulige permutationer er der? Det første element kan flyttes til en af fire pladser, det andet element kan flyttes til en af de tre resterende pladser, det tredje element har to muligheder, og det sidste element skal tage den ene tilbageværende plads. Der er altså 4×3×2×2×1=4!=244 \ gange 3 \ gange 2 \ gange 1 = 4! = 24 mulige permutationer at vælge imellem, men der er kun to mulige resultater ved at sammenligne to forskellige ting: “STØRRE” og “MINDRE”. Hvis du lavede en liste over alle mulige permutationer, kunne du måske beslutte, at “STØRRE” betyder, at du har brug for permutation nr. 8, og “MINDRE” betyder, at du har brug for permutation nr. 24, men du kan på ingen måde vide, hvornår du har brug for de andre 22 permutationer.

Med to sammenligninger har du 2×2=42 \ gange 2 = 4 mulige resultater, hvilket stadig ikke er nok. Du kan ikke sortere alle mulige blandede array’er, medmindre du foretager mindst fem sammenligninger (25=322^5 = 32). Hvis W(N)W(N) er det værst tænkelige antal sammenligninger, der er nødvendige for at sortere NN forskellige elementer ved hjælp af en eller anden algoritme, kan vi sige

2W(N)≥N!2^{W(N)} \geq N!

Tager man en logaritme base 2,

W(N)≥log2N!W(N) \geq \log_2{N!}

Asymptotisk set er N!N! vokser som NNNN^N (se også Stirlings formel), så

W(N)⪰logNNN=NlogNW(N) \succeq \log{N^N} = N\log{N}

O(NlogN)O(N\log N) er en O(NlogN)O(N\log N) grænse for det værste tilfælde bare ved at tælle udgange.

Gennemsnitligt tilfælde fra informationsteori

Vi kan få et stærkere resultat, hvis vi udvider dette tælleargument med en smule informationsteori. Her er, hvordan vi kan bruge en sorteringsalgoritme som en kode til overførsel af information:

1. Jeg tænker på et tal – lad os sige 15
2. Jeg slår permutation nr. 15 op fra listen over permutationer af fire elementer
3. Jeg kører sorteringsalgoritmen på denne permutation og registrerer alle sammenligningsresultaterne “STØRRE” og “MINDRE”
4. Jeg overfører sammenligningsresultaterne til dig i binær kode
5. Du gentager mit sorteringsalgoritmeforløb, trin for trin, idet du henviser til min liste over sammenligningsresultater efter behov
6. Nu da du ved, hvordan jeg omarrangerede mit array for at få det sorteret, kan du vende permutationen om for at finde mit oprindelige array
7. Du slår mit oprindelige array op i permutationslisten for at finde ud af, at jeg overførte tallet 15

Okay, det er lidt mærkeligt, men det kan lade sig gøre. Det betyder, at sorteringsalgoritmer er bundet af de samme love somnormale kodningsordninger, herunder den sætning, der beviser, at der ikke findes en universel datakompressor. Jeg overførte en bit pr. sammenligning, som algoritmen foretager, så i gennemsnit må antallet af sammenligninger være mindst det antal bits, der er nødvendige for at repræsentere mine data, i henhold til informationsteorien. Mere teknisk set må det gennemsnitlige antal sammenligninger være mindst Shannon-entropien af mine inputdata, målt i bits. Entropi er et matematisk mål for informationsindholdet eller uforudsigeligheden af noget.

Hvis jeg har et array af NN-elementer, der kan være i enhver mulig rækkefølge uden skævhed, så er entropien maksimeret og er log2N!\log_2{N!} bits. Det beviser, at O(NlogN)O(N\log{N}) er et optimalt gennemsnit for en sammenligningsbaseret sortering med vilkårligt input.

Det er teorien, men hvordan er de virkelige sorteringsalgoritmer i forhold til hinanden? Nedenfor er et plot af det gennemsnitlige antal sammenligninger, der er nødvendige for at sortere et array. Jeg har sammenlignet det teoretiske optimum med naiv quicksort og Ford-Johnson merge-insertion-sortering, som er designet til at minimere sammenligninger (selv om den sjældent er hurtigere end quicksort generelt, fordi der er mere i livet end at minimere sammenligninger). Siden den blev udviklet i 1959, er merge-insertion sort blevet justeret for at presse nogle få sammenligninger mere ud, men plottet viser, at den allerede er næsten optimal.

Det er rart, når lidt teori giver et så tæt praktisk resultat.

Summary so far

Her er, hvad der er blevet bevist indtil videre:

1. Hvis arrayet kunne starte i en hvilken som helst rækkefølge, er der mindst O(NlogN)O(N\log{N}) sammenligninger nødvendige i værste tilfælde
2. Det gennemsnitlige antal sammenligninger skal være mindst arrayets entropi, hvilket er O(NlogN)O(N\log{N}) for tilfældigt input

Bemærk, at #2 gør det muligt for sammenligningsbaserede sorteringsalgoritmer at være hurtigere end O(NlogN)O(N\log{N}), hvis input er lav entropi (med andre ord, mere forudsigeligt). Sammenlægningssortering er tæt på O(N)O(N), hvis input indeholder mange sorterede subrækker. Insertion sortering er tæt på O(N)O(N), hvis input er et array, der blev sorteret, før det blev forstyrret en smule. Ingen af dem slårO(NlogN)O(N\log{N}) i værste tilfælde, medmindre nogle array-ordneringer er umulige som input.

Generelle sorteringsalgoritmer

Sammenligningsbaserede sorteringer er et interessant specialtilfælde i praksis, men der er intet teoretisk specielt vedCMP i forhold til enhver anden instruktion på en computer. Begge ovenstående argumenter kan generaliseres til enhver sorteringsalgoritme, hvis man bemærker et par ting:

1. De fleste computerinstruktioner har mere end to mulige udgange, men har stadig et begrænset antal
2. Det begrænsede antal udgange betyder, at en instruktion kun kan behandle en begrænset mængde entropi

Det giver os den samme O(NlogN)O(N\log{N}) nedre grænse for antallet af instruktioner. Enhver fysisk realiserbar computer kan kun behandle et begrænset antal instruktioner ad gangen, så det er også en O(NlogN)O(N\log{N})-nedre grænse for den nødvendige tid.

Men hvad med “hurtigere” algoritmer?

Den mest nyttige praktiske konsekvens af den generelle O(NlogN)O(N\log{N})-grænse er, at hvis man hører om en asymptotisk hurtigere algoritme, ved man, at den må være “snydt” på en eller anden måde. Der må være en eller anden hage, der betyder, at det ikke er en sorteringsalgoritme til generelle formål, der skalerer til arbitrært store arrays. Det kan stadig være en nyttig algoritme, men det er en god idé at læse det med småt nøje.

Et velkendt eksempel er radix sort. Den kaldes ofte en O(N)O(N)-sorteringsalgoritme, men hagen er, at den kun virker, hvis alle tallene passer ind i kk bits, og den er i virkeligheden O(kN)O(kN).

Hvad betyder det i praksis? Lad os antage, at du har en 8-bit maskine. Du kan repræsentere 28=2562^8 = 256 forskellige tal i 8 bits, så hvis du har et array med tusindvis af tal, vil du haveuplikater. Det er måske i orden til nogle anvendelser, men til andre er du nødt til at opgradere til mindst 16 bit, som kan repræsentere 216=65.5362^16 = 65.536 tal tydeligt. 32 bit vil understøtte 232=4.294.967.2962^32 = 4.294.967.296 forskellige tal. Efterhånden som størrelsen af arrayet stiger, vil antallet af nødvendige bits også stige. For at repræsentere NN forskellige tal tydeligt skal du bruge k≥log2Nk \geq \log_2{N}. Så medmindre du har det fint med mange dubletter i dit array, er O(kN)O(kN) faktisk O(NlogN)O(N\log{N}).

Behovet for O(NlogN)O(N\log{N}) af inddata i det generelle tilfælde beviser faktisk det overordnede resultat i sig selv. Dette argument er ikke så interessant i praksis, fordi vi sjældent har brug for at sortere milliarder af hele tal på en 32-bit maskine, og hvis nogen har ramt grænserne for en 64-bit maskine, har de ikke fortalt det til os andre.