streamalism.org

1. Oversikt

Kjøretidskompleksiteten til algoritmer er ofte avhengig av inngangens art.

I denne veiledningen får vi se hvordan triviell implementering av Quicksort-algoritmen har dårlig ytelse for gjentatte elementer.

Videre lærer vi noen få Quicksort-varianter for effektivt å partisjonere og sortere innganger med høy tetthet av dupliserte nøkler.

2. Trivial Quicksort

Quicksort er en effektiv sorteringsalgoritme basert på skillet og erobre paradigmet. Funksjonelt sett, det opererer på stedet på inngangssamlingen og omorganiserer elementene med enkle sammenlignings- og bytteoperasjoner.

2.1. Partisjonering med én pivot

En triviell implementering av Quicksort-algoritmen er sterkt avhengig av en enkelt-pivot partisjoneringsprosedyre. Med andre ord deler partisjonering matrisen A = [a_s, a_{p + 1}, a_{p + 2},…, A_r] i to deler A [p..q] og A [q + 1..r] slik at:

• Alle elementene i den første partisjonen, A [p..q] er mindre enn eller lik svingverdien A [q]
• Alle elementene i den andre partisjonen, A [q + 1..r] er større enn eller lik pivotverdien A [q]

Etter det blir de to partisjonene behandlet som uavhengige inngangsarrayer og matet seg til Quicksort-algoritmen. La oss se Lomutos kviksort i aksjon:

2.2. Ytelse med gjentatte elementer

La oss si at vi har en matrise A = [4, 4, 4, 4, 4, 4, 4] som har alle like elementer.

Ved partisjonering av denne matrisen med single-pivot partisjoneringsskjemaet, får vi to partisjoner. Den første partisjonen vil være tom, mens den andre partisjonen vil ha N-1-elementer. Lengre, hver påfølgende påkallelse av partisjonsprosedyren vil redusere inngangsstørrelsen med bare en. La oss se hvordan det fungerer:

Siden partisjonsprosedyren har lineær tidskompleksitet, er den totale tidskompleksiteten, i dette tilfellet, kvadratisk. Dette er det verste tilfellet for vårt inngangssett.

3. Treveis partisjonering

For å effektivt sortere en matrise med et høyt antall gjentatte taster, kan vi velge å håndtere like taster mer ansvarlig. Tanken er å plassere dem i riktig posisjon når vi først møter dem. Så det vi leter etter er en tre partisjonstilstand for matrisen:

• Partisjonen til venstre inneholder elementer som er strengt mindre enn partisjoneringsnøkkelen
• Demidtpartisjonen inneholder alle elementene som er lik partisjoneringsnøkkelen
• Partisjonen til høyre inneholder alle elementene som er strengt større enn partisjoneringsnøkkelen

Vi dykker nå dypere inn i et par tilnærminger som vi kan bruke for å oppnå treveis partisjonering.

4. Dijkstras tilnærming

Dijkstras tilnærming er en effektiv måte å gjøre treveis partisjonering på. For å forstå dette, la oss se på et klassisk programmeringsproblem.

4.1. Nederlandsk nasjonalflaggproblem

Inspirert av nederlands trefarget flagg, foreslo Edsger Dijkstra et programmeringsproblem kalt Dutch National Flag Problem (DNF).

I et nøtteskall er det et omleggingsproblem hvor vi får kuler i tre farger plassert tilfeldig i en linje, og vi blir bedt om å gruppere kulene med samme farge. Videre må omleggingen sikre at grupper følger riktig rekkefølge.

Interessant, DNF-problemet gjør en slående analogi med 3-veis partisjonering av en matrise med gjentatte elementer.

Vi kan kategorisere alle tallene i en matrise i tre grupper med hensyn til en gitt nøkkel:

• Den røde gruppen inneholder alle elementene som er strengt mindre enn nøkkelen
• Den hvite gruppen inneholder alle elementene som er like nøkkelen
• Den blå gruppen inneholder alle elementer som er strengt større enn nøkkelen

4.2. Algoritme

En av tilnærmingene for å løse DNF-problemet er å velge det første elementet som partisjoneringsnøkkel og skanne matrisen fra venstre til høyre. Når vi sjekker hvert element, flytter vi det til sin rette gruppe, nemlig Mindre, Lik og Større.

For å holde rede på partisjoneringsfremdriften vår, trenger vi hjelp fra tre pekere, nemlig lt, nåværende, og gt. Når som helst, elementene til venstre for lt vil være strengt mindre enn partisjoneringsnøkkelen, og elementene til høyre for gt vil være strengt større enn nøkkelen.

Videre bruker vi nåværende pekeren for skanning, noe som betyr at alle elementene ligger mellom nåværende og gt tips er ennå ikke utforsket:

