Пређи на садржај

Celobrojno sortiranje

С Википедије, слободне енциклопедије

U računarstvu , celobrojno sortiranje je algoritam koji sortira i prikuplja podatke numeričkih vrednosti, od kojih je svaka ceo broj. Algoritam dizajniran za celobrojo sortiranje, može se upotrebiti i za sortiranje podataka koji su tipa float ili tipa string.[1] Mogućnost da izvršava aritmetiku nad celobrojnim vrednostima, omogućava celobrojnom sortiranju da bude brže od sortiranja poređenjem u mnogim slučajevima, u zavisnosti od toga koje su operacije dozvoljene u modelu računarstva i koliko su velike celobrojne vrednosti koje treba sortirati.

Klasični algoritam celobrojnog segmentnog sortiranja, counting sortiranja i radix sortiranja su najčešće korišćeni i najpraktičniji.[2] Mnogo kasnije istraživanja o algoritmu celobrojnog sortiranja usmerena su više na praktičnost nego na teorijska poboljšanja u najgorem slučaju , i algoritmi koji dolaze iz ove pretrage nisu praktični na 64-bitnoj arhitekturi računara, takođe eksperimenti su pokazali da neke od ovih metoda mogu biti poboljšanja na radix sortiranju za podatke koji sadrže 128 ili više bita po ključu.[3] Pored toga, za velike podatke,modeli približno slucajanog pristups memoriji mnogih algoritma celobrojnog sortiranja mogu ih sputati za razliku od sortiranja poređenjem koje je dizajnirano sa hijararhijom memorije na umu.[4] Celobrojno sortiranje pruža jednu od šest testova u DARPA High Productivity Computing System Discrete Mathematics benchmark suite[5] . I jedan od 11 testova u NAS Parallel Benchmarks.

Model računanja

[уреди | уреди извор]

Vreme izračunavanja celobrojnog sortiranja zavisi od tri parametra: da broj n bude sortiran, da veličina K najvećeg ključa bude sortiran, a broj bitova w može biti predstavljen na mašinskom jeziku računara na algoritmu koji se koristi. Tipično, pretpostavlja se da je w ≥ log2(max(n, K)); to jest, da je mašinski jezik dovoljno veliki da predstavi indeks u nizu ulaznih podataka i da je dovoljno veliki da predstavi samostalan ključ.[6] Algoritam celobrojnog sortiranja je obično dizajniran da radi bilo u modelima računanja bilo pokazivačkim ili automatima slučajnog pristupa, glavnna razlika između ova dva modela je u tome što sa slučajnim pristupom mašina omogućava da svaka vrednost koja se čuva u registrima koji će se koristiti kao adresa memorije, čita i piše operacije, sa cenom po jedinici rada, što omogućava određene kompleksne operacije nad podacima koji se brzo nalaze korišćenjem lookup tabela. Nasuprot tome, pokazivački model omogućava pristup memoriji samo preko pokazivača na memoriju koja se ne može koristiti koristeći aritmetičke operacije. U oba modela, dodatak, boolean operacije i binarne operacije pomeranja obično se mogu ostvariti u jednici vremena po operaciji. Različiti algoritmi sortiranja imaju različite pretpostavke, kako god bilo, celobrojno množenje se takođe obavlja u jedinici vremena po operaciji.[7] Drugi specijalizovani modeli računanja kao paralelan pristup memoriji će takođe biti razmatrani.[8]

Andersson, Miltersen & Thorup 1999 su pokazali da u nekim slučajevima kod množenja ili lookup tabele je potrebno da neki algoritmi celobrojnog sortiranja mogu biti zamenjeni pojedinim operacijama koje bi bile mnogo lakše da bi se lakše realizovale u hardveru, ali obično nisu dostupni na računarima opste namene. Thorup 2003, dokazao je kako se mogu zameniti ove operacije bitovskim poljima manipulišući instrukcijama koje su dostupne na Pentium procesorima.

Sortiranje u odnosu na primarni red

[уреди | уреди извор]

Moguće je da osnova algoritma sortiranja selekcijom bilo kog niza struktuiranih podataka, koja omogućava jedan od glavnih skupova od n elemenata sa ključem u intervalu od 0 to K − 1, u zavisnosti od operacije, da pronađe i ukloni stavku sa minimalnim ključem. Jednostavno se kreira prioritetni niz koji sadrži sve elemente, zatim se više puta primenjuje minimalno brisanje dok se niz ne isprazni. Deo niza čiji je element izbrisan, sada je sortiran deo niza. Vreme za stvaranje ovog algoritma je vreme za kreiranje niza, plus vreme za n minimalnih operacija brisanja. Na primer, kod algoritma sortiranja poređenjem, heap sortiranje ima ovu formu. Kako god bilo, takođe postoje algoritmi ovog tipa koji su brži za celobrojne ključeve, na osnovu prioritetnih redova struktuiranih podataka koji su specijalizovani za cele brojeve.

