Timsort

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2019. július 10-én felülvizsgált verziótól ; az ellenőrzések 11 szerkesztést igényelnek .

A Timsort egy hibrid rendezési algoritmus , amely kombinálja a beszúrásos rendezést és az összevonási rendezést , Tim Peters által 2002-ben publikált . A Timsort jelenleg a szabványos rendezési algoritmus [1] a Pythonban , az OpenJDK 7 -ben [2] , az Apple Swift Standard Library 5 -ben [3] , és az Android JDK 1.5 -ös verziójában [4] implementálva . Az algoritmus fő gondolata az, hogy a valós világban a rendezett adattömbök gyakran tartalmaznak rendezett altömböket. Ilyen adatokon a Timsort lényegesen gyorsabb, mint sok rendezési algoritmus [5] .

Az algoritmus fő ötlete

Egy speciális algoritmus szerint a bemeneti tömb altömbökre van felosztva.
Minden altömb beszúrási rendezés szerint van rendezve .
A rendezett altömböket egyetlen tömbbe gyűjtik össze egy módosított egyesítési rendezés segítségével .

Az algoritmus főbb jellemzői részletesen, nevezetesen az összevonási rendezés felosztására és módosítására szolgáló algoritmusban találhatók.

Algoritmus

Felhasznált fogalmak

N a bemeneti tömb mérete
run egy rendezett altömb a bemeneti tömbben. Sőt, nem szigorúan növekvő vagy szigorúan csökkenő sorrendben. Azok:
- vagy " ", $a_{0}\leqslant a_{1}\leqslant a_{2}\leqslant ...$
- vagy " " $a_{0}>a_{1}>a_{2}>...$
minrun - mint fentebb említettük, az algoritmus első lépésében a bemeneti tömb altömbökre lesz osztva. minrun egy ilyen altömb minimális mérete. Ezt a számot egy bizonyos logika szerint számítjuk ki az N számból.

0. lépés A minfutás kiszámítása.

(1) A minrun-ok számát (egy rendezett sorozat minimális méretét) N alapján határozzuk meg a következő elvek alapján: ne legyen túl nagy, mert a beillesztési rendezést később egy minrun méretű altömbre alkalmazzuk , és csak kis tömbökön hatásos.

(2) Ne legyen túl kicsi, mert minél kisebb az altömb, annál több iterációt kell végrehajtani az alrendszerek összevonására az algoritmus utolsó lépésében. Az N / minrun optimális értéke 2 (vagy ahhoz közeli) hatvány. Ez a követelmény annak a ténynek köszönhető, hogy az alrendszer- összevonási algoritmus megközelítőleg azonos méretű altömbökön működik a leghatékonyabban.

Ezen a ponton az algoritmus szerzője hivatkozik saját kísérleteire, amelyek azt mutatták, hogy az (1) pont sérül, ha minrun > 256, a (2) pont sérül, ha minrun < 8, és a leghatékonyabb az értékek használata. a tartomány (32;65). Ez alól kivétel, ha N < 64, akkor minrun = N és a timsort egyszerű beszúrásos rendezés lesz. Jelenleg a minrun kiszámításának algoritmusa rendkívül egyszerű: N-ből a legmagasabb 6 bitet veszik, és egyet hozzáadnak, ha a fennmaradó legkisebb jelentőségű bitekben legalább egy nem nulla van. Pszeudokód:

Jáva

