Spoljašnje sortiranje

Spoljašnje sortiranje je pojam koji se korist za klasu algoritama sortiranja koji sadržati velike količine podataka. Spoljašnje sortiranje se koristi kada podaci ne mogu da stanu u glavnu memoriju uređaja (najčešće RAM), pa umesto toga oni moraju biti smešteni u sporiju spoljašnju memoriju (obično tvrdi disk). Spoljašnje sortiranje obično koristi sortiranje-objedinjavanje strategiju. U fazi sortiranja, delovi podatkaka dovoljno mali da stanu u glavnou memoriju se čitaju, sortiraju, i ispisuju u privremeni fajl. U fazi objedinjavanja, sortirani podfajlovi se spajaju u jedan fajl.

Spoljašnji algoritam objedinjavanjem

Jedan od primera spoljašnjeg sortiranja je algoritam spoljašnjeg sortiranja objedinjavanjem(eng. external merge sort), koji sortira delove koji mogu da stanu u RAM-u, a onda ih spaja. Na primer za sortiranje 900 megabajta podataka korišćenjem 100 megabajta RAM-a:

• Učitaj 100 MB podataka u glavnou memoriju i sortiraj nekom konvencionalnom metodom, kao što je kviksort.
• Upiši sortirane podatke na disku.
• Ponovi korake 1 i 2 dok se svi podaci ne nalaze u sortirane delove od po 100 MB (ima 900MB / 100 MB = 9 delova), koji sada treba biti spojene u jednu izlaznu datoteku.
• Učitaj prvih 10 MB (= 100 MB / (9 chunks 1)) svakog sortiranog dela u ulazne bafer u glavnoj memoriji i alociraj preostalih 10 MB za izlazni buffer. (U praksi, bolje performanse bi omogućilo

pravljenje većeg izlaznig bafera, a manjeg ulaznog bafera).

• Izvodi 9-smerno objedinjavanje i smesti rezultat u izlazni buffer. Ako je izlazni bafer pun, upiši rezultat u konačno sortiranu datoteku, i ispraznite bafer. Ako bilo koji od 9 ulaznih bafera postane prazan, napuniti ga sa sledećih 10 MB od dodeljenih 100 MB sortiranog dela sve dok ima dostupnih podataka iz tog dela. Ovo je ključni korak - jer algoritam objedninjavanjem prolazi samo jednom

kroz svaki od delova, svaki deo ne mora biti učitan u potpunosti, već sekvencijalno njegovi delovi mogu se učitati kada je potrebno.

Dodatni prolaz

Ovaj primer prikazuje sortiranje kroz dva prolaska: prvo sortiranje, a zatim sledi objedninjavanje. Uočite da smo imali jedan prolaz koji je spojio sve delove odjednom, za razliku od običnog sortiranja objedinjavanjem, gde objedinjujemo po dva dela u svakom koraku, i i potrebno je log n ovakvih prolazaka. Razlog za to je da svaki ovakav prolazak zahteva čitanje i pisanje svake vrednost iz niz na disku i iz diska istovremeno. Pristupanje disku je obično sporo, pa čitanje i pisanje treba izbegavati koliko je god moguće.

Međutim, postoji prečice korišćenjem manjeg broja prolazka. Kako se broj delova povećava, količina podataka koja može da se pročitati, na vreme iz svako od delova tokom objedinjavanja, se smanjuje. Za sortiranje, recimo, 50 GB u 100 MB RAM-a, koristeći jedan prolazak nije efikasno: zahtev diska da se ulayni bafer napuni podacima iz svakog od 500 delova (čitamo 100MB / 501 ~ 200KB iz svkog dela istovremeno) uzima većinu vremena sorta. Koristeći dva prolaska rešava problem. Tada sortiranje može izgledati ovako:

• Pokrenite početni prolazak sortiranja delova kao i pre.
• Pokreni prvi prolazak objedinjavanja kombinovanjem 25 delova istovremeno, što dovodi do 20 većih sortiranih delova.
• Pokreni drugu prolazak objedinjavanja za spajanje 20 većih sortiranih delova.

Kao kod sortiranja u memoriji, efikasno spoljašnje sortiranje zahteva O (n log n) vremena: eksponencijalno povećanje količine podataka zahteva linearno povećanje broja prolazaka. Ako se liberalno koriste gigabajti RAM-a koje poseduju moderni računari, logaritamski faktor raste vrlo sporo: pod razumnim pretpostavkama, da je moguće sortirati 500 GB podataka pomoću 1 GB glavne memorije pre nego što treći prolazak postane prednost, a može sortirati mnogo puta pre nego što četvrti prolazak postane i koristan.

Podešavanje performansi

Sort Benchmark, kreiran od strane naučnika Džima Greja, upoređuje algoritme spoljaćnjeg sortiranja koristeći fino podešen hardver ili softver. Za ovo se koristi nekoliko tehnikaČ

• Korišćenje paralelizma
  • Više drajvova može biti paraleleno u cilju bržeg čitanja i pisanja. Ovo može biti veliki napredak u smislu efikasnosti.
  • Softver sortiranja može koristiti višestruke niti, da bi ubrzao proces na modernim računarima, koji poseduju više jezgara.
  • Softver može da koristi asinhroni U/I kako bi se samo prilikom prvog pokretanja podatka vršilo sortiranje ili objedinjavanje, a prolikom narednih pokretanja čitalo sa diska ili pisalo na disk.
  • Više mašina povezanih brzim mrežama mogu da sortiraju delove velike količine podataka paralelno.
• Povećanje brzine hardvera
  • Korišćenje RAM-a za sortiranje smanjiti broj zahteva diska i izbeći potrbu za većim brojem prolazaka.
  • Brza spoljašnja memorija, kao na primer 15K RPM, može ubrzati sortiranje(ali dodatno košta, proporcionalno sa veličinom podataka).
  • Mnogi drugi faktori mogu uticati na hardversku maksimalnu brzinu sortiranja: brzina procesora i broj jezgara, vreme pristupa RAM-u, širina ulaza/izlaza, brzina pisanja/čitanja sa diska, vreme zahteva diska. „Uravnotežavanje“ hardvera za smanjenje uskih grla je veoma važan deo prilikom dizajniranja efikasnog softvera za sortiranje.
  • Cena efikasnosti kao i apsolutna brzina mogu biti kritični, naročito u grupisanim sredinama gde niska cena čvora može dovesti do potrebe za potržnjiu još čvorova

• Povećanje brzine softvera
  • Neki od Sort Banchmark ulazi koriste varijaciju sortiranja višestrukim razvrstavanjem (eng. radix sort) za prvu fazu sortiranja : oni razdvajaju podatke u jedan od mnogih „korpi“ u odnosu na početnu vrednost.
  • Zbijanje ulaza, posrednih fajlova i izlaza može smanjiti vreme na U/I, ali nije dozvoljno u Sort Benchmark.
  • S obzirom da Sort Benchmark sortira zapise (100-bajta) koristeći kratke ključeve (10-bajta), softver

sortiranja ponekad preuređuje ključeve odvojeno od vrednosti da bi se smanjio opseg U/I memorije.

Drugi algoritmi

Spoljašnje sortiranje objedinjavanjem nije jedini algoritam spoljašnjeg sortiranja: postoje i sortiranja podelom, koja funkcionišu tako što se particionišu nesortirane vrednosti u manje „korpe“ i tada mogu da se sortiraju u glavnoj memoriji. Postoji dualnost ili osnovna sličnost između algoritama sortiranja baziranih na objedinjavanju i algoritama baziranih na podeli. Postoje algoritmi spoljašnjeg sortiranja u mestu, koji ne zahtevaju višak prostora na disku nego originalni podatak.

Spoljašnji linkovi

• Sort Benchmark