lajittelualgoritmit ovat kiusallinen yhdistelmä pohjimmiltaan välttämätöntä ja syvästi kiistanalaista. Uusista insinööreistä, jotka haluavat tehdä vaikutuksen haastattelussa vanhempiin insinööreihin, jotka etsivät ratkaisua nopeasti skaalautuvaan tietokantaan, on lukemattomia tekijöitä, jotka on otettava huomioon. Mikä on kahden kohteen välisen vertailun nopeus? Paljonko vaihtoaika on? Kuinka suuri tietokanta on? Millaisia esineitä se sisältää? Onko se jo puoliksi lajiteltu? Pitääkö tulosten olla vakaita?

jokainen näistä kysymyksistä voi esittää argumentteja jonkin algoritmin puolesta. Onko lähdeaineisto suuri ja monimutkainen? Useimmat kielet oletuksena standardin, nopea lajitella sen O (n log n) aika monimutkaisuus. Onko se pienempi? Insertion Sort tekee ihmeitä niille. Enimmäkseen hoidettu? Kupla voisi melkein toimia siihen. Jos haluat lukea / visualisoida kunkin ansiot, tutustu tähän vertailuun toptal.com.

yksi lajittelualgoritmi, jota et löydä kyseiseltä sivustolta, tai melkein mikään muukaan, on Tim Sort. Tämä epämääräinen lajittelulaji on tällä hetkellä ainutlaatuinen Pythonille, ja sitä käytetään sen oletuslajittelualgoritmina. Soita array.sort Python-kielellä, ja Tim Sort saa suorituksen. Tästä huolimatta on harvinaista löytää insinöörejä, jotka sekä tuntevat että ymmärtävät Tim sortin. Mikä se on?

Tim sortin toteutti ensimmäisen kerran vuonna 2002 Tim Peters käytettäväksi Pythonissa. Sen väitetään syntyneen ymmärryksestä, että suurin osa lajittelualgoritmeista syntyy koululuokissa, eikä niitä ole suunniteltu käytännön käyttöön reaalimaailman datassa. Tim Sort hyödyntää yleisiä kaavoja datassa ja käyttää yhdistämisen lajittelun ja lisäyksen lajittelun yhdistelmää yhdessä jonkin sisäisen logiikan kanssa optimoidakseen suuren mittakaavan tietojen manipuloinnin.

miksi Tim lajittelee?

kun katsoo kuvaa 2, voi heti nähdä jotain mielenkiintoista. Parhaimmillaan Tim lajitella outperforms yhdistää lajitella ja nopea lajitella. Pahimmillaan se toimii vertailukelpoisella nopeudella Merge Lajittele ja itse asiassa päihittää nopean lajittelun. Toisin sanoen se on odottamattoman nopea.

avaruuden suhteen Tim Sort on spektrin huonommassa päässä, mutta useimpien lajittelualgoritmien tilavastike on melko niukka. O (n) ei ole liian karkea useimmissa tapauksissa; se on syytä huomata mahdollisena puute, ja yksi paikka, jossa nopea lajitella todella outshines Tim lajitella.

lopullinen kohde, jonka perusteella lajittelualgoritmeja usein arvioidaan, on stabiilisuus. Stabiilisuus on käsite, jonka mukaan lajiteltaessa samanarvoiset esineet säilyttävät alkuperäisen järjestyksensä. Saatat ihmetellä, miksi välitämme siitä. Tavarat ovat samanarvoisia-miksi välitämme siitä, miten ne on järjestetty?

yksinkertainen vastaus on, että stabiilisuudella on väliä pinotuille lajeille. Toisin sanoen lajitellaan ensin yhden kriteerin perusteella, sitten toisen kriteerin perusteella. Jos teet tämän epävakaalla algoritmilla, menetät välittömästi luotettavuuden ensimmäisestä lajistasi, kun suoritat toisen. Viitteenä, nopea lajittelu on epävakaa, ja Merge lajittelu on vakaa.

Tim Sort on myös vakaa, puhumattakaan nopeasta joskin hieman raskaasta(verrattuna vain nopeaan Sortiin). Vaikka lajittelualgoritmeja voidaan (ja pitäisi) arvioida muiden näkökohtien perusteella, nämä ovat kolme suurta.

toteutus kolmessa vaiheessa

Tim-lajittelu on monimutkaista, jopa algoritmisin standardein. Toteutus on parasta jakaa osiin.

Binäärihaku

ensimmäinen asia, jonka tarvitset Tim-lajittelun toteuttamiseksi, on binäärinen hakumenetelmä. Tätä käytetään vain Lisäyslajin toteuttamiseen myöhemmin.

viite: binääriset hakualgoritmit

Lisäyslajittelu & Merge Sort

toiseksi, sinun täytyy koodata Lisäyslajittelu ja Merge Sort. Nämä ovat tuttuja algoritmeja, ja niiden pitäisi olla useimpien insinöörien takataskussa, mutta käymme läpi perusasiat siitä, miten ne toimivat ja miksi ne ovat meille arvokkaita täällä.

