Мундарижа Кириш

2.2.7. Кўп фазали саралаш усули

Айрим ҳолларда сараланадиган рўйхат компьютер хотирасига бутунлигича сиғмайдиган даражада катта бўлади. Кўп ҳолларда ёзув узунлиги калит узунлигидан етарлича ортиб кетади. Гоҳида ёзув узунлиги жуда катта ва икки ёзувни алмаштириш кўп вақт олади, алгоритм самарадорлиги таҳлили солиштиришлар сонини ва алмашишлар сонини ҳисобга олиши керак.

Айрим ҳолларда мумкин бўлган массивни эълон қилиш кифоя, бу ерда унинг ўлчами компьютер хотирасига киритиш ошиб бориши барча талаб этилаётган маълумотларни киритишга боғлиқ. У ҳолда операцион тизим виртуал хотирадан фойдаланади ва унинг фойдаланиш самарадорлигини ҳисобга олиш керак. Аммо бу ҳолатда ҳам оператив хотира ва дисклар ўртасида ўзаро алмашиниш аҳамиятга эга бўлиши мумкин. Ҳатто Quicksort каби самарадор саралаш алгоритмларида бўлиниш қисмлари ва мантиқий хотира блоки узунлиги ўртасидаги муносабат катта сондаги блокларни қайта ёзишга олиб келади. Бундай муаммолар кўпинча дастур компьютерда ишлатиб кўрилгунга қадар англанилмайди, шу билан бирга унинг ишлаш тезлиги қаноатлантирмаганлиги сабабли, тор жойларни аниқлаш учун техник таҳлил воситаларидан фойдаланилади. Ҳатто бу ҳолатда ҳам таҳлил натижа бермаслиги мумкин, операцион тизим виртуал хотирада алмашишларнинг изланиш инстурментларини кўрсатмайди.

Саралаш алгоритмларининг самарадорлигини аниқлаш учун биз у томонидан бажарилган солиштиришларни санаб чиқдик. Лекин виртуал хотирада диск блокларида ўқиш ёки унга ёзиш бўйича ишнинг ҳажми мантиқий ва арифметик операцияларнинг мураккаблигини етарли даражада ошириши мумкин. Бу иш операцион тизим томонидан бажарилади ва шунинг учун унинг самарадорлига таъсир қилувчи реал воситалар бизда мавжуд эмас.

Бошқа ёндашишда файлга рухсат этилган файллардан фойдаланишимиз мумкин ва керакли позицияга навбатдаги ўқиш блокидан чиқиш учун файлда қидириш амаллари массивга бевосита мурожаатни алмаштириш керак. Натижада ишлатилаётган мантиқий хотира ўлчами кичраяди, демак виртуал хотирадаги бошқарилмайдиган юклама камаяди. Киритиш – чиқариш операциялари ҳажми ҳоҳ биз ёки ҳоҳ операцион тизим бошқарсин, барибир аҳамиятга эга.

Натижада юқорида кўрилган бўлимлардаги саралаш алгоритмлари катта ҳажмдаги маълумотларда амалиётга яроқсиз бўлиб қолади. Энди бошқа имкониятга эътиборимизни қаратимиз: бизда тўртта файл ва уларни бирлаштириш воситаси мавжуд бўлсин.

Аввало оператив хотирада бир вақтнинг ўзида сақлаш мумкин бўлган ақлли ёзувлар сонини баҳолаймиз. Бу катталикка тенг бўлган S узунликдаги массивни эълон қиламиз: бу массив саралашнинг икки босқичида қўлланилади. Биринчи қадамда биз S ёзувларни ўқиймиз ва мос ички саралаш ёрдамида саралаймиз. Бу сараланган ёзувларни А файлга қайта ёзамиз. Кейин яна S ёзувларни ўқиймиз, саралаймиз ва уни В файлга ёзамиз. Бу жараён сараланган ёзув блоклари гоҳ А файлга, гоҳ В файлга алмашиниб ёзилгунга қадар давом этади. Биринчи босқични амалга оширувчи алгоритм қуйидагича:
CreateRuns(S)

S тузиладиган бўлаклар ўлчами

CurrentFile=A

while кирувчи файл охирга етмаган do

read кирувчи файлдан S ёзувларни

sort S ёзувларни

if CurrentFile=A then

