Timsort: erittäin nopea, O (n log n), vakaa lajittelualgoritmi rakennettu reaalimaailmaan — ei rakennettu akateemisessa maailmassa.
Klikkaa tästä nähdäksesi päivitetyn artikkelin:
Timsort on reaalimaailman dataan tehokas lajittelualgoritmi, jota ei ole luotu akateemisessa laboratoriossa. Tim Peters loi Timsortin Python-ohjelmointikielelle vuonna 2001. Timsort analysoi ensin luettelon, jota se yrittää lajitella, ja valitsee sitten lähestymistavan, joka perustuu listan analyysiin.
algoritmin keksimisen jälkeen sitä on käytetty oletuslajittelualgoritmina Pythonissa, Javassa, Android-alustassa ja GNU Octavessa.
Timsortin iso O-notaatio on O (n log n). Oppia Big O notation, lue tämä.
Timsortin lajitteluaika on sama kuin Mergesortilla, joka on nopeampi kuin useimmilla muilla lajeilla. Timsort itse asiassa käyttää lisäys lajitella ja Mergesort, kuten näet pian.
Peters suunnitteli Timsortin käyttämään jo tilattuja elementtejä, joita on useimmissa reaalimaailman tietojoukoissa. Se kutsuu näitä jo tilattuja elementtejä ”luonnollisiksi juoksuiksi”. Se iteroituu yli datan kerätä elementit ajaa ja samanaikaisesti yhdistää ne kulkee yhdessä yhdeksi.
matriisissa on vähemmän kuin 64 elementtiä
jos matriisissa, jota yritämme lajitella, on vähemmän kuin 64 elementtiä, Timsort suorittaa lisäyslajittelun.
lisäyslaji on yksinkertainen lajitelma, joka on tehokkain pienillä listoilla. Se on melko hidas isommilla listoilla, mutta hyvin nopea pienillä listoilla. Insertiolajin idea on seuraava:
- Katso elementtejä yksi kerrallaan
- Rakenna lajiteltu lista lisäämällä Elementti oikeaan paikkaan
tässä on jäljitystaulukko, joka näyttää, miten lisäys lajittelisi luettelon
tässä tapauksessa asetamme uudet lajitellut elementit uuteen alaryhmään, joka alkaa ryhmän alusta.
tässä on gif, joka näyttää lisäyslajin:
enemmän juoksuista
Jos luettelo on suurempi kuin 64 elementtiä kuin algoritmi tekee ensimmäisen läpiviennin listan läpi etsien osia, jotka ovat tiukasti kasvavia tai laskevia. Jos osa pienenee,se kääntää sen osan.
joten jos juoksu vähenee, se näyttää tältä (jossa juoksu on lihavoitu:
jos ei laske, se näyttää tältä:
minrun on koko, joka määritetään joukon koon perusteella. Algoritmi valitsee sen niin, että useimmat satunnaisen joukon juoksut ovat Tai muuttuvat minrun-pituisiksi. Yhdistäminen 2 arrays on tehokkaampaa, kun määrä kulkee on yhtä suuri tai hieman pienempi kuin, teho kaksi. Timsort valitsee minrunin yrittääkseen varmistaa tämän tehokkuuden varmistamalla, että minrun on yhtä suuri tai pienempi kuin kahden voima.
algoritmi valitsee minrunin alueelta 32-64. Se valitsee minrunin siten, että alkuperäisen joukon Pituus, kun se jaetaan minrunilla, on yhtä suuri tai hieman pienempi kuin kahden potenssi.
jos juoksun pituus on pienempi kuin minrun, lasketaan minrunista karkaavan juoksun pituus. Käyttämällä tätä uutta numeroa, voit napata että monet kohteet ennen ajaa ja suorittaa lisäys lajitella luoda uusi ajaa.
joten jos minrun on 63 ja juoksun pituus on 33, tehdään 63-33 = 30. Voit sitten napata 30 elementtejä edessä lopussa ajaa, joten tämä on 30 kohdetta ajaa ja sitten suorittaa lisäys lajitella luoda uusi ajaa.
tämän osan valmistuttua meillä pitäisi nyt olla joukko lajiteltuja juoksuja luettelossa.
yhdistäminen
Timsort suorittaa nyt mergesortin yhdistääkseen juoksut yhteen. Timsort pitää kuitenkin huolen siitä, että se säilyttää vakauden ja yhdistää tasapainon yhdistäessään lajittelua.
vakauden säilyttämiseksi ei pitäisi vaihtaa kahta samanarvoista numeroa. Tämä ei ainoastaan pidä alkuperäisiä asemiaan luettelossa, vaan mahdollistaa algoritmin nopeamman toiminnan. Keskustelemme pian yhdistymisen saldosta.
kun Timsort löytää juoksuja, se lisää ne pinoon. Yksinkertainen pino näyttäisi tältä:
Kuvittele kasa lautasia. Lautasia ei voi ottaa alhaalta, joten ne pitää ottaa ylhäältä. Sama pätee pinoon.
Timsort yrittää tasapainottaa kahta kilpailevaa tarvetta mergesortin juostessa. Yhtäältä haluaisimme viivyttää yhdistämistä mahdollisimman pitkään, jotta voisimme hyödyntää myöhemmin mahdollisesti ilmaantuvia kuvioita. Mutta haluaisimme vielä enemmän tehdä yhdistämisen mahdollisimman pian hyödyntää ajaa, että juuri löytynyt ajaa on edelleen korkealla muistin hierarkiassa. Emme myöskään voi viivyttää yhdistämistä ”liian kauan”, koska se kuluttaa muistia muistaa ajot, jotka ovat vielä yhdistämättä, ja pino on kiinteä koko.
tämän kompromissin varmistamiseksi Timsort pitää kirjaa pinon kolmesta viimeisimmästä kohdasta ja luo kaksi lakia, joiden tulee pitää paikkansa näistä asioista:
1. A > B + C
2. B > C
missä A, B ja C ovat pinon kolme viimeisintä kohtaa.
Tim Petersin itsensä sanoin:
mikä osoittautui hyväksi kompromissiksi, säilyttää pinomerkinnöissä kaksi invarianttia, joissa A, B ja C ovat kolmen oikeimman vielä yhdistymättömän siivun pituudet
yleensä eri pituisten vierekkäisten juosten yhdistäminen paikoilleen on vaikeaa. Vielä vaikeammaksi tilanteen tekee se, että meidän on säilytettävä vakaus. Tämän kiertämiseksi Timsort asettaa syrjään väliaikaisen muistin. Se asettaa pienempi (kutsumalla sekä kulkee A ja B) kaksi kulkee että väliaikainen muisti.
laukka
Timsortin yhdistäessä A: ta ja B: tä, se huomaa yhden juoksun ”voittaneen” monta kertaa peräkkäin. Jos kävisi ilmi, että run a koostui täysin pienemmistä numeroista kuin run B, niin run a päätyisi takaisin alkuperäiselle paikalleen. Kahden juoksun yhdistäminen vaatisi paljon työtä, jotta ei saavutettaisi mitään.
useimmiten tiedoilla on jokin ennestään olemassa oleva sisäinen rakenne. Timsort olettaa, että jos monet run A: n arvot ovat pienemmät kuin run B: n arvot, on todennäköistä, että A: lla on edelleen pienemmät arvot kuin B: llä.
Timsort siirtyy tämän jälkeen laukkatilaan. Sen sijaan, että timsort tarkistaisi A: n ja B: n toisiaan vastaan, se suorittaa binäärihaun B: n sopivaan kohtaan A: ssa. näin Timsort voi siirtää A: n kokonaisen osan paikalleen. Sitten Timsort etsii A: n sopivan sijainnin B: stä.Timsort siirtää sitten kokonaisen B-tölkin osan kerralla paikalleen.
katsotaan tämä tositoimissa. Timsort tarkistaa B: n (joka on 5) ja binäärihakua käyttäen se etsii oikean sijainnin A: sta.
No, B kuuluu A: n listan häntäpäähän. nyt Timsort tarkistaa A: n (joka on 1) B: n oikeaan paikkaan. Tämä luku menee B: n alkuun. tiedämme nyt, että B kuuluu A: n loppuun ja A kuuluu B: n alkuun.
käy ilmi, että tämä operaatio ei kannata, jos sopiva paikka B: lle on hyvin lähellä A: n alkua (tai päinvastoin). laukka-tila poistuu siis nopeasti, jos se ei tuota tulosta. Lisäksi, Timsort huomioi ja vaikeuttaa päästä laukka tilassa myöhemmin lisäämällä useita peräkkäisiä vain A-tai B-vain voittoja tarvitaan tulla. Jos laukka-tila tuottaa tulosta, Timsort helpottaa paluuta.
lyhyesti sanottuna Timsort tekee 2 asiaa uskomattoman hyvin:
- suuri suorituskyky matriiseilla, joiden sisäinen rakenne on
- pystyen säilyttämään vakaan järjestyksen
aiemmin, jotta saavuttaisit vakaan järjestyksen, sinun täytyy liittää luettelosi kohteet kokonaislukujen joukkoon ja lajitella se tuplejoukkona.
koodi
jos koodi ei kiinnosta, voit vapaasti jättää tämän osan väliin. Lisätietoja on tämän osion alla.
alla oleva lähdekoodi perustuu mine ja Nanda Javarman teokseen. Lähdekoodi ei ole täydellinen, eikä se ole samanlainen kuin Pythonin virallinen lajiteltu() lähdekoodi. Tämä on vain typerä Timsort toteutin saada yleistä tuntumaa Timsort. Jos haluat nähdä Timsortin alkuperäisen lähdekoodin kaikessa komeudessaan, katso se täältä. Timsort on virallisesti toteutettu C: llä, ei Pythonilla.
Timsort on itse asiassa rakennettu suoraan Pythoniin, joten tämä koodi toimii vain selityksenä. Voit käyttää Timsort yksinkertaisesti kirjoittaa:
list.sort()
tai
sorted(list)
jos haluat hallita, miten Timsort toimii ja saada tuntumaa siihen, suosittelen, että yrität toteuttaa sen itse!
tämä artikkeli perustuu Tim Petersin alkuperäiseen johdantoon Timsortiin, joka löytyy täältä.