Konkretno, van Emde Boas stablo može da se koristi kao priopitetni red da sortira niz od n kljuceva, gde je svaki u opsegu od 0 to K − 1, u vremenskoj složenosti O(n log log K). To je teoretsko poboljšanje u odnosu na radix sortiranje kada je K dovoljno veliko. Međutim, da bi se koristilo van Emde Boas-ovo stablo, jedan ili treba direktno adresibilnu memoriju K reči, ili mora da se simulira pomoću Heš tabela, smanjujući tako linearni prostor, praveći algoritam slučajnim. Drugi prioritetni red sa sličnim performansama (uključujući potrebu randomizacije putem Heš tabela) je Y –brzo stablo koje je osmislio Willard 1982. Thorup 2007 je pokazao kako jednakost između prioritetnih redova ide u drugom smeru: ako je moguće izvšiti celobrojno sortiranje u vremenu T(n) po ključu, onda je isto vreme potrebno za ubacivanje ili brisanje operacije u primarnom redu. Throup - ova redukcija je komplikovana i podrazumeva dostupnost bilo brzih operacija množenja ili lookup tabele, ali takođe pruža alternativni prioritetni red koristeći samo sabiranje i logičke operacije sa vremenom T(n) + T(log n) + T(log log n) + ... po operaciji, nајviše množenjem vremenа od strаne iterativnog algoritma.

Algoritam za male ključeve

[уреди | уреди извор]

Odavno je poznato da segmentno sortiranje ili counting sortiranje mogu da sortiraju niz od n ključeva, svaki u opsegu od 0 do K − 1, u vremenu O(n + K). U segmentnom sortiranju, pokazivači na podatke distribuirani su u tabelu "bucket" (predstavljena kao vrsta povezanih listi) koristeći ključeve kao pokazivače u tabeli. Onda, su svi podaci spojeni tako da formiraju izlaznu listu.[9] U counting sortiranju, bucket je zamenjen brojačem koji određuje broj podataka koji imaju istu vrednost, a zatim prefix suma se koristi da se odredi podniz, u izlaznom nizu, gde bi trebalo da se nalaze podaci sa istom vrednošću.[10] Radix sortiranje je algoritamska tehnika u kojoj se neki drugi algoritam koji je odgovarajuć samo za male ključeve ponavlja, praveći algoritam koji se može upotrebiti na veće ključeve. Ključ koji je upotrebljen za i –ti korak drugog algoritma za sortiranje, je i –ta cifra pozicije celog ključa, prema radix sortiranju, počev od cifre najmanje težine i napreduje u najznačajnije. Da bi ovaj algoritam radio, osnova algoritma mora biti stabilna, podaci sa istim ključem ne bi trebali da menjaju pozicije među sobom. Koristeći radix sortiranje, radixom da se izabere proporcionalno n, sa segmentnim sortiranjem i counting sortiranjem u osnovi , moguće je sortirati niz od n ključeva, svaki u opsegu od 0 to K − 1, u vremenu O(n logn K). Koristeći 2n radix omogućava da ključ osnovnog algoritma bude napravjen koristeći samo binarno pomeranje i maskiranje.[11] Sofisticiranije tehnike sa sličnim ukusom i boljim performansama teorijski je razvio Kirkpatrick & Reisch 1984. Oni su primetili da svaki prolazak kroz radix sortiranje može da se tumači kao „smanjenje opsega“ tehnike koja, u linearnom vremenu, smanjuje maksimalne veličine ključeva za faktor n, umesto toga, njihova tehnika smanjuje veličinu ključa u kvadratnom korenu na kvadratni koren svoje ranije vrednosti (prepolovi broj bitova potrebnih za predstavljanje ključa), takođe u linearnom vremenu. Kao i u radix sortiranju, oni predstavljaju ključeve kao dvocifrene brojeve u osnovi b, gde je osnova b približno koren iz K. Onda se stavke grupišu i sortiraju se bucket sortiranjem u skladu sa svojim ciframa najveće težine, u linearnom vremenu, koristeći veliku ali neinicijalizovanu direktnu adresnu memoriju ili heš tabele. Svako segmentno sortiranje ima svog predstavnika: stavka sa najvećim ključem, oni zatim sortiraju listu podataka koristeći kao ključ cifre najveće težine kao predstavnike i cifre najmanje težine kao ne predstavnike.

