Timsort

	Timsort
Namena	sortiranje
Struktura podataka	niz
Vremenska kompl.
Srednja VK
Memorijska kompl.

Timsort je hibridni algoritam za sortiranje, derivat sortiranja spajanjem i selekcijom, dizajniran da se ponaša dobro na mnogo vrsta realnih svetskih podataka. Napravio ga je Tim Peters 2002. godine za potrebe Pajton programskog jezika. Algoritam pronalazi podskupove podataka koji su već poređani, i koristi to znanje da sortira ostatak efikasnije. Ovo se radi spajanjem identifikovanog skupa, koji se naziva prolaz, sa postojećim prolazima dok određeni kriterijum nije ispunjen. Timsort je Pajtonov standardni algoritam za sortiranje od verzije 2.3. Koristi se za sortiranje nizova u Java SE 7,^[2] na Android platformi,^[3]i u GNU Oktavi.^[4]

Operacije uredi

Timsort je dizajniran da koristi prednosti parcijalnog redosleda koji već postoji u većini podataka iz realnog sveta. Timsort radi tako što nalazi prolaze, podskupove od najmanje dva elementa, među podacima. Prolazi su ili neopadajući(svaki element je jednak ili veći od prethodnog) ili striktno opadajući(svaki element je manji od prethodnog). Ako je opadajući, onda mora biti strogo opadajući, pošto se opadajući prolazi kasnije obrću jednostavnim zamenama elemenata sa oba kraja konvergirajući u sredini. Ovaj metod je stabilan ako se elementi prezentuju u striktno opadajućem redosledu. Posle obavljanja ovakvog prolaza u datom nizu, Timsort ga prihvata i procesuira, i onda traži sledeći prolaz.

Miniprolaz uredi

Timsort algoritam traži ovakve sortirane sekvence, miniprolaze, da ubrza postupak

Prirodni prolaz je podniz koji je već sortiran. Prirodni podnizi u realnom svetu mogu biti podaci različitih dužina. Timsort bira tehnike sortiranja u zavisnosti od dužine prolaza. Na primer, ako je prolaz manji od određene dužine, koristi se sortiranje umetanjem. Prema tome, timsort je prilagodljiv algoritam.^[5] Veličina prolaza se poredi sa minimumom veličine prolaza. Minimalna veličina prolaza(miniprolaz) zavisi od dužine niza. Za niz koji ima manje od 64 elementa, miniprolaz je veličine niza, redukujući timsort na sortiranje umetanjem. Za veće nizove, miniprolaz se bira u rangu između 32 i 64 elementa, tako da je veličina niza, podeljena miniprolazom, jednaka ili malo manja od stepena dvojke. Finalni algoritam uzima šest najznačajnijih bitova veličine niza, dodaje jedan ako su svi nedostajući bitovi postavljeni, i koristi taj rezultat kao miniprolaz. Ovaj algoritam radi za sve nizove, uključujući i one manje od 64.^[5]

Sortiranje umetanjem uredi

Kada su nizovi slučajni, prirodni prolazi će verovatno imati manje elemenata od miniprolaza. U ovom slučaju, određen broj uspešnih elemenata se bira, i sortiranje umetanjem povećava veličinu prolaza do miniprolaza. Prema tome, većina prolaza u slučajnom nizu su, ili postanu, miniprolazi u veličini. Rezultat su efikasna, balansirana spajanja. Takođe, rezultuje razumnim brojem poziva funkcija pri implementaciji algoritma.^[6]

Spajanje memorije uredi

Miniprolazi se umeđu u stek. Ako X < Y + Z tada se X i Y se spajaju i umeću u stek. Ovako, spajanje je kontinuirano sve dok svi nizovi ne zadovoljavaju a)X > Y + Z i b)Y > Z

