forståelse Timsort
sorteringsalgoritmer er en akavet kombination af fundamentalt nødvendige og dybt omstridte. Fra nye ingeniører, der ønsker at imponere i en samtale til ældre ingeniører, der søger en løsning på en hurtig skaleringsdatabase, der er utallige faktorer, der skal tages i betragtning. Hvad er sammenligningshastigheden mellem to objekter? Hvad er byttetiden? Hvor stor er databasen? Hvilken type objekter indeholder den? Er det allerede semi-sorteret? Skal resultaterne være stabile?
hvert af disse spørgsmål kan trække argumenter til fordel for en eller anden algoritme. Er kildedataene store og komplekse? De fleste sprog er standard til standard, hurtig sortering med dens o( n log n) tidskompleksitet. Er den mindre? Indsættelse Sort virker vidundere på dem. Mest sorteret? Heck, Bubble Sort kan næsten arbejde for det. Hvis du vil læse/visualisere fordelene ved hver, skal du tjekke denne sammenligning ved toptal.com.
en sorteringsalgoritme, du ikke finder på det sted, eller næsten enhver anden, er Tim Sort. Denne obskure slags er i øjeblikket unik for Python og bruges som standard sorteringsalgoritme. Ring array.sort i Python, og Tim Sort er, hvad der bliver henrettet. På trods af dette er det sjældent at finde ingeniører, der både kender og forstår Tim Sort. Så: hvad er det?
Tim Sort blev først implementeret i 2002 af Tim Peters til brug i Python. Det kom angiveligt fra forståelsen af, at de fleste sorteringsalgoritmer er født i skolelokaler og ikke designet til praktisk brug på data fra den virkelige verden. Tim Sort drager fordel af almindelige mønstre i data og bruger en kombination af Fletningssortering og Indsætningssortering sammen med en vis intern logik for at optimere manipulationen af data i stor skala.
hvorfor Tim sortere?
Når vi ser på figur 2, kan vi straks se noget interessant. På sit bedste, Tim sortere udkonkurrerer Fusionssortering og hurtig sortering. I værste fald kører den med sammenlignelig Hastighedsfletningssortering og overgår faktisk hurtig sortering. Med andre ord er det uventet hurtigt.
med hensyn til plads er Tim Sort på den værre ende af spektret, men rumovervejelsen for de fleste sorteringsalgoritmer er ret sparsom. O (n) er ikke for groft i de fleste tilfælde; Det er værd at bemærke som en mulig mangel, og det ene sted, hvor hurtig sortering virkelig overgår Tim Sort.
det sidste element, som sorteringsalgoritmer ofte bedømmes på, er stabilitet. Stabilitet er konceptet, at når de sorteres, opretholder objekter af samme værdi deres oprindelige rækkefølge. Nu undrer du dig måske over, hvorfor vi bryr os om det. Varerne er af samme værdi — hvorfor har vi noget imod, hvordan de bestilles?
det enkle svar er, at stabilitet betyder noget for stablede Sorter. Det vil sige, du sorterer først ud fra et kriterium, derefter baseret på et andet. Hvis du gør dette i en ustabil algoritme, mister du øjeblikkeligt enhver pålidelighed fra din første sortering, når du kører den anden. Som reference er hurtig sortering ustabil, og Fletningssortering er stabil.
Tim Sort er også stabil, for ikke at nævne hurtig, hvis lidt tungvægt(i sammenligning med kun hurtig sortering). Mens sorteringsalgoritmer kan (og bør) bedømmes ud fra andre overvejelser, er disse de tre store.
implementeringen i tre trin
Tim sortering er kompleks, selv efter algoritmiske standarder. Implementeringen er bedst opdelt i dele.
binær søgning
den første ting, du har brug for for at implementere en Tim-sortering, er en binær søgemetode. Dette bruges bare til at implementere din indsættelsessortering senere.
til reference: binære søgealgoritmer
Indsætningssortering & Flet sortering
for det andet skal du kode Indsætningssortering og flette sortering. Disse er velkendte algoritmer, og bør være i baglommen hos de fleste ingeniører, men vi vil gå over de grundlæggende elementer i, hvordan de fungerer, og hvorfor de er værdifulde for os her.
indsætningssortering er en meget grundlæggende sorteringsalgoritme. Det løber gennem arrayet, og når det støder på en vare, der er ude af drift (strengt mindre/mere end varen før den), flytter den den til den rette position i det allerede sorterede array. Indsætningssortering er berygtet for at arbejde meget hurtigt på allerede sorterede arrays såvel som mindre arrays. Faktisk kan vi se fra Fig 2, at indsættelsessortering har en imponerende best case run time of o (n). Husk at gå videre med Tim Sort: bedste tilfælde til Indsætningssortering er et allerede sorteret array. Det lyder måske fjollet, men det vil være relevant.
Flet sortering fungerer på den anden side efter et grundlæggende princip: det er meget let at flette allerede sorterede arrays. Så, det opdeler en start array i halve igen og igen, indtil det er intet andet end enkelte elementer. Derefter genopbygger den langsomt hovedarrayet ved at flette disse elementer sammen igen i sorteret rækkefølge. Fordi vi startede fra byggesten i størrelse en, var det meget let at bygge indledende sorterede arrays. Derefter er det let at flette dem. I sidste ende bruger vi O(n log n) tid, og (vigtigere) gør vi det på en måde, der garanteres at være stabil.
for eksempel implementeringer se:
Flet sortering:https://www.geeksforgeeks.org/merge-sort/
Indsætningssortering:https://www.geeksforgeeks.org/insertion-sort/
Implementer Tim Sort
nøglen til at forstå Tim sorteres implementering er at forstå brugen af kørsler. Tim Sort udnytter naturligt forekommende presorted data til sin fordel. Ved presorted mener vi simpelthen, at sekventielle elementer er alle stigende eller faldende (vi er ligeglad med hvilke).
først indstiller vi enminrun størrelse. Hvad vi mener med dette er, at vi ønsker at sikre, at alle vores kørsler er mindst en vis længde. Bemærk, at vi ikke garanterer, at vi finder kørsler af denne størrelse — vi kommer ind på dette senere. Vi siger simpelthen, at et løb skal være mindst af en vis længde.
når vi støder på et løb, sætter vi det til side. Når vi finder det længste løb inden for et minrun rækkevidde. Vi har nu en velkendt datastruktur: et lille, sorteret array. Hvis det er mindst minrun i længden, så huvah! Vi er gode til at komme videre. Hvis det ikke er tilfældet, sætter vi indsættelsessortering i spil.
Du kan huske ovenfra, at indsættelsessortering er særlig effektiv på to typer arrays: små og allerede sorterede. Det, vi lige har lavet, er et lille, sorteret array. Hvis det ikke er mindst minrun i længden, når vi frem og tager nok andre elementer til at fuldføre løbet, og brug derefter Indsætningssortering til at skubbe dem ind i vores sorterede array, hurtigt og nemt. Selvfølgelig, hvis et løb møder slutningen af arrayet, kan du lade det være lidt kort.
når du har oprettet alle dine kørsler (dvs.sorterede subarrays), bruger du din Fletningssortering til at slutte dem sammen. I bedste fald er hele arrayet allerede sorteret, og Tim Sort er smart nok til at vide, at det ikke behøver at gøre noget andet. Andre gange har det en tendens til bare at være ekstremt effektivt. Som en ekstra fordel er både Indsætningssortering og Fletningssortering stabile, så det resulterende array er stabilt.
for dem, der foretrækker kugler:
- Opret en
minrunstørrelse, der er en effekt på 2 (normalt 32, aldrig mere end 64, eller din indsættelsessortering mister effektivitet) - Find et løb i den første
minrunaf data. - hvis løbet ikke er mindst
minruni længden, skal du bruge Indsætningssortering til at gribe efterfølgende eller tidligere emner og indsætte dem i løbet, indtil det er den korrekte minimumsstørrelse. - gentag, indtil hele arrayet er opdelt i sorterede underafsnit.
- Brug den sidste halvdel af Fletningssortering til at deltage i de bestilte arrays.
konklusion
Tim Sort er kraftfuld. Det er hurtigt og stabilt, men måske vigtigst det udnytter virkelige verden mønstre og udnytter dem til at bygge et slutprodukt. Er det til enhver situation? Sikkert ikke. Held og lykke med at programmere det på en tavle under en samtale, og hvis du bare har brug for en hurtig enkel sorteringsalgoritme i en knivspids, vil du sandsynligvis ikke gider at implementere noget dette kompleks. Men for dataforskere, der knuser tal, er det mere end et kig værd.
for de nysgerrige kan du tjekke hele Tim Sorteringskoden på github.
Tak
tak en og alle til mine læsere. Jeg sætter pris på din tid, og håber inderligt, at du fandt indholdet informativt. Hvis du har spørgsmål eller svar, er du velkommen til at droppe et nedenfor.