Til å begynne med kan vi stille lt og nåværende pekere helt i begynnelsen av matrisen og gt pekeren helt på slutten av den:

For hvert element leses via nåværende pekeren, sammenligner vi den med partisjoneringsnøkkelen og tar en av de tre sammensatte handlingene:

• Hvis inngang [gjeldende] <-tast, så bytter vi inngang [gjeldende] og inngang [lt] og øk begge deler nåværende og lt pekere
• Hvis inngang [gjeldende] == nøkkel, så øker vi nåværende pekeren
• Hvis inngang [gjeldende]> tast, så bytter vi inngang [gjeldende] og inngang [gt] og dekrement gt

Etter hvert, vi stopper når nåværende og gt pekere krysser hverandre. Med det reduseres størrelsen på den uutforskede regionen til null, og vi sitter igjen med bare tre nødvendige partisjoner.

Til slutt, la oss se hvordan denne algoritmen fungerer på et inngangssett som har dupliserte elementer:

4.3. Gjennomføring

La oss først skrive en verktøyprosedyre som heter sammenligne() å gjøre en treveis sammenligning mellom to tall:

offentlig statisk int sammenligne (int num1, int num2) {if (num1> num2) return 1; annet hvis (num1 <num2) returnerer -1; ellers returnere 0; }

Deretter la oss legge til en metode som heter bytte() å utveksle elementer på to indekser i samme matrise:

public static void swap (int [] array, int position1, int position2) {if (position1! = position2) {int temp = array [position1]; array [position1] = array [posisjon2]; matrise [posisjon2] = temp; }}

For å identifisere en partisjon i matrisen unikt, trenger vi venstre og høyre grenseindeks. Så la oss gå videre og lage en Skillevegg klasse:

offentlig klasse Partisjon {privat int venstre; privat int rett; }

Nå er vi klare til å skrive vår treveis skillevegg() fremgangsmåte:

offentlig statisk partisjon partisjon (int [] input, int begin, int end) {int lt = begin, current = begin, gt = end; int partitioningValue = input [begin]; mens (gjeldende <= gt) {int CompareCurrent = Sammenlign (input [gjeldende], partitioningValue); switch (CompareCurrent) {case -1: swap (input, current ++, lt ++); gå i stykker; tilfelle 0: nåværende ++; gå i stykker; tilfelle 1: bytte (inngang, strøm, gt--); gå i stykker; }} returner ny partisjon (lt, gt); }

Til slutt, la oss skrive en kviksort () metode som utnytter vårt 3-veis partisjoneringsskjema for å sortere venstre og høyre partisjoner rekursivt:

offentlig statisk ugyldig kviksort (int [] input, int begin, int end) {if (end <= begin) return; Partition middlePartition = partisjon (input, start, slutt); quicksort (input, begin, middlePartition.getLeft () - 1); quicksort (input, middlePartition.getRight () + 1, end); }

5. Bentley-McIlroy's Approach

Jon Bentley og Douglas McIlroy var medforfatter av en optimalisert versjon av Quicksort-algoritmen. La oss forstå og implementere denne varianten i Java:

5.1. Partisjoneringsordning

Kjernen i algoritmen er en iterasjonsbasert partisjoneringsplan. I starten er hele tallmengden et uutforsket område for oss:

Vi begynner deretter å utforske elementene i matrisen fra venstre og høyre retning. Hver gang vi går inn i eller forlater utforskningssløyfen, vi kan visualisere matrisen som en sammensetning av fem regioner:

• På de ytterste to endene ligger regionene som har elementer som er lik partisjonsverdien
• Den uutforskede regionen forblir i sentrum, og størrelsen fortsetter å krympe for hver iterasjon
• Til venstre for den uutforskede regionen ligger alle elementene mindre enn partisjoneringsverdien
• På høyre side av den uutforskede regionen er elementer som er større enn partisjonsverdien

Til slutt avsluttes utforskingsløkken vår når det ikke er noen elementer å utforske lenger. På dette stadiet, størrelsen på den uutforskede regionen er faktisk null, og vi har bare fire regioner igjen:

Neste, vi flytte alle elementene fra de to like regionene i sentrum slik at det bare er en like region i sentrum som omgir den mindre regionen til venstre og større regionen til høyre. For å gjøre det, bytter vi først elementene i venstre like-region med elementene i høyre ende av mindre regionen. På samme måte byttes elementene i høyre like-region med elementene i venstre ende av større-regionen.

Endelig vil vi være det igjen med bare tre partisjoner, og vi kan videre bruke den samme tilnærmingen til å dele de mindre og større regionene.

5.2. Gjennomføring

I vår rekursive implementering av treveis Quicksort, må vi påkalle vår partisjonsprosedyre for underarrayer som har et annet sett med nedre og øvre grenser. Så, vår skillevegg() metoden må godta tre innganger, nemlig matrisen sammen med venstre og høyre grense.

