streamalism.org

1. Pregled

Složenost vremena izvođenja algoritama često ovisi o prirodi unosa.

U ovom uputstvu vidjet ćemo kako se trivijalna implementacija Quicksort algoritma ima slabe performanse za ponovljene elemente.

Nadalje, naučit ćemo nekoliko varijanti Quicksort za učinkovito particioniranje i sortiranje ulaza s velikom gustoćom dupliciranih ključeva.

2. Trivijalni brzi sorti

Quicksort je učinkovit algoritam sortiranja zasnovan na paradigmi podijeli i osvoji. Funkcionalno gledano, to djeluje na mjestu ulaznog polja i preuređuje elemente jednostavnim operacijama usporedbe i zamjene.

2.1. Particioniranje s jednim zaokretom

Trivijalna implementacija Quicksort algoritma u velikoj se mjeri oslanja na postupak particioniranja s jednim pivotom. Drugim riječima, particioniranje dijeli niz A = [a_str, a_{p + 1}, a_{p + 2}, ..., a_r] u dva dijela A [p..q] i A [q + 1..r] tako da:

• Svi elementi u prvoj particiji, A [p..q] su manje ili jednake pivot vrijednosti A [q]
• Svi elementi u drugoj particiji, A [q + 1..r] su veće ili jednake vrijednosti osovine A [q]

Nakon toga, dvije se particije tretiraju kao neovisni ulazni nizovi i predaju se Quicksort algoritmu. Pogledajmo Lomutov Quicksort na djelu:

2.2. Izvedba s ponovljenim elementima

Recimo da imamo niz A = [4, 4, 4, 4, 4, 4, 4] koji ima sve jednake elemente.

Kada particioniramo ovaj niz s shemom particioniranja s jednim pivotom, dobit ćemo dvije particije. Prva će particija biti prazna, dok će druga particija imati N-1 elemente. Unaprijediti, svaki sljedeći poziv postupka particije smanjit će ulaznu veličinu samo za jedan. Pogledajmo kako to funkcionira:

Budući da postupak particije ima linearnu vremensku složenost, ukupna vremenska složenost, u ovom je slučaju kvadratna. Ovo je najgori scenarij za naš ulazni niz.

3. Trosmjerna particija

Da bismo učinkovito sortirali niz s velikim brojem ponovljenih tipki, možemo odabrati odgovornije rukovanje jednakim tipkama. Ideja je postaviti ih u pravi položaj kad ih prvi put sretnemo. Dakle, ono što tražimo je stanje particije niza:

• Krajnja lijeva particija sadrži elemente koji su strogo manji od particijskog ključa
• Thesrednja particija sadrži sve elemente koji su jednaki particijskom ključu
• Desna particija sadrži sve elemente koji su strogo veći od particijskog ključa

Sada ćemo dublje zaroniti u nekoliko pristupa koje možemo koristiti za postizanje trosmjerne particije.

4. Dijkstrin pristup

Dijkstrin pristup učinkovit je način izvođenja trosmjerne particije. Da bismo to razumjeli, pogledajmo klasični problem programiranja.

4.1. Problem nizozemske nacionalne zastave

Inspiriran trobojnom zastavom Nizozemske, Edsger Dijkstra predložio je programski problem nazvan Nizozemski nacionalni problem zastave (DNF).

Ukratko, to je problem preslagivanja gdje dobivamo kuglice od tri boje nasumično smještene u liniju, a od nas se traži da grupiramo iste kuglice zajedno. Štoviše, preslagivanje mora osigurati da skupine slijede ispravan redoslijed.

Zanimljivo je da problem DNF čini zapanjujuću analogiju s trosmjernom particijom niza s ponovljenim elementima.

Sve brojeve niza možemo kategorizirati u tri skupine s obzirom na zadani ključ:

• Crvena grupa sadrži sve elemente koji su strogo manji od ključa
• Bijela skupina sadrži sve elemente koji su jednaki ključu
• Plava skupina sadrži sve elemente koji su strogo veći od ključa

4.2. Algoritam

Jedan od pristupa rješavanju problema DNF je odabrati prvi element kao particijski ključ i skenirati niz s lijeva na desno. Dok provjeravamo svaki element, premještamo ga u njegovu ispravnu skupinu, naime Manji, Jednaki i Veliki.

Da bismo pratili napredak u podjeli, trebala bi nam pomoć tri naputka, naime lt, Trenutno, i gt. U bilo kojem trenutku, elementi s lijeve strane lt bit će strogo manji od particijskog ključa i elemenata s desne strane gt bit će strogo veći od ključa.

Dalje, koristit ćemo Trenutno pokazivač za skeniranje, što znači da svi elementi koji se nalaze između Trenutno i gt pokazivači tek trebaju biti istraženi:

Za početak možemo postaviti lt i Trenutno pokazivači na samom početku niza i gt pokazivač na njegovom kraju:

