Спољашње сортирање

Спољашње сортирање је појам који се корист за класу алгоритама сортирања који садржати велике количине података. Спољашње сортирање се користи када подаци не могу да стану у главну меморију уређаја (најчешће РАМ), па уместо тога они морају бити смештени у спорију спољашњу меморију (обично тврди диск). Спољашње сортирање обично користи сортирање-обједињавање стратегију. У фази сортирања, делови податкака довољно мали да стану у главноу меморију се читају, сортирају, и исписују у привремени фајл. У фази обједињавања, сортирани подфајлови се спајају у један фајл.

Спољашњи алгоритам обједињавањем

Један од примера спољашњег сортирања је алгоритам спољашњег сортирања обједињавањем(енг. еxтернал мерге сорт), који сортира делове који могу да стану у РАМ-у, а онда их спаја. На пример за сортирање 900 мегабајта података коришћењем 100 мегабајта РАМ-а:

• Учитај 100 МБ података у главноу меморију и сортирај неком конвенционалном методом, као што је квиксорт.
• Упиши сортиране податке на диску.
• Понови кораке 1 и 2 док се сви подаци не налазе у сортиране делове од по 100 МБ (има 900МБ / 100 МБ = 9 делова), који сада треба бити спојене у једну излазну датотеку.
• Учитај првих 10 МБ (= 100 МБ / (9 цхункс 1)) сваког сортираног дела у улазне бафер у главној меморији и алоцирај преосталих 10 МБ за излазни буффер. (У пракси, боље перформансе би омогућило

прављење већег излазниг бафера, а мањег улазног бафера).

• Изводи 9-смерно обједињавање и смести резултат у излазни буффер. Ако је излазни бафер пун, упиши резултат у коначно сортирану датотеку, и испразните бафер. Ако било који од 9 улазних бафера постане празан, напунити га са следећих 10 МБ од додељених 100 МБ сортираног дела све док има доступних података из тог дела. Ово је кључни корак - јер алгоритам обједнињавањем пролази само једном

кроз сваки од делова, сваки део не мора бити учитан у потпуности, већ секвенцијално његови делови могу се учитати када је потребно.

Додатни пролаз

Овај пример приказује сортирање кроз два проласка: прво сортирање, а затим следи обједнињавање. Уочите да смо имали један пролаз који је спојио све делове одједном, за разлику од обичног сортирања обједињавањем, где обједињујемо по два дела у сваком кораку, и и потребно је лог н оваквих пролазака. Разлог за то је да сваки овакав пролазак захтева читање и писање сваке вредност из низ на диску и из диска истовремено. Приступање диску је обично споро, па читање и писање треба избегавати колико је год могуће.

Међутим, постоји пречице коришћењем мањег броја пролазка. Како се број делова повећава, количина података која може да се прочитати, на време из свако од делова током обједињавања, се смањује. За сортирање, рецимо, 50 ГБ у 100 МБ РАМ-а, користећи један пролазак није ефикасно: захтев диска да се улаyни бафер напуни подацима из сваког од 500 делова (читамо 100МБ / 501 ~ 200КБ из свког дела истовремено) узима већину времена сорта. Користећи два проласка решава проблем. Тада сортирање може изгледати овако:

• Покрените почетни пролазак сортирања делова као и пре.
• Покрени први пролазак обједињавања комбиновањем 25 делова истовремено, што доводи до 20 већих сортираних делова.
• Покрени другу пролазак обједињавања за спајање 20 већих сортираних делова.

Као код сортирања у меморији, ефикасно спољашње сортирање захтева О (н лог н) времена: експоненцијално повећање количине података захтева линеарно повећање броја пролазака. Ако се либерално користе гигабајти РАМ-а које поседују модерни рачунари, логаритамски фактор расте врло споро: под разумним претпоставкама, да је могуће сортирати 500 ГБ података помоћу 1 ГБ главне меморије пре него што трећи пролазак постане предност, а може сортирати много пута пре него што четврти пролазак постане и користан.

Подешавање перформанси

Сорт Бенцхмарк, креиран од стране научника Џима Греја, упоређује алгоритме спољаћњег сортирања користећи фино подешен хардвер или софтвер. За ово се користи неколико техникаЧ

• Коришћење паралелизма
  • Више драјвова може бити паралелено у циљу бржег читања и писања. Ово може бити велики напредак у смислу ефикасности.
  • Софтвер сортирања може користити вишеструке нити, да би убрзао процес на модерним рачунарима, који поседују више језгара.
  • Софтвер може да користи асинхрони У/I како би се само приликом првог покретања податка вршило сортирање или обједињавање, а проликом наредних покретања читало са диска или писало на диск.
  • Више машина повезаних брзим мрежама могу да сортирају делове велике количине података паралелно.
• Повећање брзине хардвера
  • Коришћење РАМ-а за сортирање смањити број захтева диска и избећи потрбу за већим бројем пролазака.
  • Брза спољашња меморија, као на пример 15К РПМ, може убрзати сортирање(али додатно кошта, пропорционално са величином података).
  • Многи други фактори могу утицати на хардверску максималну брзину сортирања: брзина процесора и број језгара, време приступа РАМ-у, ширина улаза/излаза, брзина писања/читања са диска, време захтева диска. „Уравнотежавање“ хардвера за смањење уских грла је веома важан део приликом дизајнирања ефикасног софтвера за сортирање.
  • Цена ефикасности као и апсолутна брзина могу бити критични, нарочито у груписаним срединама где ниска цена чвора може довести до потребе за потржњиу још чворова

• Повећање брзине софтвера
  • Неки од Сорт Банцхмарк улази користе варијацију сортирања вишеструким разврставањем (енг. радиx сорт) за прву фазу сортирања : они раздвајају податке у један од многих „корпи“ у односу на почетну вредност.
  • Збијање улаза, посредних фајлова и излаза може смањити време на У/I, али није дозвољно у Сорт Бенцхмарк.
  • С обзиром да Сорт Бенцхмарк сортира записе (100-бајта) користећи кратке кључеве (10-бајта), софтвер

сортирања понекад преуређује кључеве одвојено од вредности да би се смањио опсег У/I меморије.

Други алгоритми

Спољашње сортирање обједињавањем није једини алгоритам спољашњег сортирања: постоје и сортирања поделом, која функционишу тако што се партиционишу несортиране вредности у мање „корпе“ и тада могу да се сортирају у главној меморији. Постоји дуалност или основна сличност између алгоритама сортирања базираних на обједињавању и алгоритама базираних на подели. Постоје алгоритми спољашњег сортирања у месту, који не захтевају вишак простора на диску него оригинални податак.

Спољашњи линкови

• Sort Benchmark