Proksmap sortiranje

S Vikipedije, slobodne enciklopedije
Proksmap sortiranje
Insertion sorting into buckets during proxmap.
Insertion sorting into buckets during proxmap.
Primer sortiranja umetanjem liste slučajnih brojeva.
KlasaAlgoritam sortiranja
Struktura podatakaNiz
Najgora performanca
Najbolja performanca
Najgora prostorna kompleksnost
Elementi su raspoređeni među kofama
Nasuprot bucket sort-iranju koje se vrši nakon što su kofe napunjene, elementu su sortirani umetanjem kako su ubacivani

Proksmapsort ili Proksmap sortiranje je vrsta algoritma sortiranja, koji radi tako što podeli niz podataka, ili ključeva, na manji broj podnizova. Ime je skraćenica od računanja "proximity map"-e, koja određuje, za svaki ključ K, početak podniza u kome će se K nalaziti u konačnom poretku. Ključevi su postavljeni u svaki podniz korišćenjem sortiranja umetanjem. Ukoliko su ključevi dobro raspoređeni kroz podnizove, vremenska složenost sortiranja je linearna, što je mnogo brže od Comparison sort sortiranja, koje ne može biti bolje od O(nlogn). Procene teorije kompleksnosti uključuju broj podnizova i proximity mapping funkciju. To je oblik Bucket sort-a i Radix sort-a. Algoritam ne postaje mnogo kompleksniji kako količina podataka raste.

Kada je proksmap sortiranje završeno ProxmapSearch može biti korišćeno za pronalazak ključeva u sortiranom nizu za vremensku složenost O(1), ukoliko su ključevi dobro raspoređeni tokom sortiranja.

Istorija[uredi | uredi izvor]

Pregled[uredi | uredi izvor]

Osnovna strategija[uredi | uredi izvor]

Osnova: Za niz A sa n ključeva:

  • mapira ključ u podnizu kranjeg niza A2 primenom map key funkcija za svaki element niza
  • određuje koliko ključeva će biti mapirano na isti podniz koristeći niz "broja pogodaka," H
  • određuje gde počinje svaki podniz u krajnjem nizu, tako da je svaka "kofa" odgovarajuće veličine za sve ključeve koji će biti mapirani, koristeći niz "proksmapa" P
  • za svaki ključ, računa podniz na koji će biti mapiran, koristeći niz "lokacija" L
  • za svaki ključ, pronalazi lokaciju i smešta ga u ćeliju A2; ako nastaje kolizija sa ključem koji je već tu, sotrira se umetanjem, pomeranjem većih ključeva za jedno mesto udesno, kako bi se obezbedio prostor za ovaj ključ. Pošto su podnizovi dovoljno veliki da skladište sve ključeve koji su mapirani na njih, neće doći do prekoračenja u naredni podniz.

Jednostavnije: Za niz A sa n ključeva:

  1. Inicijalizuj: Napravi i inicijalizuj dva niza dužine n: hitCount, proxMap i 2 niza dužine A.length: lokaciju i A2.
  2. Deljenje: koristeći pažljivo odabranu mapKey funkciju, podeli A2 na podnizove, koristeći ključeve iz A.
  3. Rasporedi: prođi kroz A, ubaci svaki ključ u odgovarajuću kofu u A2; sortiranje umetanjem po potrebi.
  4. Prikupljanje: prođi kroz podnizove redom i postavi sve elemente u originalni niz, ili prostije, koristi A2.

Napomena: ključevi mogu sadržati i druge podatke, na primer, instanca niza objekta Student sadrži ključ, ali i indeks studenta i ime. ProxMapSort je pogodan za organizaciju grupa objekata, a ne samo ključeva.

Primer[uredi | uredi izvor]

Uzmimo pun niz: A[0 do n-1] sa n ključeva. Neka je i indeks niza A. Sortiraj ključeve A' u niz A2 iste veličine. Map key funkcija je definisana kao mapKey(key) = floor(K).