Za svaki element očitan putem Trenutno pokazivač, uspoređujemo ga s particijskim ključem i poduzimamo jednu od tri složene akcije:

• Ako ulaz [trenutna] <tipka, onda razmjenjujemo ulaz [trenutno] i ulaz [lt] i povećati oboje Trenutno i lt pokazivači
• Ako ulaz [trenutno] == ključ, zatim povećavamo Trenutno pokazivač
• Ako tipka [trenutno]> tipka, onda razmjenjujemo ulaz [trenutno] i ulaz [gt] i dekrement gt

Naposljetku, zaustavit ćemo se kad Trenutno i gt pokazivači se križaju. Uz to, veličina neistraženog područja smanjuje se na nulu, a ostat će nam samo tri potrebne particije.

Konačno, pogledajmo kako ovaj algoritam radi na ulaznom nizu koji ima dvostruke elemente:

4.3. Provedba

Prvo, napišimo postupak korisnosti s imenom usporedi () napraviti trosmjernu usporedbu između dva broja:

javna statička int usporedba (int num1, int num2) {if (num1> num2) return 1; inače if (num1 <num2) return -1; else return 0; }

Dalje, dodajmo metodu tzv zamijeniti () za razmjenu elemenata u dva indeksa istog niza:

javna statička zamjena praznina (int [] niz, int pozicija1, int pozicija2) {if (pozicija1! = pozicija2) {int temp = niz [pozicija1]; niz [pozicija1] = niz [pozicija2]; niz [pozicija2] = temp; }}

Da bismo jedinstveno identificirali particiju u polju, trebat će nam njezini lijevi i desni granični indeksi. Pa, krenimo i stvorimo a Pregrada razred:

particija javne klase {private int lijevo; privatno int pravo; }

Sada smo spremni napisati svoj trosmjerni način particija () postupak:

javna statička particija particije (int [] ulaz, int početak, int kraj) {int lt = početak, trenutni = početak, gt = kraj; int partitioningValue = input [početak]; while (current <= gt) {int compareCurrent = compare (input [current], partitioningValue); prekidač (compareCurrent) {slučaj -1: swap (input, current ++, lt ++); pauza; slučaj 0: trenutni ++; pauza; slučaj 1: zamjena (ulaz, struja, gt--); pauza; }} vrati novu particiju (lt, gt); }

Na kraju, napišimo a brzi sortiraj () metoda koja koristi našu trosmjernu shemu particioniranja za rekurzivno sortiranje lijeve i desne particije:

javna statička void quickort (int [] ulaz, int početak, int kraj) {if (kraj <= početak) return; Particija middlePartition = particija (ulaz, početak, kraj); brzi sortiranje (input, begin, middlePartition.getLeft () - 1); brzi sortiranje (input, middlePartition.getRight () + 1, kraj); }

5. Bentley-McIlroyev pristup

Jon Bentley i Douglas McIlroy suautori su optimizirana verzija Quicksort algoritma. Razumijemo i implementiramo ovu varijantu u Javi:

5.1. Shema podjele

Suština algoritma je shema particioniranja zasnovana na iteraciji. U početku je čitav niz brojeva za nas neistraženi teritorij:

Zatim započinjemo s istraživanjem elemenata niza iz lijevog i desnog smjera. Kad god ulazimo ili izlazimo iz petlje istraživanja, možemo vizualizirati niz kao sastav pet regija:

• Na krajnja dva kraja nalaze se područja koja imaju elemente koji su jednaki vrijednosti particije
• Neistraženo područje ostaje u središtu i njegova se veličina smanjuje sa svakom ponavljanjem
• S lijeve strane neistražene regije leže svi elementi manji od vrijednosti particioniranja
• Na desnoj strani neistražene regije nalaze se elementi veći od vrijednosti particije

Na kraju, naša petlja istraživanja prestaje kad više nema elemenata koji se istražuju. U ovoj fazi, veličina neistraženog područja je zapravo nula, a preostale su nam samo četiri regije:

Dalje, mi pomaknite sve elemente iz dvije jednake regije u središte tako da postoji samo jedna jednaka regija u središtu koja okružuje manja regija slijeva i veća regija s desne strane. Da bismo to učinili, prvo zamijenimo elemente u lijevoj jednakoj regiji s elementima na desnom kraju manje regije. Slično tome, elementi u desnoj jednakoj regiji zamjenjuju se elementima na lijevom kraju veće regije.

Napokon ćemo biti ostao sa samo tri pregrade, a isti pristup možemo dalje koristiti za podjelu manjih i većih regija.

5.2. Provedba

U našoj rekurzivnoj implementaciji trosmjernog Quicksort-a, morat ćemo pozvati naš particijski postupak za podnizove koji će imati različit skup donjih i gornjih granica. Dakle, naša particija () metoda mora prihvatiti tri ulaza, naime niz zajedno s lijevom i desnom granicom.