Grupisanjem stavki sa liste segmentnim sortiranjem, svaki deo segmentnog sortiranja se može postaviti u sortiranom redosledu, a izdvajanjem predstavnika iz sortirane liste segmenti se mogu spojiti u sortiranom redosledu. Tako, u linearnom vremenu, problem sortiranja se svodi na drugi problem rekurzivnog sortiranja u kom su ključevi mnogo manji, kvadratni koren svoje prethodne veličine. Ovaj postupak se ponavlja sve dok ključ ne postane dovoljno mali da segmentno sortiranje dovodi do vremena izvršavanja O(n log logn K).

Komplikovani slučajno algoritam Han & Thorup 2002 omogućavada ova ograničenja budu umanjena još više, od O(n log logn K).

Algoritmi za nekoliko stavki

[уреди | уреди извор]

Algoritam celobrojnog sortiranja je neumeren ako se zahteva reč koja je veličine w koja je znatno veća log max(n, K).[12] Kao ekstremni primer, ako je wK, i svi ključevi su različiti, onda ključevi mogu biti sortirani predstavljajući ih kao bitovski niz, sa jednim bitom na poziciji i gde je i jedan od ulaznih ključeva, a zatim se više puta ukljanja bit najmanje težine.[13] Neumereno packed sortiranje koje je osmislio Albers & Hagerup 1997 koristi podprogram, koji je baziran na Ken Batcher - ovom paralelnom sortiranju mreže, za spajanje dve sortirane sekvence ključa gde je svaki od njih dovoljno kratak da se pakuje u jednoj mašinskoj reči. Ulaz u složeni sortirajući algoritam, niz predmeta složenih jedan po jedan reči, transformiše se u sabijenu formu, svaki niz reči drži više predmeta u složenom redu, koristeći ovaj potprogram udvostručvava broj jedinica pakovanih u svakoj reči. Kada je niz u zapakovanoj formi, Albers and Hagerup koriste formu sortiranja spajanjem da ih sortira, kada se dve sekvence spoje u jednu dužu sekvencu, istim paralelnim sortiranjem potprogram može da se koristi više puta za izdvajanje pakovanih reči sastavljenih od najmenjih preostalih elemenata od dve sekvence. Ovaj algoritam dobija dovoljnu brzinu od svoje reprezentacije da sortira ulaz u linearnom vremenu kad god je to moguće za jednu reč koja sadrži Ω(log n log log n) ključeva; tj, gde je log K log n log log ncw za neku konstantu c > 0.

Algoritam za velike reči

[уреди | уреди извор]

segmentno sortiranje, counting sortiranje, radix sortiranje ivan Emde Boas - ovo stablo najbolje radi za ključeve male veličine, jer sa dovoljno velikim ključevima, oni postaju sporiji od algoritma za sortiranje poređenjem. Međutim, kada je veličina ključa ili veličina reči veoma velika u odnosu na broj jedinica (ili ekvivalentna kada je broj jedinica mali), moguće je sortirati algoritmom quick sortiranja, koristeći različite algoritme koji koriste prednosti urođenog paralelizma sa mogućnošću da obavljaju aritmetičke operacije na velikim rečima.

Rani rezultat u tom pravcu dali su Ajtai, Fredman & Komlós 1984) koristeći jedinicu uzorka modela izračunavanja(veštački model u kome se složenost algoritma meri samo po broju pristupa memoriji koje obavi). Oslanjajući se na svoj rad, Fredman & Willard 1994 opisali su dve strukture, Q-heap i automatski heap, koje su primenljive na automate sa slucajnim pristupom. Q-heap je paralelna verzija binarnog stabla, i omogućava operacije prioritetnih nizova kao i da odabiranje naslednika i pretka bude obavljeno neprekidno za setove O((log N)1/4) predmeta, gde je N ≤ 2w veličina tabele pre izračunavanja potrebna za implementiranje strukture podataka. Atomski heap je B-stablo u kome je svaki čvor drveta predstavljen kao Q-heap; dozvoljava operacije prioritetnih redova u konstantnom vremenu za (log N)O(1) stavki. Andersson et al. 1998 predvideli su algoritam pod nazivom sortiranje obeležavanjem koje omogućava linearno vreme sortiranja od 2O((log w)1/2 − ε), za bilo koje ε > 0. Kao i u algoritmu Kirkpatrick i Reisch, oni obavaljaju smanjenje opsega koristeći prikaz ključa kao brojeve u osnovi b sa pažljivim izborom b. Smanjen opseg algoritma zamenjuje svaku cifru „potpisom“, heširanom vrednošću sa O(log n) bita koji imaju različite vrednosti cifara različitih potpisa. Ako je n dovoljno malo, brojevi koji su formirani procesom zamene biće značajno manji od originalnog ključa, uključujući neumereni algoritam sortiranja pakovanjem kreiranih od strane Albers & Hagerup 1997 da sortira zamenjene brojeve u linearnom vremenu. Iz sortirane liste zamenjenih brojeva, moguće je formirati kompresovano digitalno stablo od ključeva u linearnom vremenu, a deca svakog čvora digitalnog stabla mogu se sortirati rekurzivno koristeći samo ključeve veličine b, nakon čega stablo pravi poprečan sortiran niz stavki.