Array table
A1 6.7 5.9 8.4 1.2 7.3 3.7 11.5 1.1 4.8 0.4 10.5 6.1 1.8
H 1 3 0 1 1 1 2 1 1 0 1 1
P 0 1 -9 4 5 6 7 9 10 -9 11 12
L 7 6 10 1 9 4 12 1 5 0 11 7 1
A2 0.4 1.1 1.2 1.8 3.7 4.8 5.9 6.1 6.7 7.3 8.4 10.5 11.5

A demonstration of ProxMapSort, a bucket sort variant that uses intermediate parallel arrays to efficiently index and size its sublists.

Pseudokod[uredi | uredi izvor]

// compute hit counts
for i = 0 to 11 // where 11 is n
{
    H[i] = 0;
}
for i = 0 to 12 // where 12 is A.length
{
    pos = MapKey(A[i]);
    H[pos] = H[pos] + 1;
}

runningTotal = 0; // compute prox map – location of start of each subarray
for i = 0 to 11
    if H[i] = 0
        P[i] = -9;
    else
        P[i] = runningTotal;
        runningTotal = runningTotal + H[i];

for i = 0 to 12 // compute location – subarray – in A2 into which each item in A is to be placed
    L[i] = P[MapKey(A[i])];

for I = 0 to 12; // sort items
    A2[I] = <empty>;
for i = 0 to 12 // insert each item into subarray beginning at start, preserving order
{
    start = L[i]; // subarray for this item begins at this location
    insertion made = false;
    for j = start to (<the end of A2 is found, and insertion not made>)
    {
        if A2[j] == <empty> // if subarray empty, just put item in first position of subarray
            A2[j] = A[i];
            insertion made = true;
        else if A[i] < A2[j] // key belongs at A2[j]
            int end = j + 1; // find end of used part of subarray – where first <empty> is
            while (A2[end] != <empty>)
                end++;
            for k = end -1 to j // move larger keys to the right 1 cell
                A2[k+1] = A2[k];
                A2[j] = A[i];
            insertion made = true; // add in new key
    }
}

Ovde, A je niz koji se sortira, a mapKey funkcija određuje broj podnizova koji se koriste. Na primer, floor(K) će prosto dodeliti onoliko podnizova koliko ima celih brojeva u A. Deljenje ključa konstantom smanjuje broj podnizova; Različite funkcije se mogu koristiti da prevedu domen elemenata A u podnizove, kao što su zamena slova A–Z sa 0–25 ili vraćanje prvog elementa (0–255) za dati string. Podnizovi se sortiraju kako podaci pristižu, a ne kada su svi podaci smešteni u podniz, kao što je slučaj u tipičnom Bucket sort-u.

Proxmap Pretraga[uredi | uredi izvor]

ProxmapSearch koristi proxMap niz, generisan prethodno proksmap sortiranjem, kako bi se pronašli ključevi u sortiranom nizu A2 u konstantnom vremenu.

Osnovna strategija[uredi | uredi izvor]

  • Sortiraj ključeve koristeći ProxmapSort, čuvajući MapKey funkciju i P i A2 nizove.
  • Za pretragu ključa, idi do P[MapKey(k)], početka podniza koji sadrži ključ, ako se taj ključ nalazi u podacima.
  • Sekvencijalno pretraži podniz; ukoliko je ključ pronađen, vrati ga; ukoliko se pronađe vrednost veća od ključa, ključ nije u podacima.
  • Računanje P[MapKey(k)] je O(1) vremenske složenosti. Ukoliko je tokom sortiranja korišćena mapa koja daje dobar raspored ključeva, svaki podniz je ograničen odozogo konstantom c, tako da je najviše c poređenja potrebno da se ključ pronađe, ili da se sazna da li je prisutan; stoga ProxmapSearch je O(1) vremenske složenosti. Ako se koristi najgora mapa, svi ključevi su u jednom podstringu i najgora vremenska složenost je O(n) poređenja.

Pseudokod[uredi | uredi izvor]

function mapKey(key) 

  return floor(key)

  proxMap ← previously generated proxmap array of size n
  A2 ← previously sorted array of size n
