Timsort

Allikas: Vikipeedia
Timsort
Algoritmi liik Sortimisalgoritm
Ajaline keerukus halvimal juhul O(n log n)
Ajaline keerukus keskmiselt O(n log n)
Ajaline keerukus parimal juhul O(n)
Mahuline keerukus O(n)

Timsort on sorteerimisalgoritm, mis on saadud piste- ja ühildusmeetodeid kombineerides[1] ning alusmeetodeid optimeerides ja täiendades. Timsort loodi 2002. aastal Pythoni programmeerimiskeele jaoks Tim Petersi poolt[2]. Lisaks on Timsorti implementeeritud veel mitmed programmeerimiskeeled nagu Java,[3] Swift,[4] ja Rust.[5] Timsort töötab jaga-ja-valitse algoritmi põhimõttel, mis lühidalt seisneb kolmes sammus: jaga sisendmassiiv väiksemateks massiivideks, sorteeri väiksemad massiivid kasutades kahendpistemeetodit, ühilda saadud väiksemad massiivid tagasi üheks tervikuks. Tulemuseks on sorteeritud massiiv. Timsort kasutab ära massiivis juba esinevaid sorteeritud lõike. Timsorti halvima juhu ajaline keerukus on O(n log n), parima juhu ajaline keerukus aga O(n).

Algoritmi kirjeldus[muuda | muuda lähteteksti]

Timsort on keeruline algoritm. Süvitsi mõistmiseks on kasulik algoritm jagada osadeks. Tim Peters lõi algoritmi põhimõttega, et sorteerides ära kasutada juba sorteeritud lõike, mis esinevad pärismaailmas kasutusel olevatel andmemassiivides. Implementatsiooniks on tarvilik luua kõigepealt meetod kahendotsinguks ning piste- ja ühildusmeetodid. Timsort on stabiilne sorteerimisalgoritm, st sama väärtusega elementide järjekord sorteerimisel ei muutu.

Enne detailsemat algoritmi kirjeldust oleks tarvis teada järgmiseid termineid ja nende põhimõtteid:

näide: run (juba sorteeritud lõik massiivis)
  • run - kui massiivis on üle 64 elemendi, otsib Timsort massiivist natural run-e, mis on vähemalt kahest elemendist koosnevad juba sorteeritud massiivi lõigud, mis ongi algoritmi kontekstis run. Kui leitakse kahanevas järjekorras run, pööratakse see tagurpidi. Viited nendele lõikudele pannakse pinusse[6]. Väiksematel (pikkus n < 64) massiividel rakendatakse lihtsalt pistemeetodit.
  • minrun - massiivi pikkusest tuletatud arv vahemikus (32; 64], millega jagatise tulemusena massiivi pikkusega saadakse kas võrdne või väiksem arv mõnest kahe astmest. Algoritm valib selle arvu, sest suvalises jadas on pikkade natural run-ide esinemine ebatõenäoline. Kui natural run-is esineb vähem kui minrun elementi, pikendatakse see run minrun elementi pikaks. Suvalises massiivis selle tulemusena kipuvad kõik run-id olema pikkusega minrun.[7]

Timsort kasutab pistemeetodit sorteerimaks massiive, milles on alla 64 elemendi. Pistemeetod on suurte massiivide puhul aeglane, ent õige implementatsiooni korral väikeste massiivide puhul väga kiire.[6]

Esimene samm: minrun-i leidmine

Teine samm: sisendmassiivi tükeldamine run-ideks ning nende sorteerimine

  1. alustame massiivi algusest, otsides natural run-e
  2. kui hetkene run on väiksem kui minrun, võta järgnevaid elemente kuni selle run-i pikkus on minrun
  3. saadud run sorteeritakse pistemeetodiga

Kolmas samm: sorteeritud run-ide ühildamine

  1. ideaalis peaks massiivis olema sarnase pikkusega sorteeritud run-id
  2. loo tühi ennikutest (run-i algusaadress, run-i pikkus) koosnev pinu
  3. hakka lisama run-e järjest pinusse
  4. iga pinusse lisamise puhul tuleb kontrollida, pinu peal olevad run-id vastavad järgnevatele tingimustele:

Tingimused, mida Timsort kasutab määratlemaks, kas run-e pinu peal peab omavahel ühendama:

run-id pannakse pinusse. Kui |Z| ≤ |Y| + |X|, siis X ja Y ühildatakse ning pannakse tagasi pinusse. Ühildumine jätkub, kuni kõik run-id täidavad tingimusi i. |Z| > |X| + |Y| ja ii. |Y|>|X|

Olgu X, Y, Z pinu pealmised run-id. Püstkriipsud run-i ümber tähendavad run-i pikkust, nt |X|.

i. |Z| > |X| + |Y|

ii. |Y| > |X|[7]

Kui üks neist tingimustest on rikutud, ühendatakse omavahel Y ja lühem X või Z seast.

Seda sammu korratakse kuni kogu pinu täidab neid tingimusi.

Käsitlemata run-ide puhul vaadeldakse pinu uuesti läbi, tehes vahetusi ja ühildamisi kui vaja.

Kolmanda sammu eesmärk on hiljem ühildusmeetodiga ühendada järjest sarnasema pikkusega run-id, et ühildumine oleks efektiivne.

Näide: oletame, et meil on ideaalne juhus, meil on 8 run-i suurusega 128, 64, 32, 16, 8, 4, 2, 2 (järjekord on tegelikkuses suvaline). Algoritm ei ühenda ühtegi run-i enne, kui 2 ja 2 saavad pinus run-e kontrollides kokku. Sellele järgneb 7 perfektset, efektiivset ühendamist.

Neljas samm:

Eelnevas sammus sorteerisime ja ühendasime erinevaid run-e, et saada pinusse optimaalne viimane run-ide ühendamise järjekord, lähtuvalt pikkustest (et lõplik ühendamine toimuks võimalikult sarnase pikkusega run-idest).

Nüüd hakkame järjest ühendama kahe haaval järelejäänud run-e, lõpuks saades sorteeritud massiivi.

  1. loome ajutise run-i mille suurus on allesjäänud run-idest vähima pikkus
  2. paneme kõik elemendid lühemast run-ist ajutisse run-i
  3. võrdleme suurema ja ajutise run-i elemente:

i. neist väiksema asetame lühemasse run-i (need elemendid on ajutises olemas)

ii. seame järgmiseks vaadeldavaks elemendiks ära võetud elemendist järgmise

iii. kordame kuni üks run-idest (suurem või ajutine) on täielikult läbi vaadatud

Tulemusena lõpuks on sorteeritud massiiv.

Neljandas sammus kasutab algoritm ühildusmeetodit, kuid mitte tavalist - seda on kohandatud, suurendades efektiivsust, kasutamaks eelnevalt leitud run-e. See tähendab, et kuigi algoritm justkui ütleb neljandas sammus, et hakkame ükshaaval võrdlema kahe run-i elemente, siis tegelikult Timsort teeb seda efektiivsemalt. Näide: olgu meil run-id elementidega [1, 2, 3, 4, … 100] ning [101, 102, 103, .. 200]. Ebaefektiivne oleks neid üksikute võrdluste põhjal hakata ühildama.

Timsort kasutab selleks võtet, mida kutsutakse nimega galloping. Eesti keeles samuti galopp, tähendab see sisuliselt seda, et elemente ei tõsteta ühildatud, sorteeritud run-i mitte ükshaaval, vaid lõikude kaupa, mis kiirendab protsessi, kuna individuaalsete võrdluste arv on vähendatud. Lõigud leitakse kasutades kahendotsingut.

Näide, et toimuvat illustreerida paremini:

Olgu meil run X = [1, 2, 3, 4, 5, .. 100] ning Y = [101, 102, 103, .. 200].

Kõik punasega märgitud elemendid on väiksemad kui 21, mistõttu neid võib korraga paigutada lõpliku massiivi.