insertiolaji on hyvin alkeellinen lajittelualgoritmi. Se kulkee array, ja aina kun se kohtaa kohde, joka on epäkunnossa (ehdottomasti vähemmän/enemmän kuin kohde ennen sitä), se siirtää sen sopivaan asentoon jo lajiteltu array. Insertion Sort on tunnettu siitä, että se työskentelee hyvin nopeasti jo lajiteltujen ryhmien sekä pienempien ryhmien parissa. Itse asiassa, voimme nähdä kuva 2, että lisäys lajitella on vaikuttava paras tapaus ajaa aika O (n). Pidä mielessä eteenpäin Tim Sort: paras tapaus Insertion Sort on jo lajiteltu array. Se voi kuulostaa typerältä, mutta sillä on merkitystä.

merge Sort puolestaan toimii perusperiaatteella: jo lajiteltujen ryhmien yhdistäminen on tavattoman helppoa. Niin, se jakaa alkujoukko kahtia uudelleen ja uudelleen, kunnes se ei ole mitään muuta kuin yksittäisiä elementtejä. Sitten se hitaasti rakentaa pääjoukon uudelleen yhdistämällä ne elementit takaisin yhteen lajiteltuun järjestykseen. Koska aloitimme yhden kokoisista rakennuspalikoista, alustavien lajiteltujen taulukoiden rakentaminen oli erittäin helppoa. Sitten niitä on helppo yhdistää. Lopulta käytämme O (n log n) aikaa, ja (mikä tärkeintä) teemme sen tavalla, joka on taattu vakaaksi.

esimerkiksi toteutukset katso:

Merge Sort: https://www.geeksforgeeks.org/merge-sort/

Insertion Sort: https://www.geeksforgeeks.org/insertion-sort/

Implement Tim Sort

avain Tim sortin toteutuksen ymmärtämiseen on sen ajojen käytön ymmärtäminen. Tim lajitella vivut luonnossa esiintyviä presorted tietoja sen eduksi. By presorted me yksinkertaisesti tarkoittaa, että peräkkäiset elementit ovat kaikki kasvaa tai vähenee (emme välitä, joka).

ensin asetettiin minrun koko. Tällä tarkoitetaan sitä, että haluamme varmistaa, että kaikki juoksumme ovat vähintään tietyn mittaisia. Huomaa, että emme takaa, että löydämme tämän kokoluokan juoksuja — palaamme asiaan myöhemmin. Sanomme vain, että juoksun pitää olla vähintään tietyn mittainen.

kun törmäämme juoksuun, laitamme sen sivuun. Kun löydämme pisin run sisällä minrun alue. Meillä on nyt tuttu tietorakenne: pieni, lajiteltu joukko. Jos se on vähintään minrun pituudeltaan, niin huzzah! Voimme jatkaa eteenpäin. Jos se ei ole, laitamme Lisäyslajin peliin.

saatat muistaa ylhäältä, että Lisäyslajittelu on erityisen tehokas kahdentyyppisissä ryhmissä: pienissä ja jo lajitelluissa. Teimme juuri pienen, lajitellun joukon. Jos se ei ole vähintään minrun pituudeltaan, me kurkotamme eteenpäin ja nappaamme tarpeeksi muita elementtejä suorittaaksemme ajon, sitten työnnä ne Insertion Sort-ohjelmalla lajiteltuun riviimme, nopeasti ja helposti. On selvää, että jos ajaa kohtaa lopussa array voit antaa sen olla hieman lyhyt.

kun olet luonut kaikki suorituksesi (eli lajitellut alaryhmät), käytät Yhdistämislajiasi liittääksesi ne yhteen. Parhaassa tapauksessa koko array on jo lajiteltu ja Tim lajitella on tarpeeksi fiksu tietää sen ei tarvitse tehdä mitään muuta. Muina aikoina, se on yleensä vain erittäin tehokas. Lisäetuna sekä lisäys-että Yhdistämislaji ovat vakaita, joten tuloksena oleva joukko on vakaa.

niille, jotka suosivat luoteja:

1. Vakiinnuta minrun koko, joka on potenssi 2 (yleensä 32, ei koskaan yli 64 tai Lisäyslajisi menettää tehokkuutensa)
2. Etsi juoksu ensimmäisestä minrun datasta.
3. Jos suoritus ei ole vähintään minrun pituudeltaan, käytä Insertion Sort-toimintoa napataksesi seuraavat tai aiemmat kohteet ja laittaaksesi ne ajoon, kunnes se on oikea vähimmäiskoko.
4. toistetaan, kunnes koko joukko on jaettu lajiteltuihin alaluokkiin.
5. käytä Merge sortin jälkimmäistä puoliskoa liittyäksesi järjestettyihin ryhmiin.

johtopäätös

Tim Sort on voimakas. Se on nopea ja vakaa, mutta ehkä tärkeintä se hyödyntää reaalimaailman kuvioita ja hyödyntää niitä lopputuotteen rakentamiseen. Onko se jokaiseen tilanteeseen? Luultavasti ei. Onnea ohjelmointi se tussitaululle haastattelun aikana, ja jos tarvitset vain nopea yksinkertainen lajittelu algoritmi hyppysellinen et luultavasti halua vaivautua toteuttamaan jotain näin monimutkaista. Kuitenkin, data tutkijat crunching numeroita se on enemmän kuin kannattaa katsoa.

uteliaille voi tarkistaa koko Tim Sort-koodin GitHubista.

Kiitos

kiitos yksi ja kaikki lukijoilleni. Arvostan aikaa, ja vilpittömästi toivon, että löysit sisältöä informatiivinen. Jos sinulla on kysyttävää tai vastauksia, voit pudottaa yhden alle.