public static int getMinrun ( int n ) { // egyenlő 1-gyel, ha az eltolt bitek között van legalább egy nem nulla int r = 0 ; while ( n >= 64 ) { r |= ( n & 1 ); n >>= 1 ; } return n + r ; }

1. lépés: Felosztás résztáblákra és rendezésük.

Az aktuális elem mutatója a bemeneti tömb elejére kerül.
Az aktuális elemtől kezdve ebben a tömbben keresi a rendezett altömb futtatását. A definíció szerint a futtatás egyedileg tartalmazza az aktuális és az azt követő elemet. Ha az eredményül kapott altömb csökkenő sorrendben van rendezve, akkor az elemek átrendeződnek úgy, hogy növekvő sorrendben menjenek.
Ha az aktuális futás mérete kisebb, mint a minrun, akkor a talált futást követő elemek a minrun-size (run) értékben kerülnek kiválasztásra. Így a kimenet egy minrun vagy nagyobb méretű altömb lesz, amelynek egy része (és ideális esetben az egész) rendezett.
A beillesztési rendezés erre az altömbre vonatkozik. Mivel az alrendszer mérete kicsi, és egy része már megrendelt, a válogatás gyors és hatékony.
Az aktuális elem mutatója az altömb utáni elemre kerül.
Ha nem éri el a bemeneti tömb végét, folytassa a 2. lépéssel, ellenkező esetben fejezze be ezt a lépést.

2. lépés: Egyesítés.

Ha a bemeneti tömb adatai közel voltak a véletlenszerűséghez, akkor a rendezett altömbök mérete közel van a minrun-hoz, ha az adatok rendezett tartományokat tartalmaztak, akkor a rendezett altömbök mérete nagyobb, mint a minrun.

Ezeket az altömböket egyesítenünk kell, hogy megkapjuk az eredményül kapott, teljesen rendezett tömböt. Ahhoz, hogy az egyesület hatékony legyen, két követelménynek kell megfelelnie:

Egyesítse a nagyjából azonos méretű altömböket
Tartsa fenn az algoritmus stabilitását – azaz ne csináljon értelmetlen permutációkat.

Algoritmus:

Létrejön egy üres halom <subarray start index>-<subarray size> párokból. Az első rendezett altömb kerül felvételre.
Az aktuális altömbhöz tartozó <start index>-<size> adatpár hozzáadódik a veremhez.
Meg kell határozni, hogy szükséges-e az aktuális altömb összevonása a korábbiakkal. Ehhez két szabályt ellenőriz (legyen X, Y és Z a verem legfelső három altömbjének mérete):

Z > Y + X Y > X

Ha valamelyik szabályt megsértjük, az Y tömb összevonódik az X és Z tömbök közül a kisebbikkel, és addig ismétli, amíg mindkét szabály teljesül, vagy az adatok teljesen rendeződnek.
Ha még mindig vannak figyelmen kívül hagyott altömbök, akkor a következőt veszi, és folytassa a 2. lépéssel. Ellenkező esetben a vége.

Ennek az eljárásnak a célja az egyensúly fenntartása. A változtatások úgy fognak kinézni, mint a jobb oldali képen, ami azt jelenti, hogy a veremben lévő altáblák méretei megfelelőek a további egyesítéshez. Ideális esetben: vannak 128, 64, 32, 16, 8, 4, 2, 2 méretű altömbök. Ebben az esetben az utolsó 2 altömb össze nem éréséig nem történik összevonás, majd 7 tökéletesen kiegyensúlyozott egyesítés jön létre. teljesített.

Az altömbök egyesítésének eljárása

Az összevonási eljárás az altömbök elrendezésétől függően halad és hasonlít össze, ezért az algoritmus balról jobbra (ha a kisebb tömb a bal oldalon van) és jobbról balra (ha a kisebb tömb a jobb oldalon van) bejárást igényel. A gyakorlatban általában az első eljárásra szorítkozunk, és a bal oldali tömböt választjuk ki, annak méretétől függetlenül - ennek szinte nincs hatása a rendezés sebességére.

Egy ideiglenes tömb jön létre az egyesített altömbök közül a kisebbik méretében.
Az altömbök közül a kisebbik átmásolásra kerül egy ideiglenes tömbbe
Az aktuális pozícióra mutató mutatók egy nagyobb és ideiglenes tömb első (utolsó) elemeire kerülnek.
Minden következő lépésnél figyelembe veszik a nagyobb és ideiglenes tömbök aktuális elemeinek értékét, közülük a kisebbet (nagyobbat) veszik és egy új rendezett tömbbe másolják. Az aktuális elem mutatója abba a tömbbe kerül, amelyből az elemet vettük.
A 4. lépést addig ismételjük, amíg az egyik tömb véget nem ér.
A fennmaradó tömb összes eleme hozzáadódik az új tömb végéhez.

Az altáblák egyesítési eljárásának módosítása (Galloping Mode)

Képzelje el a következő tömbök egyesítésének eljárását:

A = {1, 2, 3,..., 9999, 10000} B = { 20000, 20001, ...., 29999, 30000}

A fenti eljárás működik náluk, de a negyedik lépésnél minden alkalommal egy összehasonlítást és egy másolatot kell végrehajtania. Ennek eredményeként 10 000 összehasonlítás és 10 000 másolat. Timsort algoritmusa ezen a ponton kínál egy módosítást, amit „gallopnak” nevez. Algoritmus:

Megkezdődik az egyesítési eljárás, amint az fent látható.
Minden egyes művelet során, amikor egy elemet egy ideiglenes vagy nagyobb altömbből az eredményül kapottba másol, a rendszer megjegyzi, hogy az elem melyik altömbből származik.
Ha ugyanabból a tömbből bizonyos számú elemet (az algoritmus ezen megvalósításában ez a szám 7) már vettünk, akkor feltételezzük, hogy továbbra is abból veszünk adatokat. Ennek az elképzelésnek a megerősítésére az algoritmus „gallop” módba lép, vagyis a másodiktól kezdődően az aktuális elem bináris keresésével (a tömb rendezett) átmegy a jelölt tömbön, hogy a következő nagy adatmennyiséget biztosítsa. tömböt kell csatlakozni.
Abban a pillanatban, amikor az aktuális szolgáltatói tömbből származó adatok már nem megfelelőek (vagy a tömb végéhez értünk), az adatok teljes egészében másolásra kerülnek.

Vágta mód például:

Forrástömbök: A = {1, 2, 3,..., 9999, 10000} B = { 20000, 20001, ...., 29999, 30000}

Az első 7 iteráció az A tömb 1, 2, 3, 4, 5, 6 és 7-es számát hasonlítja össze a 20000-es számmal, mivel a 20000 nagyobb - az A tömb elemei átmásolódnak a kapott tömbbe. A következő iterációtól kezdve az algoritmus „gallop” módba kapcsol: szekvenciálisan összehasonlítja az A tömb 8, 10, 14, 22, 38, n+2^i, …, 10000 elemeit 20000 számmal (~log2 N összehasonlítások). Miután elértük az A tömb végét, és tudjuk, hogy ez mind kisebb, mint B, az A tömb szükséges adatait átmásoljuk a kapott tömbbe.

Jegyzetek

↑ Helytelen rendezési funkció Android, Rust, Java és Python esetén . "Hacker". Letöltve: 2015. december 5. Az eredetiből archiválva : 2015. december 8.. (határozatlan)
↑ jjb Commit 6804124: Cserélje ki a "módosított mergesort" szót a java.util.Arrays.sort fájlban a timsort kifejezésre . Java Development Kit 7 Hg repo . Letöltve: 2011. február 24. Az eredetiből archiválva : 2012. szeptember 4.. (határozatlan)
↑ Apple Swift Sort . GitHub . Letöltve: 2021. május 5. Az eredetiből archiválva : 2021. június 24.
↑ Osztály: java.util.TimSort<T> . Android JDK 1.5 dokumentáció . Letöltve: 2011. február 24. Az eredetiből archiválva : 2012. szeptember 4.. (határozatlan)
↑ Hetland, 2010 .

Irodalom

Peter McIlroy "Optimistic Sorting and Information Theoretic Complexity", Proceedings of the Fourth Annual Annual ACM-SIAM Symposium on Discrete Algorithms, ISBN 0-89871-313-7 , 53. fejezet, 467-474. oldal, 1993. január [1] .
Magnus Lie Hetland. Python-algoritmusok: Alapvető algoritmusok elsajátítása a Python nyelvben. - Apress, 2010. - 336 p. - ISBN 978-1-4302-3237-7 .

Linkek

Az algoritmus ábrázolása a készítőjétől (eng.) . Az eredetiből archiválva: 2012. szeptember 4.
A Timsort Pythonban implementálva PyPy számára ( py). Az eredetiből archiválva: 2012. szeptember 4.
Algoritmus vizualizáció (eng.) . Az eredetiből archiválva: 2012. szeptember 4.

Rendezési algoritmusok
Elmélet	Bonyolultság O jelölés Rendelési viszony Típusok rendezése fenntartható Belső Külső
Csere	buborék Keverés Törpék Gyors Fésű Rendezés páros-páratlan Bitenként
Választás	Választás Piramis alakú Sima
Betétek	Betétek shella fa
egyesülés	egyesülés
Nincs összehasonlítás	Számolás Blokk
hibrid	introsort Timsort
Egyéb	Topológiai hálózatok biton
nem praktikus	Bogosort Stooge fajta palacsinta lassú