Kada su dužine prolaza optimizovane, prolazi se spajaju. Kada je prolaz pronađen, algoritam gura njegovu baznu adresu i dužinu na stek. Funkcija određuje da li će prolaz biti spojen sa prethodnim prolazima. Timsort ne spaja neuzastopne prolaze, jer ako bi se to radilo izazvalo bi da element, koji je zajednički za sva tri prolaza postane nesortiran. Prema tome, spajanje se uvek radi nad uzastopnim prolazima. Zbog ovoga, tri najviša prolaza na steku koji su nesortirani se gledaju. Ako, na primer, X, Y, Z, predstavljaju dužine tri najviša prolaza na steku, algoritam spaja prolaze tako da sledeća dva pravila zadovoljena:

X > Y + Z
Y > Z^[5]

Na primer, ako prvo pravilo nije zadovoljeno trenutnim statusom prolazom, to jest, ako X < Y + Z, tada se Y spaja sa manjim izmezu X i Y. Spajanje se nastavlja dok oba pravila nisu ispunjena. Tada algoritam određuje sledeći prolaz.^[6] Pravila gore su napravljena sa ciljem održavanja veličine prolaza što je moguće bliže jedna drugoj da bi se balansirala spajanja. Samo mali broj prolaza se pamti, pošto je stek specifične veličine. Algoritam koristi sveže pojave prolaza da ih spoje, u keš memoriji. Prema tome, kompromis se postiže tako što se odlaže spajanje, a koristi sveže pojavljivanje u keš memoriji.

Procedura spajanja uredi

Algoritam stvara privremenu memoriju jednaku veličini manjeg niza. Tada, on premešta iz(recimo da je H manje)H u privremenu memoriju i onda sortira i puni elemente u finalnom redu u kombinovan prostor od H i U