function proxmap-search(key)
  for i = proxMap[mapKey(key)] to length(array)-1
    if (sortedArray[i].key == key)
      return sortedArray[i]

Analiza[uredi | uredi izvor]

Performanse[uredi | uredi izvor]

Vremenska složenost računanja H, P i L je O(n). Svaki se računa tokom jednog prolaska kroz niz, uz konstantno provedeno vreme u svakoj lokaciji niza.

  • Najgori slučaj: MapKey skladišti sve elemente u jedan podniz, što dovodi do standardnog sortiranja umetanjem, vremenske složenosti O(n^2).
  • Najbolji slučaj: MapKey skladišti mali broj elemenata u svaki podniz u redosledu gde dolazi do najboljeg slučaja sortiranja umetanjem. Svako sortiranje umetanjem je složenosti O(c), c je veličina podniza; postoji p podnizova, stoga p * c = n, tako da faza umetanja složenosti O(n); stoga složenost ProxmapSort-a je O(n).
  • Prosečan slučaj: Najveća veličina svakog podniza je c, konstanta; umetanje za svaki podstring je onda u najgorem slučaju O(c^2) složenosti, takođe konstanta. (Stvarno vreme zapravo može biti mnogo bolje, pošto c elemenata nije sortirano dok se poslednji element ne doda u kofu). Ukupno vreme predstavlja broj kofa, (n/c), složenosti O(c^2)=O(n).

Korišćenje dobre MapKey funkcije je važno za izbegavanje najgoreg slučaja. Moramo znati nešto o rasporedu podataka da bismo došli do dobrog ključa.

Optimizacije[uredi | uredi izvor]

  1. Štednja vremena: Sačuvati MapKey(i) vrednosti, kako se ne bi ponovo računale (kao što su u kodu iznad).
  2. Štednja prostora: proxMaps mogu biti čuvane u hitCount nizu, pošto on nije više potreban kada je proksmapa određena; podaci mogu biti sortirani u A, umesto korišćenja A2, ako neko poželi da navede koje su vrednosti A do sada sortirane.

Poređenje sa drugim algoritmima[uredi | uredi izvor]

Pošto proksmap sortiranje nije samo algoritam sortiranja, donja granica Ω(n log n) nije primenjiva. Brzina se može objasniti time što u osnovi nije zasnovan na poređenju i što koristi nizove, umesto dinamički alociranih objekata i pokazivača koji se moraju pratiti, kao što je slučaj kod binarnog stabla pretrage.

ProxmapSort omogućava upotrebu ProxmapSearch-a. Uprkos složenosti O(n), ProxMapSearch to nadoknađuje O(1) prosečnim vremenom pristupa, što ga čini privlačnim za velike baze podataka. Ukoliko podaci ne moraju biti često ažurirani, vreme pristupa može učiniti ovu funkciju privlačnijom od ostalih sortiranja koja nisu zasnovana na poređenju.

Generički bucket sort u vezi sa ProxmapSort-om[uredi | uredi izvor]

Kao ProxmapSort, bucket sort uobičajeno rukuje listom od n numeričkih ulaza, u granicama od 0 do nekog maksimalnog ključa ili vrednosti M i deli domen vrednosti u n kofa veličine M/n. Ukoliko je svaka kofa sortirana koristeći sortiranje umetanjem, može se pokazati da ProxmapSort i bucket sort rade paralelnom linearnom vremenskom složenošću.[1] Međutim, performanse ovog sortiranja opadaju sa povećanjem broja ključeva u kofama; ukoliko su vrednosti zbijene, biće svrstane u istu kofu i performase će biti značajno umanjene. Ova osobina važi i za ProxmapSort: ukoliko su kofe prevelike, performanse će značajno opasti.

Reference[uredi | uredi izvor]

  1. ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill. 2001. ISBN 978-0-262-03293-3. Section 8.4: Bucket sort. str. 174-177.

Literatura[uredi | uredi izvor]

Spoljašnje veze[uredi | uredi izvor]

Preuzeto iz „https://sr.wikipedia.org/w/index.php?title=Проксмап_сортирање&oldid=26983437”