The Art of Machinery

Kuka tahansa kunnollinen algoritmien oppikirja selittää, kuinka nopeita lajittelualgoritmit, kuten quicksort ja heapsort, ovat, mutta ei tarvita hullua matematiikkaa todistaakseen, että ne ovat niin oireenmukaisesti nopeita kuin vain mahdollista.

Pedanttinen huomautus merkintätavoista

Useimmat tietojenkäsittelytieteilijät käyttävät big-O-merkintätapaa tarkoittaakseen ”asymptoottisesti yhtäläinen, vakion skaalauskerrointa myöten”, mikä ei ole aivan sitä, mitä se tarkoittaa muille matemaatikoille. Anteeksi, käytän big-O:ta kuten CS:n oppikirjoissa, mutta en ainakaan sekoita sitä muuhun matemaattiseen merkintätapaan.

Vertailuun perustuva lajittelu

Katsotaan niiden algoritmien erikoistapausta, jotka vertaavat arvoja kaksi kerrallaan (kuten quicksort ja heapsort ja melkein kaikki muut suositut algoritmit). Ideat voidaan myöhemmin laajentaa koskemaan kaikkia lajittelualgoritmeja.

Yksinkertainen laskenta-argumentti pahimmassa tapauksessa

Esitellään, että sinulla on joukko, jossa on neljä elementtiä, kaikki erilaisia, satunnaisessa järjestyksessä. Voitko lajitella sen vertaamalla vain yhtä elementtiparia? Ilmeisesti ei, mutta tässä on yksi hyvä syy, joka todistaa, ettet voi: Määritelmän mukaan, lajitellaksesi joukon,sinun täytyy miten järjestää elementit uudelleen, jotta saat ne järjestykseen. Toisin sanoen sinun on tiedettävä, mitä permutaatiota tarvitaan. Kuinka monta mahdollista permutaatiota on olemassa? Ensimmäinen alkio voidaan siirtää johonkin neljästä paikasta, toinen alkio voi mennä johonkin jäljellä olevista kolmesta, kolmannella alkioilla on kaksi vaihtoehtoa, ja viimeisen alkion on otettava yksi jäljellä oleva paikka. Valittavana on siis 4×3×2×1=4!=244 \times 3 \times 2 \times 1 = 4! = 24 mahdollista permutaatiota, mutta kahden eri asian vertailusta on vain kaksi mahdollista tulosta: ”SUUREMPI” ja ”PIENEMPI”. Jos tekisit listan kaikista mahdollisista permutaatioista, voisit ehkä päättää, että ”SUUREMPI” tarkoittaa, että tarvitset permutaation #8 ja ”PIENEMPI” tarkoittaa, että tarvitset permutaation #24, mutta et voi mitenkään tietää, milloin tarvitset loput 22 permutaatiota.

Kahdella vertailulla sinulla on 2×2=42 \times 2 = 4 mahdollista tulosta, mikä ei vieläkään ole tarpeeksi. Et voi lajitella kaikkia mahdollisia sekoitettuja joukkoja, ellet tee vähintään viittä vertailua (25=322^5 = 32). Jos W(N)W(N) on pahimmassa tapauksessa tarvittavien vertailujen määrä, joka tarvitaan NN:n eri elementtien lajitteluun jollain algoritmilla, voimme sanoa

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

Logaritmin perusta 2,

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

Asymptoottisesti N!N! kasvaa kuten NNN^N (katso myös Stirlingin kaava), joten

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

Ja tämä on O(NlogN)O(N\log N) raja-arvo pahimmalle tapaukselle jo pelkästään ulostulojen laskemisen perusteella.

Keskimääräinen tapaus informaatioteoriasta

Pystymme saamaan vahvemman tuloksen, jos laajennamme tuota laskenta-argumenttia hieman informaatioteorialla. Näin voisimme käyttää lajittelualgoritmia informaation välittämisen koodina:

1. Ajattelen lukua – vaikkapa 15
2. Etsin permutaation #15 neljän alkion permutaatioiden luettelosta
3. Johdan lajittelualgoritmin tälle permutaatiolle ja kirjaan ylös kaikki ”SUUREMPI”- ja ”PIENEMPI”-vertailun tulokset
4. Lähetän vertailun tulokset sinulle binäärikoodina
5. Sinä toistat lajittelualgoritmini suorituksen, askel askeleelta, viitaten vertailutulosteni luetteloon tarpeen mukaan
6. Nyt kun tiedät, miten järjestin matriisin uudelleen saadakseni sen lajitelluksi, voit kääntää permutaation päinvastaiseksi saadaksesi selville alkuperäisen matriisin
7. Katsot alkuperäisen matriisin permutaatioluettelosta saadaksesi selville, että lähetin numeron 15

Okei, se on hieman outoa, mutta se voidaan tehdä. Tämä tarkoittaa, että lajittelualgoritmeja sitovat samat lait kuin tavanomaisia koodausjärjestelmiä, mukaan lukien lause, joka todistaa, ettei universaalia datapuristinta ole olemassa. Välitän yhden bitin jokaista algoritmin tekemää vertailua kohden, joten vertailujen määrän on oltava keskimäärin vähintään yhtä suuri kuin tietojeni esittämiseen tarvittavien bittien määrä informaatioteorian mukaan. Teknisesti ottaen vertailujen keskimääräisen määrän on oltava vähintään syöttämäni datan Shannonin entropian suuruinen biteissä mitattuna. Entropia on jonkin asian informaatiosisällön eli ennustamattomuuden matemaattinen mitta.