Spajanje susednih prolaza se radi uz pomoć privremene memorije. Privremena memorija je veličine manjih od dva prolaza. Algoritam kopira manji od dva prolaza u privremenu memoriju i koristi originalnu memoriju i memoriju drugog prolaza da smesti sortirani rezultat. Jednostavni algoritam sortiranja radi sleva nadesno, ili zdesna nalevo, u zavisnosti koji je prolaz manji, na privremenoj i originalnoj memoriji većeg prolaza. Krajnji sortirani prolaz se smešta u originalnu memoriju dva inicijalna prolaza. Timsort traži odgovarajuće pozicije za početni element jednog niza u drugom koristeći adaptaciju binarne pretrage. Na primer, dva prolaza A i B trebaju biti spojeni, a A je manji prolaz. U ovom slučaju binarna pretraga gleda A da nađe prvu poziciju veću od prvog elementa u B(a`). Primetimo da su A i B već sortirani individualno. Kada je a` je pronađen, algoritam može ignorisati elemente pre te pozicije dok ubacuje B. Slično, algoritam takođe traži najmanji element u B(b`) veći od najvećeg elementa u A(a). Elementi posle b` mogu takođe biti ignorisani pri spajanju. Ova preliminarna pretraga nije efikasna za visok stepen nasumičnosti podataka, ali je efikasna za druge situacija, pa je prema tome, uključena.

Galopirajući mod uredi

Elementi(označeni plavom strelicom) se porede i manji element se smešta na finalnu poziciju(koju označava crvena strelica).

Spajanje se uglavnom dešava kad je pozvan „jedan po jedan par“, kada su elementi oba prolaza prošli poređenje. Kada algoritam spaja levo nadesno, manji od dva se dovodi u deo za spajanje. Brojač broja puta u kojim se krajnji element pojavi u datom prolazu se pamti. Kada ova vrednost dostigne određeni prag, MIN_GALOP, spajanje se prebacuje u „galopirajući mod“. U ovom metodu se koristi prethodno pomenuta adaptacija binarne pretrage, da se utvrdi gde prvi element manjeg niza treba biti smešten u većem nizu(i suprotno). Funkcije mege-lo i merge-hi inkrementiraju vrednost min_galopa, ako galopiranje nije efikasno, i dekrementira ako jeste. Ako više uzastopnih elemenata dolazi iz različitih prolaza, izlazi se iz galopirajućeg moda.^[5]

Svi crveni elementi su manji od plavih(ovde, 21). Prema tome, mogu biti pomereni u deo do krajnjeg niza.

U galopirajućem modu, algoritam traži prvi element jednog niza u drugom. Ovo se radi poređenjem prvog elementa(inicijalnog elementa) sa nultim elementom u drugom nizu, onda sa prvim, trećim i tako dalje, to je (2k-1)ti element, tako da se dobije rang elemenata između kojih će inicijalni element biti. Ovo sužava rang binarne pretrage, prema tome povećava efikasnost. Galopiranje se pokazalo efikasnije osim u slučajevima specifično dugih prolaza, ali nasumični podaci obično imaju kraće prolaze. Takođe, u slučajevima kada se galopiranje pokazuje manje efikasno od binarne pretrage, izlazi se iz galopirajućeg moda.

Galopiranje nije uvek efikasno. Jedan od razloga je veliki broj poziva funkcija. Pozivi funkcija su skupi i prema tome kada se javljaju često, utiču na efikasnost programa. U nekim slučajevima galopiranje zahteva više poređenja od obične linearne pretrage. Dok za prve slučajeve oba moda mogu zahtevati isti broj poređenja, tokom vremena galopiranje zahteva 33% više poređenja od linearne pretrage da bi dobio isti rezultat. Dodatno, sva poređenja se vrše pozivom funkcija.

Galopiranje je korisno jedino kada je početni element prolaza nije među prvih sedam elemenata drugog prolaza. Ovo implicira MIN_GALOP od sedam. Da bi se izbegla zadržavanja galopirajućeg moda, spajajuće funkcije podešavaju vrednost min_galopa. Ako je element iz niza koji trenutno vraća elemente, min_galop se smanjuje za jedan. Inače, vrednost se povećava za jedan, pa smanjuje verovatnoću prelaska u galopirajući mod. Kada se ovo uradi, u slučaju nasumičnih podataka, vrednost min_galopa se povaćava toliko da se nikad ne ulazi u galopirajući mod.

U slučaju korišćenja merge-hi funkcije(tj. spaja se zdesna nalevo), galopiranje počinje sa desnog kraja podataka, odnosno od poslednjeg elementa. Galopiranje od početka takođe daje potrebne rezultate, ali pravi više poređenja. Prema tome, algoritam galopiranja koristi promenljivu koja čuva indeks od kojeg galopiranje treba početi. Timsort može ući u galopiranje u bilo kojem indeksu i nastaviti da proverava sledeći indeks koji je protivteža 1, 3, 7,...., (2k-1)... i tako dalje od trenutnog indeksa. U slučaju merge-hi, protivteža indeksu će biti -1, -3, -7...^[5]

Performanse uredi

Prema informacionoj teoriji, ni jedan algoritam poređenja ne može bolje od $\Theta (n\log n)$ poređenja u prosečnom slučaju. Na realnim podacima, timsort često zahteva mnogo manje od $\Theta (n\log n)$ poređenja, jer koristi činjenicu da su podskupovi skupa već sortirani.^[7] U slučaju da su podaci potpuno obrnuti u odnosu na smer sortiranja, timsort se približava teoretskom limitu $\log(n!)$ koji je u $\Theta (n\log n)$ Sledeća tablica poredi složenost timsorta i ostalih algoritama za sortiranje.^[5]

	Timsort	Sortiranje spajanjem	Kviksort	Sortiranje umetanjem	Sortiranje selekcijom	Smutsort
Najbolji slučaj	$\Theta (n)$	$\Theta (n\log n)$	$\Theta (n\log n)$	$\Theta (n)$	$\Theta (n^{2})$	$\Theta (n)$
Prosečan slučaj	$\Theta (n\log n)$	$\Theta (n\log n)$	$\Theta (n\log n)$	$\Theta (n^{2})$	$\Theta (n^{2})$	$\Theta (n\log n)$
Najgori slučaj	$\Theta (n\log n)$	$\Theta (n\log n)$	$\Theta (n^{2})$	$\Theta (n^{2})$	$\Theta (n^{2})$	$\Theta (n\log n)$

Sledeća tablica prikazuje poređenje prostorne različitih tehnika sortiranja. Primetimo, da sortiranje spajanjem, u najgorem slučaju ima uglavnom složenost $O(n)$

	Timsort	Sortiranje spajanjem	Kviksort	Sortiranje umetanjem	Sortiranje selekcijom	Smutsort
Prostorna složenost	$O(n)$	$O(n)$	$O(\log n)$	$O(1)$	$O(1)$	$O(1)$

Primetimo, međutim, da prostorna složenost i timsorta i sortiranja spajanjem može biti smanjena na $\log n$ po ceni brzine(pogledajte sortiranje u mestu).

Reference uredi

^ Peters, Tim. „[Python-Dev] Sorting”. Python Developers Mailinglist. Pristupljeno 24. 2. 2011. „[Timsort] also has good aspects: It's stable (items that compare equal retain their relative order, so, e.g., if you sort first on zip code, and a second time on name, people with the same name still appear in order of increasing zip code; this is important in apps that, e.g., refine the results of queries based on user input). ... It has no bad cases (O(N log N) is worst case; N-1 compares is best).”
^ jjb. „Commit 6804124: Replace "modified mergesort" in java.util.Arrays.sort with timsort”. Java Development Kit 7 Hg repo. Arhivirano iz originala 4. 9. 2012. g. Pristupljeno 24. 2. 2011.
^ „Class: java.util.TimSort<T>”. Android JDK 1.5 Documentation. Arhivirano iz originala 08. 09. 2012. g. Pristupljeno 24. 2. 2011.
^ „liboctave/util/oct-sort.cc”. Mercurial repository of Octave source code. Lines 23-25 of the initial comment block. Pristupljeno 18. 2. 2013. „Code stolen in large part from Python's, listobject.c, which itself had no license header. However, thanks to Tim Peters for the parts of the code I ripped-off.”
^ ^a ^b ^v ^g ^d ^đ timsort, python. „python_timsort”.
^ ^a ^b timsort, understanding. „understanding timsort”.
^ Martelli, Alex (2006). Python in a Nutshell (In a Nutshell (O'Reilly)). O'Reilly Media, Inc. str. 57. ISBN 978-0-596-10046-9.

Literatura uredi

Martelli, Alex (2006). Python in a Nutshell (In a Nutshell (O'Reilly)). O'Reilly Media, Inc. str. 57. ISBN 978-0-596-10046-9.

Spoljašnje veze uredi

Visualising Timsort - the source for the image on this page.
Python's listobject.c - the C implementation of timsort for CPython.
OpenJDK's TimSort.java - the Java implementation of timsort.
GNU Octave's oct-sort.cc - the C++ implementation of timsort for GNU Octave.
Sort Comparison - a Pure Python and Cython implementation of Timsort, among other sorts.

[1] Peters, Tim. „[Python-Dev] Sorting”. Python Developers Mailinglist. Pristupljeno 24. 2. 2011. „[Timsort] also has good aspects: It's stable (items that compare equal retain their relative order, so, e.g., if you sort first on zip code, and a second time on name, people with the same name still appear in order of increasing zip code; this is important in apps that, e.g., refine the results of queries based on user input). ... It has no bad cases (O(N log N) is worst case; N-1 compares is best).”

[2] . „Commit 6804124: Replace "modified mergesort" in java.util.Arrays.sort with timsort”. Java Development Kit 7 Hg repo. Arhivirano iz originala 4. 9. 2012. g. Pristupljeno 24. 2. 2011.

[3] „Class: java.util.TimSort<T>”. Android JDK 1.5 Documentation. Arhivirano iz originala 08. 09. 2012. g. Pristupljeno 24. 2. 2011.

[4] „liboctave/util/oct-sort.cc”. Mercurial repository of Octave source code. Lines 23-25 of the initial comment block. Pristupljeno 18. 2. 2013. „Code stolen in large part from Python's, listobject.c, which itself had no license header. However, thanks to Tim Peters for the parts of the code I ripped-off.”

[python_timsort-5] v ^g ^d ^đ timsort, python. „python_timsort”.

[drmaciver-6] timsort, understanding. „understanding timsort”.

[7] Martelli, Alex (2006). Python in a Nutshell (In a Nutshell (O'Reilly)). O'Reilly Media, Inc. str. 57. ISBN 978-0-596-10046-9.

[2]

[3]

[4]

[1]

[5]

[6]

[7]