CurrentFile=B

else

CurrrentFile=A

end if

end while

Кирувчи файл сараланган бўлакларга тўлиқ бўлингандан сўнг, иккинчи қадамга ўтсак бўлади, яъни бу бўлакларнинг бирлаштиришга ўтсак бўлади. А ва В фаайллардан ҳар бири қандайдир сараланган бўлаклар кетма – кетлигидан таркиб топган, аммо бирлаштириб саралашдаги каби биз иккита турли бўлакларда ёзувларнинг тартиби ҳақида ҳеч нарса дея олмаймиз.

Бирлаштириш жараёни худди MergeLists функциясига ўхшаш бўлади, аммо олдин ёзувлар янги массивга ёзилган бўлса, энди уларни янги файлга ёзамиз. Шунинг учун А ва В файллардан дастлабки яримталик бўлакларни ўқишдан бошлаймиз. Фақатгина яримта бўлакларни ўқиймиз, негаки биз аниқладикки, хотирада бир вақтнинг ўзида фақат S ёзувлар жойлашиши мумкин, бизга эса иккала файллардаги ёзувлар керак. Энди бу ярим бўлакларни битта С бўлак файлига бирлаштирамиз. Иккала файлдаги ярим бўлаклардан бири тугаганидан кейин, биринчи бўлак қолган файлдан ўқилади ва иккинчи ярим бўлак ҳам худди шу файлдан ўқилади. Бўлаклардан бирини қайта ишлаш тугагач, иккинчи бўлакнинг охири С файлга ёзилади. Шундан сўнг А ва В файлларнинг биринчи икки бўлакси бирлашуви тугагач кейинги икки бўлак D файлда бирлашади. Бўлакларнинг бирлашишининг бу жараёни бирлашган бўлаклар ёзувлари гоҳ С файлга, гоҳ D файлга алмашиниб ёзилгунга қадар давом этади. Натижада биз 2S узунликдаги сараланган бўлакларга бўлинган иккита файлга эга бўламиз. Кейин бу жараён такрорланади, яъни бўлаклар С ва D файллардан ўқилади ва бирлашган 4S узунликдаги бўлаклар эса А ва В файлларга ёзилади. Кўриниб турибдики, оқибатда бўлаклар файллардан бирида сараланган рўйхатга бирлаштирилади. Иккинчи қадамни амалга ошириш алгоритми қуйидагича:

PolyPhaseMerge(S)

S дастлабки бўлаклар ўлчами

Size=S

Input1=A

Input2=B

CurrentOutput=C

while not done do

while бўлаклар тугамаган do

Input1 файлидаги Size узунликдаги бўлакни

Input2 файлидаги Size узунликдаги бўлак билан бирлаштириш

натижани CurrentOutput га ёзиш

if (CurrentOutput=A) then

CurrentOutput=B

elsif (CurrentOutput=B) then

CurrrentOutput=A

elsif (CurrentOutput=C) then

CurrrentOutput=D

elsif (CurrentOutput=D) then

CurrrentOutput=C

end if

end while

Size=Size*2

if (Input1=A) then

Input1=C

Input2=D

Current Output=A

else

Input1=A

Input2=B

CurrentOutput=C

end if

end while

Таҳлил қилишдан олдин қандай миқдордаги бўлаклар билан иш олиб боришимизни ва бу миқдор ўтишлар сонига қанчалик таъсир этишини қараймиз. Агар дастлабки файлда N ёзувлар ва хотирага бир вақтнинг ўзида 5 та ёзув сиғса, у ҳолда CreateRuns процедураси бажарилганидан сўнг биз икки файлга тақсимланган бўлакларга эга бўламиз. PolyPhaseMerge алгоритмининг ҳарбир ўтишида бўлаклар жуфти бирлаштирилади, шунинг учун бўлаклар сони икки баравар кўпаяди. Биринчи ўтишдан сўнг бўлаклар, иккинчидан сўнг— бўлаклар бўлади ва умумиё ҳолда, j- ўтишдан кейин бўлаклар бўлади. Агар битта бўлак қолса иш тугайди, яъни D ўтишдан сўнг, бунда яъни да. Бу шуни билдирадики, алгоритм ўз ишини бирлаштириш жараёнида ўтишдан сўнг тўхтатади.