Jos minulla on joukko NN-alkioita, jotka voivat olla missä tahansa mahdollisessa järjestyksessä ilman vääristymiä, entropia maksimoituu ja onlog2N!\log_2{N!} bittiä. Tämä todistaa, että O(NlogN)O(N\log{N}) on optimaalinen keskiarvo vertailuun perustuvalle lajittelulle mielivaltaisella syötteellä.

Tässä on teoriaa, mutta miten todelliset lajittelualgoritmit vertautuvat? Alla on kuvaaja vertailujen keskimääräisestä lukumäärästä, joka tarvitaan joukon lajitteluun. Olen verrannut teoreettista optimia naiiviin quicksort-lajitteluun ja Ford-Johnsonin merge-insertion-lajitteluun, joka on suunniteltu minimoimaan vertailuja (vaikka se on harvoin nopeampi kuin quicksort, koska elämässä on muutakin kuin vertailujen minimointi). Sen jälkeen kun se kehitettiin vuonna 1959, merge-insertion-lajittelua on paranneltu muutaman vertailun lisäämiseksi, mutta kuvaaja osoittaa, että se on jo lähes optimaalinen.

Kiva, kun pieni teoria antaa näin tiukan käytännön tuloksen.

Yhteenveto tähän mennessä

Tässä on, mitä on todistettu tähän mennessä:

1. Jos joukko voisi alkaa missä tahansa järjestyksessä, tarvitaan pahimmassa tapauksessa vähintään O(NlogN)O(N\log{N}) vertailua
2. Vertailujen keskimääräisen lukumäärän on oltava vähintään joukon entropian suuruinen, joka on O(NlogN)O(N\log{N}) satunnaiselle syötteelle

Huomaa, että #2:n avulla vertailupohjaiset lajittelualgoritmit voivat olla nopeampia kuin O(NlogN)O(N\log{N}), jos syötteen entropia on pieni (toisin sanoen paremmin ennustettava). Yhdistelmälajittelu on lähellä O(N)O(N)O(N), jos syötteessä on monia lajiteltuja alarivejä. Lisäyslajittelu on lähellä O(N)O(N)O(N), jos syötteenä on joukko, joka on lajiteltu ennen kuin sitä on hieman häiritty. Mikään niistä ei päihitäO(NlogN)O(N\log{N}) pahimmassa tapauksessa, elleivät jotkin matriisien järjestykset ole mahdottomia syötteinä.

Yleiset lajittelualgoritmit

Vertailuun perustuvat lajittelut ovat käytännössä mielenkiintoinen erikoistapaus, mutta niissä ei ole mitään teoreettisesti erikoistaCMP verrattuna mihin tahansa muuhun tietokoneen käskyyn. Molemmat edellä esitetyt väitteet voidaan yleistää koskemaan mitä tahansa lajittelualgoritmia, jos huomioidaan pari asiaa:

1. Useimmilla tietokoneen käskyillä on enemmän kuin kaksi mahdollista ulostuloa, mutta niitä on silti rajallinen määrä
2. Rajallinen määrä ulostuloja tarkoittaa sitä, että yksi käsky voi prosessoida vain rajallisen määrän entropiaa

Tämä antaa meille saman O(NlogN)O(N \log{N})-alarajoituksen käskyjen määrälle. Mikä tahansa fyysisesti toteutettavissa oleva tietokone voi käsitellä vain rajoitetun määrän käskyjä kerrallaan, joten sekin on O(NlogN)O(N\log{N}) alaraja vaaditulle ajalle.

Mutta entä ”nopeammat” algoritmit?

Yleisen O(NlogN)O(N\log{N})-rajan hyödyllisin käytännöllinen implikaatio on se, että jos kuulet jostain epäsymmetrisesti nopeammasta algoritmista, tiedät, että sen täytyy olla ”huijausta”. Täytyy olla jokin juju, joka tarkoittaa, että kyseessä ei ole yleiskäyttöinen lajittelualgoritmi, joka skaalautuu mielivaltaisen suurille matriiseille. Se saattaa silti olla käyttökelpoinen algoritmi, mutta on hyvä lukea pienellä painettu teksti tarkkaan.

Tuttu esimerkki on radix-lajittelu. Sitä kutsutaan usein O(N)O(N)-lajittelualgoritmiksi, mutta juju on siinä, että se toimii vain, jos kaikki luvut mahtuvat kk:een bittiin, ja se on oikeasti O(kN)O(kN).

Mitä se tarkoittaa käytännössä? Oletetaan, että sinulla on 8-bittinen kone. Voit esittää 28=2562^8 = 256 erilaista lukua 8 bitillä, joten jos sinulla on tuhansia lukuja sisältävä joukko, sinulla on päällekkäisyyksiä. Joissakin sovelluksissa tämä voi olla ihan ok, mutta muissa sovelluksissa sinun on päivitettävä vähintään 16-bittiseen koneeseen, joka voi esittää 216=65,5362^16 = 65,536 numeroa selvästi. 32 bittiä tukee 232=4,294,967,2962^32 = 4,294,967,296 erilaista lukua. Joukon koon kasvaessa myös tarvittavien bittien määrä kasvaa. Jotta NN eri lukua voidaan esittää selvästi, tarvitaan k≥log2Nk \geq \log_2{N}. Joten, ellet ole tyytyväinen siihen, että joukossasi on paljon kaksoiskappaleita, O(kN)O(kN) on käytännössä O(NlogN)O(N\log{N}).

O(NlogN)O(N\log{N})O(N\log{N})-syöttötiedon tarve yleisessä tapauksessa itse asiassa todistaa kokonaistuloksen jo itsessään. Tuo argumentti ei ole niin mielenkiintoinen käytännössä, koska harvoin joudumme lajittelemaan miljardeja kokonaislukuja 32-bittisellä koneella, ja jos joku on saavuttanut 64-bittisen koneen rajat, hän ei ole kertonut meille muille.