Trans-Dihotomni algoritmi

[уреди | уреди извор]

Fredman & Willard 1993 su uveli trans-dihotomni model analize za algoritam celobrojnog sortiranja, u kome se ništa ne pretpostavlja o rasponu celobrojnih ključeva i mora se garantovati performansa algoritma samo funkcijom broja vrednosti podatka. Alternativno, u ovom modelu, potrebno vreme za jedan algoritam na grupi n stavki pretpostavlja se da je najgori slučaj potrebnog vremena za bilo koju moguću kombinaciju K i w. Na primer, Fredman and Wilardov algoritam sortiranja fuzionim stablom radi u vremenu O(n log n / log log n), poboljšanje u odnosu na sortiranje poređenjem za bilo koji izbor Ki w. Alternativna verzija njihovog algoritma koja ukljućuje korišćenje nasumice izabranih brojeva i deljenje celine unapređuje ovo u O(nlog n).

Od njihovih pronalazaka, jos bolji algoritmi su razvijeni. Na primer, brzo primenjivanje Kirkpatrick–Reisch tehnike smanivanja raspona dok ključevi ne postanu dovoljno mali da se primeni Albers–Hagerup algoritam sortiranja sabijanjem, moguće je sortirati u vremenu O(n log log n), ipak, deo smanjenja raspona ovog algoritma zahteva ili veliku memoriju (proporcionalnu sa K) ili biranje slućajnog elementa u vidu heš tabela.[14] Han & Thorup 2002 pokazali su kako sortirati u slučajnom vremenu O(nlog log n). Njihova tehnika uključuje korišćenje ideja povezanih sa obeležavajućim sortiranjem za razdvajanje podataka u mnogo malih podlista, veličine dovoljno male da sortiranje obeležavanjem može efikasno složiti svaku od njih. Moguće je koristiti slične ideale za sortiranje celih brojeva u vremenu O(n log log n))i linearni prostor.[15] Koristeći samo proste aritmeticke operacije (bez množenja ili tabelarnih pronalaženja) moguće je sortirati u slučajnom očekivanom vremenu O(n log log n)[16] ili determinističkom vremenu O(n (log log n)1 + ε) za bilo koju nepromenjivu ε > 0.[1].

Референце

[уреди | уреди извор]
  1. ^ а б Han & Thorup 2002
  2. ^ McIlroy, Bostic & McIlroy 1993; Andersson & Nilsson 1998
  3. ^ Rahman & Raman 1998
  4. ^ Pedersen 1999
  5. ^ DARPA HPCS Discrete Mathematics Benchmarks Архивирано на сајту Wayback Machine (10. март 2016), Duncan A. Buell, University of South Carolina, retrieved 2011-04-20.
  6. ^ Fredman & Willard 1993
  7. ^ The question of whether integer multiplication or table lookup operations should be permitted goes back to Fredman & Willard 1993; see also Andersson, Miltersen & Thorup 1999
  8. ^ Reif 1985;comment in Cole & Vishkin 1986; Hagerup 1987; Bhatt et al. 1991; Albers & Hagerup 1997
  9. ^ Goodrich & Tamassia 2002. Note that, although Cormen et al. 2001 also describe a version of bucket sort, the version they describe is adapted to inputs where the keys are real numbers with a known distribution, rather than integer sorting.
  10. ^ Cormen et al. 2001, 8.2 Counting Sort. стр. 168–169.
  11. ^ Comrie 1929–1930; Cormen et al. 2001, 8.3 Radix Sort. стр. 170–173.
  12. ^ Kirkpatrick & Reisch 1984; Albers & Hagerup 1997
  13. ^ Kirkpatrick & Reisch 1984
  14. ^ Andersson et al. 1998
  15. ^ Han 2004
  16. ^ Thorup 2002