A Timsort megértése
a rendezési algoritmusok az alapvetően szükséges és mélyen vitatott algoritmusok kínos kombinációja. Az új mérnököktől, akik lenyűgözni akarnak egy interjúban, az idősebb mérnökökig, akik megoldást keresnek a gyorsan méretező adatbázisra, számtalan tényezőt kell figyelembe venni. Mi a két objektum összehasonlításának sebessége? Mennyi a csere ideje? Mekkora az adatbázis? Milyen típusú tárgyakat tartalmaz? Már félig rendezve van? Az eredményeknek stabilnak kell lenniük?
e kérdések mindegyike érveket vonhat le az egyik vagy másik algoritmus mellett. A forrásadatok nagyok és összetettek? A legtöbb nyelv alapértelmezés szerint a standard, gyors rendezés az o (n log n) idő bonyolultságával. Kisebb? A beillesztés Rendezés csodákat tesz ezeken. Többnyire rendezve? Heck, buborék Sort lehet, hogy majdnem működik, hogy. Ha el szeretné olvasni/megjeleníteni az egyes érdemeket, nézze meg ezt az összehasonlítást toptal.com.
az egyik rendezési algoritmus, amelyet nem talál az oldalon, vagy szinte bármely más, A Tim Sort. Ez a homályos rendezés jelenleg egyedülálló a Python számára, és alapértelmezett rendezési algoritmusként használják. Hívás array.sort Pythonban, és a Tim Sort lesz végrehajtva. Ennek ellenére ritka olyan mérnököket találni, akik mind ismerik, mind megértik Tim Sort. Tehát: mi ez?
A Tim Sort először 2002-ben valósította meg Tim Peters Pythonban való használatra. Állítólag abból a megértésből származott, hogy a legtöbb rendezési algoritmus az iskolateremben születik, és nem a valós adatok gyakorlati felhasználására tervezték. A Tim Sort kihasználja az adatok általános mintáit, és az Egyesítési rendezés és a beillesztési Rendezés kombinációját használja néhány belső logikával együtt a nagy léptékű adatok manipulálásának optimalizálására.
miért Tim rendezés?
a 2.ábrát nézve azonnal láthatunk valami érdekeset. A legjobb esetben a Tim Sort felülmúlja a Merge Sort és a Quick Sort. A legrosszabb esetben összehasonlítható sebességgel fut egyesítés rendezés és valójában felülmúlja a gyors rendezést. Más szavakkal, váratlanul gyors.
a tér szempontjából a Tim rendezés a spektrum rosszabb végén van, de a legtöbb rendezési algoritmus esetében a tér figyelembevétele meglehetősen ritka. Az O (n) A legtöbb esetben nem túl durva; érdemes megjegyezni, mint lehetséges hiányosságot, és az egyetlen helyet, ahol a gyors rendezés valóban felülmúlja a Tim Sort.
az utolsó elem, amelyet a rendezési algoritmusok gyakran megítélnek, a stabilitás. A stabilitás az a koncepció, hogy rendezve az azonos értékű tárgyak megtartják eredeti sorrendjüket. Most, lehet, hogy kíváncsi, miért érdekel ez minket. A termékek azonos értékűek — miért bánjuk, hogyan rendelik őket?
az egyszerű válasz az, hogy a stabilitás számít halmozott fajta. Vagyis először egy kritérium alapján rendez, majd egy második alapján. Ha ezt instabil algoritmusban végzi, akkor a második futtatásakor azonnal elveszíti az első Rendezés megbízhatóságát. Referenciaként a gyors rendezés instabil, az egyesítés Rendezés pedig stabil.
A Tim Sort szintén stabil, nem is beszélve a gyors, ha kissé nehézsúlyú(csak a gyors rendezéshez képest). Míg a rendezési algoritmusokat más szempontok alapján lehet (és kell) megítélni, ezek a három nagy.
A megvalósítás három lépésben
A Tim Rendezés összetett, még algoritmikus szabványok szerint is. A megvalósítást legjobban részekre lehet bontani.
bináris keresés
Az első dolog, amire szüksége van a Tim Rendezés megvalósításához, egy bináris keresési módszer. Ezt csak a beillesztési Rendezés későbbi végrehajtására használják.
referenciaként: bináris keresési algoritmusok
Insertion Sort & Merge Sort
másodszor, be kell kódolni az Insertion Sort és az Merge Sort. Ezek ismerős algoritmusok, és a legtöbb mérnök hátsó zsebében kell lenniük, de áttekintjük a működésük alapjait, és miért értékesek számunkra itt.
3.ábra: Insertionsort (a https://www.geeksforgeeks.org/insertion-sort/)
a beillesztés rendezése egy nagyon egyszerű rendezési algoritmus. Végigfut a tömbön, és amikor olyan elemet talál, amely nem megfelelő (szigorúan kevesebb/több, mint az előtte lévő elem), áthelyezi a megfelelő helyre a már rendezett tömbben. A beillesztési Rendezés hírhedt arról, hogy nagyon gyorsan dolgozik a már rendezett tömbökön, valamint a kisebb tömbökön. Valójában a 2. ábrán láthatjuk, hogy a beillesztési Rendezés lenyűgöző o(n) futási idővel rendelkezik. Ne feledje, halad előre Tim Sort: legjobb esetben a Beszúrás Rendezés egy már rendezett tömb. Lehet, hogy hülyén hangzik, de ez releváns lesz.
Merge Sort másrészt működik egy alapelv: ez rendkívül könnyű egyesíteni már rendezett tömbök. Tehát egy kezdő tömböt újra és újra kettéválaszt, amíg nem lesz más, mint egyetlen elem. Ezután lassan újjáépíti a fő tömb összevonásával ezeket az elemeket újra együtt rendezett sorrendben. Mivel az első méretű építőelemekből indultunk ki, nagyon könnyű volt kezdeti rendezett tömböket építeni. Ezután könnyű egyesíteni őket. Végül O (n log n) időt töltünk, és (fontos) ezt olyan módon tesszük, amely garantáltan stabil.
például megvalósítások lásd:
egyesítés Rendezés: https://www.geeksforgeeks.org/merge-sort/
Beszúrási Rendezés: https://www.geeksforgeeks.org/insertion-sort/
végrehajtása Tim Rendezés
a legfontosabb, hogy megértsük a Tim Sort végrehajtását megértése használata fut. A Tim Sort a természetben előforduló előre válogatott adatokat használja ki előnyére. Előre rendezve egyszerűen azt értjük, hogy a szekvenciális elemek mind növekednek vagy csökkennek (nem érdekel, melyik).
először állítsunk be egyminrun méretet. Ez alatt azt értjük, hogy biztosítani akarjuk, hogy minden futásunk legalább egy bizonyos hosszúságú legyen. Felhívjuk figyelmét, hogy nem garantáljuk, hogy találunk ilyen méretű futásokat — később belemegyünk ebbe. Egyszerűen azt mondjuk, hogy a futásnak legalább egy bizonyos hosszúságúnak kell lennie.
amikor futással találkozunk, félretesszük. Amikor megtaláljuk a leghosszabb futást egy minrun tartományon belül. Most már van egy ismerős adatstruktúránk: egy kicsi, rendezett tömb. Ha legalább minrun hosszúságú, akkor hurrá! Tovább léphetünk. Ha nem, akkor beillesztjük a beillesztési Sort.
fentről emlékezhetsz arra, hogy a Beillesztés rendezése különösen hatékony kétféle tömbön: a kicsieken és a már rendezett tömbökön. Amit most készítettünk, az egy kicsi, rendezett tömb. Ha nem legalább minrun hosszúságú, akkor előre nyúlunk, és megragadunk elég más elemet a Futtatás befejezéséhez, majd az Insertion Sort segítségével gyorsan és egyszerűen betoljuk őket a rendezett tömbünkbe. Nyilvánvaló, hogy ha egy futás találkozik a tömb végével, akkor hagyja, hogy egy kicsit rövid legyen.
miután létrehozta az összes fut (azaz rendezett subarrays), akkor használja a Merge Sort, hogy csatlakozzon hozzájuk. A legjobb esetben a teljes tömb már rendezve van, és Tim Sort elég okos ahhoz, hogy tudja, hogy nem kell mást tennie. Más idők, általában csak rendkívül hatékony. További előnyként mind a beszúrási rendezés, mind az Egyesítési Rendezés stabil, tehát a kapott tömb stabil.
azok számára, akik kedvelik a golyókat:
- hozzon létre egy
minrunméret, amely 2 teljesítmény (általában 32, soha nem több, mint 64, vagy a beillesztési Rendezés elveszíti hatékonyságát) - keressen egy futást az első
minrunadatokban. - Ha a Futtatás hossza nem éri el a
minrunhosszúságot, akkor az Insertion Sort (Beszúrás Rendezés) használatával ragadja meg a következő vagy az előző elemeket, és illessze be őket a futásba, amíg a megfelelő minimális méret nem lesz. - ismételje meg, amíg a teljes tömb rendezett alszakaszokra nem oszlik.
- használja az egyesítés Rendezés második felét a rendezett tömbök összekapcsolásához.
következtetés
Tim Sort erős. Gyors és stabil, de talán a legfontosabb, hogy kihasználja a valós mintákat, és felhasználja őket a végtermék elkészítéséhez. Ez minden helyzetben? Valószínűleg nem. Sok szerencsét programozása egy táblára egy interjú során, és ha csak szüksége van egy gyors egyszerű rendezési algoritmus egy csipetnyi akkor valószínűleg nem akar bajlódni végrehajtási valami ez a komplex. Azonban az adatok tudósok ropogó számok ez több mint érdemes egy pillantást.
a kíváncsi, akkor nézd meg a teljes Tim Sort kódot github.
köszönöm
Köszönöm mindenkinek az olvasóimnak. Nagyra értékelem az idejét, és őszintén remélem, hogy informatívnak találta a tartalmat. Ha bármilyen kérdése vagy válasza van, nyugodtan dobjon egyet alább.