Esimesed 7 (eelnevalt defineeritud algne galopi sammu suurus) elementi run-ist X võrreldakse run Y esimese elemendiga. 101 > 7, 6, 5… Kõik need run X elemendid on väiksemad kui mistahes Y elemendid, mistõttu võib kõik need tõsta sorteeritud run-i. Vaatluse alla võetakse järgmised run X elemendid 8, 9, 10 jne ning võrreldakse taaskord Y esimese elemendi, 101-ga. Galopi samm muutub järjest suuremaks, et leida veel suuremaid lõike, mille saab sorteeritud run-i tõsta.

Joonisel on näha, et Y elemendid 9, 12, 13, 14, 15 on kõik väiksemad kui ajutises run-is olev element 21, mistõttu võib kõik punaseks värvitud Y elemendid tõsta sorteeritud run-i.

Andmete tükkide kaupa liigutamine on märgatavalt kiirem kui elementide ükshaaval võrdlemine ja tõstmine, mis annabki Timsordi tema efektiivsuse ja kiiruse.

Keerukused[muuda | muuda lähteteksti]

Ajalised keerukused:

  • Halvim juht: O(n log n)
  • Parim juht: O(n)
  • Keskmine juht: O(n log n)[8]

Ruumiline keerukus: O(n)

Verifikatsioon[muuda | muuda lähteteksti]

2015. aastal leidsid hollandi ja saksa teadlased tavapärases Java Timsordi implementatsioonis vea ning andsid välja verifitseeritud parandatud algoritmi.[9]

2018. aastal tõestati Timsordi halvima juhu ajaline keerukus.[2]

Viited[muuda | muuda lähteteksti]

  1. ↑ Zhang, Yu; Zhao, Yongwang; Sanan, David (8. detsember 2018). "A Verified Timsort C Implementation in Isabelle/HOL". arXiv.org (inglise). DOI:10.48550/arxiv.1812.03318. Vaadatud 3. jaanuaril 2024.
  2. ↑ 2,0 2,1 Auger, Nicolas; Jugé, Vincent; Nicaud, Cyril; Pivoteau, Carine (2018). "On the Worst-Case Complexity of TimSort". DROPS-IDN/v2/document/10.4230/LIPIcs.ESA.2018.4 (inglise). Schloss-Dagstuhl - Leibniz Zentrum für Informatik. DOI:10.4230/LIPIcs.ESA.2018.4.
  3. ↑ "Loading..." bugs.openjdk.org. Vaadatud 3. jaanuaril 2024.
  4. ↑ "Is sort() stable in Swift 5?". Swift Forums (inglise). 4. juuli 2019. Vaadatud 3. jaanuaril 2024.
  5. ↑ "slice - Rust". doc.rust-lang.org. Vaadatud 3. jaanuaril 2024.
  6. ↑ 6,0 6,1 "Timsort — "The Fastest Sorting Algorithm" – The IE Blog" (Ameerika inglise). 3. detsember 2019. Vaadatud 3. jaanuaril 2024.
  7. ↑ 7,0 7,1 "cpython: 034b077d3015 Objects/listsort.txt". web.archive.org. 28. jaanuar 2016. Originaali arhiivikoopia seisuga 28. jaanuar 2016. Vaadatud 3. jaanuaril 2024.{{netiviide}}: CS1 hooldus: robot: algse URL-i olek teadmata (link)
  8. ↑ "TimSort - Data Structures and Algorithms Tutorials". GeeksforGeeks (Ameerika inglise). 19. mai 2017. Vaadatud 3. jaanuaril 2024.
  9. ↑ de Gouw, Stijn; Rot, Jurriaan; de Boer, Frank S.; Bubel, Richard; Hähnle, Reiner (2015). Kroening, Daniel; Păsăreanu, Corina S. (toim-d). "OpenJDK's Java.utils.Collection.sort() Is Broken: The Good, the Bad and the Worst Case". Computer Aided Verification. Lecture Notes in Computer Science (inglise). Cham: Springer International Publishing: 273–289. DOI:10.1007/978-3-319-21690-4_16.
Pärit leheküljelt "https://et.wikipedia.org/w/index.php?title=Timsort&oldid=6598364"