javna statička particija particije (int ulaz [], int početak, int kraj) {// vraća prozor particije}

Radi jednostavnosti možemo odaberite vrijednost particioniranja kao posljednji element niza. Također, definirajmo dvije varijable lijevo = početak i desno = kraj istražiti niz prema unutra.

Nadalje, trebat ćemo i mi pratite broj jednakih elemenata koji leže krajnje lijevo i desno. Dakle, krenimo s inicijalizacijom leftEqualKeysCount = 0 i rightEqualKeysCount = 0, i sada smo spremni istražiti i podijeliti niz.

Prvo se krećemo iz oba smjera i naći inverziju gdje element s lijeve strane nije manji od particione vrijednosti, a element s desne strane nije veći od particionirajuće vrijednosti. Zatim, ako se dva pokazivača lijevo i desno ne prekriže, zamijenimo dva elementa.

U svakoj iteraciji premještamo elemente jednake particijska vrijednost prema dva kraja i povećajte odgovarajući brojač:

while (true) {while (input [left] partitioningValue) {if (right == begin) break; pravo--; } if (lijevo == desno && input [lijevo] == particioniranjeVrijednost) {swap (ulaz, početak + leftEqualKeysCount, lijevo); leftEqualKeysCount ++; lijevo ++; } if (lijevo> = desno) {break; } zamjena (ulaz, lijevo, desno); if (input [left] == ​​partitioningValue) {swap (input, begin + leftEqualKeysCount, left); leftEqualKeysCount ++; } if (input [right] == ​​partitioningValue) {swap (input, right, end - rightEqualKeysCount); rightEqualKeysCount ++; } lijevo ++; pravo--; }

U sljedećoj fazi moramo pomaknite sve jednake elemente s dva kraja u središte. Nakon što izađemo iz petlje, lijevi pokazivač bit će na elementu čija vrijednost nije manja od particijska vrijednost. Koristeći ovu činjenicu, počinjemo pomicati jednake elemente s dva kraja prema centru:

desno = lijevo - 1; za (int k = početak; k = početak + leftEqualKeysCount) swap (ulaz, k, desno); } for (int k = end; k> end - rightEqualKeysCount; k--, left ++) {if (left <= end - rightEqualKeysCount) swap (input, left, k); } 

U posljednjoj fazi možemo vratiti granice srednje particije:

vrati novu particiju (desno + 1, lijevo - 1);

Na kraju, pogledajmo demonstraciju naše implementacije na uzorku unosa

6. Analiza algoritma

Općenito, Quicksort algoritam ima vremensku složenost prosječnog slučaja O (n * log (n)) i vremensku složenost O-a (n2) u najgorem slučaju. Uz veliku gustoću dupliciranih ključeva, gotovo uvijek postižemo najgore performanse s trivijalnom implementacijom Quicksorta.

Međutim, kada koristimo trosmjernu varijantu particioniranja Quicksort-a, poput DNF particije ili Bentley-jeve particije, možemo spriječiti negativan učinak dupliciranih ključeva. Dalje, kako se povećava gustoća dupliciranih ključeva, poboljšava se i izvedba našeg algoritma. Kao rezultat, postižemo najbolje slučajeve kada su svi ključevi jednaki i dobivamo jednu particiju koja sadrži sve jednake ključeve u linearnom vremenu.

Ipak, moramo napomenuti da u osnovi dodajemo opće troškove kada se prebacimo na trosmjernu shemu particioniranja s trivijalne particije s jednim pivotom.

Za pristup zasnovan na DNF-u, opći troškovi ne ovise o gustoći ponovljenih tipki. Dakle, ako koristimo DNF particioniranje za niz sa svim jedinstvenim ključevima, tada ćemo dobiti loše performanse u usporedbi s trivijalnom implementacijom u kojoj optimalno biramo osovinu.

Ali, pristup Bentley-McIlroya čini pametne stvari jer općenito premještanje jednakih tipki s dva krajnja kraja ovisi o njihovom broju. Kao rezultat toga, ako čak i tada koristimo ovaj algoritam za niz sa svim jedinstvenim ključevima, dobit ćemo relativno dobre performanse.

Ukratko, najgora vremenska složenost algoritama za jednosmjerno i trosmjerno particioniranje je O (nlog (n)). Međutim, stvarna korist vidljiva je u najboljim scenarijima, odakle vidimo vremensku složenost O (nlog (n)) za particije s jednim pivotom na Na) za trosmjernu particiju.

7. Zaključak

U ovom uputstvu naučili smo o problemima izvedbe s trivijalnom implementacijom Quicksort algoritma kada ulaz ima velik broj ponovljenih elemenata.

S motivacijom da riješimo ovaj problem, mi naučio različite trosmjerne sheme podjele i kako ih možemo implementirati u Javi.

Kao i uvijek, cjeloviti izvorni kod za implementaciju Jave korišten u ovom članku dostupan je na GitHubu.