offentlig statisk partisjonspartisjon (int input [], int begin, int end) {// returnerer partisjonsvindu}

For enkelhets skyld kan vi velg partisjonsverdien som det siste elementet i matrisen. La oss også definere to variabler venstre = begynn og høyre = slutt for å utforske matrisen innover.

Videre må vi også holde oversikt over antall like elementer som ligger på venstre og høyre side. Så la oss initialisere leftEqualKeysCount = 0 og rightEqualKeysCount = 0, og vi er nå klare til å utforske og partisjonere matrisen.

Først begynner vi å bevege oss fra begge retninger og finne en inversjon der et element til venstre ikke er mindre enn partisjonsverdi, og et element til høyre ikke er større enn partisjonsverdi. Deretter bytter vi de to elementene, med mindre de to pekerne venstre og høyre har krysset hverandre.

I hver iterasjon flytter vi elementer som er like partitioningValue mot de to endene og øk riktig teller:

while (true) {while (input [left] partitioningValue) {if (right == begin) break; Ikke sant--; } if (left == right && input [left] == ​​partitioningValue) {swap (input, begin + leftEqualKeysCount, left); leftEqualKeysCount ++; venstre ++; } hvis (venstre> = høyre) {pause; } bytte (inngang, venstre, høyre); if (input [left] == ​​partitioningValue) {swap (input, begin + leftEqualKeysCount, left); leftEqualKeysCount ++; } if (input [right] == ​​partitioningValue) {swap (input, right, end - rightEqualKeysCount); rightEqualKeysCount ++; } venstre ++; Ikke sant--; }

I neste fase må vi flytt alle de like elementene fra de to endene i midten. Når vi går ut av sløyfen, vil venstrepekeren være på et element hvis verdi ikke er mindre enn partitioningValue. Ved å bruke dette faktum begynner vi å flytte like elementer fra de to endene mot sentrum:

høyre = venstre - 1; for (int k = begynn; k = begynn + leftEqualKeysCount) bytte (inngang, k, høyre); } for (int k = end; k> end - rightEqualKeysCount; k--, left ++) {if (left <= end - rightEqualKeysCount) swap (input, left, k); } 

I den siste fasen kan vi returnere grensene til midtpartisjonen:

returner ny partisjon (høyre + 1, venstre - 1);

Til slutt, la oss ta en titt på en demonstrasjon av implementeringen vår på en prøveinngang

6. Algoritmeanalyse

Generelt har Quicksort-algoritmen en gjennomsnittlig sakstidskompleksitet på O (n * log (n)) og verst-tidskompleksitet på O (n2). Med en høy tetthet av duplikatnøkler får vi nesten alltid worst-performance med den trivielle implementeringen av Quicksort.

Imidlertid, når vi bruker treveis partisjoneringsvarianten av Quicksort, for eksempel DNF-partisjonering eller Bentleys partisjonering, kan vi forhindre den negative effekten av dupliserte nøkler. Når tettheten til duplikatnøkler øker, forbedres også ytelsen til algoritmen vår. Som et resultat får vi best mulig ytelse når alle nøkler er like, og vi får en enkelt partisjon som inneholder alle like nøkler i lineær tid.

Likevel må vi merke oss at vi i hovedsak legger til overhead når vi bytter til et treveis partisjoneringsskjema fra den trivielle en-pivot-partisjoneringen.

For DNF-basert tilnærming avhenger ikke overhead av tettheten av gjentatte taster. Så hvis vi bruker DNF-partisjonering for en matrise med alle unike nøkler, får vi dårlig ytelse sammenlignet med den trivielle implementeringen der vi optimalt velger pivot.

Men Bentley-McIlroy's tilnærming gjør en smart ting, da overhead for å flytte like nøklene fra de to ekstreme endene er avhengig av antall. Som et resultat, hvis vi bruker denne algoritmen for en matrise med alle unike nøkler, selv da, får vi rimelig god ytelse.

Oppsummert er den verste tilfelle tidskompleksiteten til både single-pivot partisjonering og treveis partisjoneringsalgoritmer. O (nlog (n)). Derimot, den virkelige fordelen er synlig i best-case-scenariene, der vi ser tidskompleksiteten gå fra O (nlog (n)) for en-pivot partisjonering til På) for treveis partisjonering.

7. Konklusjon

I denne opplæringen lærte vi om ytelsesproblemene med den trivielle implementeringen av Quicksort-algoritmen når inngangen har et stort antall gjentatte elementer.

Med en motivasjon for å løse dette problemet, har vi lært forskjellige treveis partisjoneringsordninger og hvordan vi kan implementere dem i Java.

Som alltid er den fullstendige kildekoden for Java-implementeringen som brukes i denne artikkelen tilgjengelig på GitHub.