ЗНАЙОМСТВО З СОРТУВАННЯМ ФАЙЛІВ

1. Збалансоване злиття

В реальних задачах виникають послідовності, що зберігаються в файлах і не можуть уміщатися в оперативній пам'яті у вигляді масивів. Наприклад, у великому місті може бути кілька мільйонів абонентів телефонної мережі. Звичайно, для швидкого пошуку дані про абонентів мають бути відсортованими. Виникає задача сортування файлів за умови, що файли цілком не можна подавати в оперативній пам'яті. Таке сортування називається зовнішнім.

Один із найпростіших методів зовнішнього сортування має назву збалансованого злиття. Розглянемо його ідею.

Нехай F1 є файлом однотипних значень. Відрізком у ньому називається послідовність елементів, упоpядкована за зростанням значень, яка не є частиною іншої упорядкованої послідовності. Наприклад, у послідовності <2, 8, 3, 7, 6, 5, 3, 4, 1> є шість відрізків: <2, 8>, <3, 7>, <6>, <5>, <3, 4>, <1>.

Спочатку відpізки по черзі копіюються в допоміжні файли F3 і F4. Це первинне копіювання називається розподілом. У нашому прикладі маємо <2, 8, 6, 3, 4> в F3 і <3, 7, 5, 1> в F4.

Потім паpи перших, других тощо відpізків файлів F3 і F4 зливаються в довші відpізки та по черзі копіюються в F1 і допоміжний файл F2. У нашому прикладі маємо <2, 3, 7, 8, 1, 3, 4> в F1 та <5, 6> в F2. Цей крок називається злиттям. Потім паpи відpізків файлів F1 і F2 зливаються у файли F3 і F4 тощо доти, поки в результаті чергового злиття не утвориться єдиний відрізок.

Якщо перед черговим кроком злиття було M відрізків, то після нього їх стає не більше, ніж  (M+1)/2 . Звідси випливає, що таких кроків не більше  log₂N , де N – кількість елементів файла. Оскільки на кожному кроці злиття відбувається переписування всіх N елементів у інші файли, то складність такого алгоритму сортування можна оцінити як O(Nlog₂N).

Можна збільшити кількість допоміжних файлів. Наприклад, якщо зливати не дві, а три послідовності, то кількість відрізків буде зменшуватися не менше, ніж утричі, тому кроків злиття буде не більше  log₃N , що в log₂3, тобто приблизно в півтора раза менше. Для цього будуть потрібні 5 допоміжних файлів.

Взагалі, використання 2k-1 допоміжних файлів вимагатиме не більше  log_kN кроків злиття. Отже, "розширення фронту" злиття є одним із джерел прискорення сортування.

З іншого боку, чим довшими будуть відрізки в початковому файлі, тим менше кроків злиття буде потрібно. Звідси створення початкового файла з якомога довшими відрізками також може суттєво прискорити сортування. Саме цю ідею ми розглянемо докладніше в наступному підрозділі.

2. Вибір із заміщенням

Тут ми опишемо створення файла з якомога довшими відрізками. Скористаємося методом, що належить Сьюворду та Думі, із удосконаленням Фрейзера та Уона (посилання див. у книзі [Кн3]). Цей метод грунтується на використанні дерева сортування.

Нехай початковий файл містить значення упорядкованого типу T. За цим файлом будується результатний файл із неспадаючими відрізками. При побудові використовується масив A із MX елементів. Нехай із початкового файла в цей масив прочитано n елементів, n MX. Як і в алгоритмі пірамідального сортування (підр.17.4.2), будемо дивитися на масив як на дерево. Елемент масиву розглядається як вузол дерева, і кожний вузол, індекс якого k, є батьком вузлів із індексами 2k та 2k+1, де k<ndiv2 (рис.17.1), решта вузлів є листками дерева. За парного n вузол із індексом ndiv2 має лише одного сина – вузол n.

Нехай значення масиву розташовано таким чином, що значення кожного елемента-батька не більше значень елементів-синів, тобто за k=1, 2, … , n div 2 справджується

A[k]  A[2*k] та A[k]  A[2*k+1] (18.1)

Отже, перший елемент масиву має найменше значення, і його можна вивести в файл, у якому будуються неспадаючі відрізки. Після цього можна замістити це значення наступним із початкового файла та відновити властивість (18.1) у масиві. Звичайно, якщо нове значення менше виведеного, то його доведеться виводити вже в наступний відрізок результатного файла. В такому разі це значення не заміщає виведене, а запам'ятовується в додатковому сховищі. Коли в цьому сховищі накопичиться MX елементів, тоді виведемо елементи масиву A у порядку неспадання в результатний файл без їх заміщення новими. Після цього скопіюємо зміст сховища в масив, розташуємо значення в ньому згідно (18.1) і продовжимо виводити їх у порядку неспадання, заміщаючи їх значеннями з початкового файла.

Коли початковий файл буде прочитано, тоді ми виведемо зміст масиву в результатний файл і заповнимо масив із сховища. Після цього упорядкуємо його згідно (18.1) і знову виведемо його.

Уточнення наведеного опису почнемо з подання даних. Нехай тип елементів файла має ім'я T. Означимо типи файлів та масиву типу T:

type FoT=file of T; ArrT=array [1..MX] of T;

При сортуванні дуже часто виконується обмін місцями значень елементів масиву. Оскільки розміри елементів файла можуть бути великими, обмін місцями таких значень буде займати чимало часу. Спробуємо скоротити цей час, заплативши за це витратами пам'яті.

Нехай A – глобальний масив типу ArrT, і в ньому зберігаються n значень із початкового файла f, n  MX. Для подання дерева з властивістю (18.1) означимо додатковий глобальний масив P. У ньому зберігаються індекси елементів масиву A, тобто елементи масиву P своїми значеннями вказують на елементи масиву A. Властивість (18.1) відтворюється такою перестановкою значень масиву P, що за k=1, 2, … , n div 2

A[P[k]]  A[P[2*k]] та A[P[k]]  A[P[2*k+1]] (18.2)

Таким чином, виведення значення першого елемента масиву в результатний файл g задається як write(g, A[P[1]]). Замість обміну місцями значень у масиві A відбувається обмін значень у масиві P, заданий процедурою indswap:

procedure indswap(i, k : Longint);

var v : Longint;

begin

v := P[i]; P[i] := P[k]; P[k] := v.

end;

Із описання розв'язання нашої задачі побудови файла з якомога довшими відрізками неважко виділити окремі підзадачі та задати їх розв'язання підпрограмами.

Однією з підзадач є "заповнити масив змістом сховища". Реалізуємо сховище додатковим файлом типу T. Нехай копіювання значень із нього в масив задає процедура із заголовком

procedure copyfa(var f : FoT; var A : ArrT; var m : Longint);

Третій параметр служить для повернення кількості скопійованих значень. Оскільки сховище має таке саме подання, що і початковий файл, цією процедурою можна скористатися і для початкового заповнення масиву з файла.

Наступна підзадача – "вивести елементи масиву A у порядку неспадання в результатний файл без їх заміщення новими". Нехай це виведення задає процедура outtree із заголовком

procedure outtree(var f : FoT; var A : ArrT; m : Longint);

Для подальшого уточнення алгоритму скористаємося підпрограмами підрозділу 17.4.2, дещо змінивши їх із урахуванням подання даних.

Нехай процедура з заголовком indbld(m:Longint) задає початкову перестановку значень масиву P таким чином, що виконується умова (18.2). Нехай процедура indreorg(i,k:Longint) задає відновлення властивості (18.2) у частині масиву A[P[i]], … , A[P[k]].

З використанням усіх указаних підпрограм уточнимо алгоритм. Нехай змінна n зберігає кількість значень, скопійованих у масив A, ch – кількість значень, записаних у сховище, подане файлом h. Нехай last – останнє значення, виведене в результатний файл. Не записуючи всіх означень, наведемо основну частину програми:

copyfa(f, A, n); indbld(n); ch:=0;

while (n>0) and not eof(f) do

begin

last:=A[P[1]]; write(g, last);

read(f, A[1]);

if (A[1] < last) and (ch < MX) then

begin write(h, A[1]); ch:=ch+1 end

else

if A[1] < last then {ch=MX}

begin

outtree(g, A, n);

copyfa(h, A, n); ch:=0;

indbld(n);

end

else {A[1]  last}indreorg(1, n)

end;

if n > 0 then outtree(g, A, n);

if ch > 0 then

begin

copyfa(h, A, n); ch:=0;

indbld(n); outtree(g, A, n)

end

Із зазначених вище підпрограм уточнимо лише процедуру outtree, решта залишаються вправами (див.підр.17.4.2).

procedure outtree(var f : FoT; var A : ArrT; m : Longint);

begin

while m>3 do

begin

write(g, A[P[1]]); indswap(1, m);

m:=m-1; indreorg(1, m);

end;

write(g, A[P[1]]);

if m=3 then

if A[P[2]] > A[P[3]] then indswap(2, 3);

if m > 1 then write(g, A[P[2]]);

if m=3 then write(g, A[P[3]])

end

Задача

18.1. Написати програму сортування файла на основі ідей, описаних у підр.18.1–18.2.

3. Індексові файли

Почнемо з прикладу. Дані про абонента телефонної мережі включають в себе його номер, прізвище, адресу та багато іншої інформації. Шукати дані про абонента доводиться, наприклад, як за його номером, так і за прізвищем. А пошуки у відсортованому файлі значно швидші, ніж у невідсортованому. Отже, за значеннями якого з полів – номера чи прізвища – слід сортувати файл?

Відповідь на це питання дає застосування так званих індексових файлів. Розглянемо послідовність пар із рядків і чисел:

<("qw", 31), ("er", 86), ("ty", 12), ("io", 24)>.

Якщо замінити пари їх номерами (індексами) у послідовності, то упорядкування пар за алфавітним зростанням їх рядків має вигляд <2, 4, 1, 3>, тобто найменшим є "er" із пари 2, наступним – "io" із 4 тощо. Така послідовність номерів і є змістом індексового файла, відповідного цій послідовності пар за упорядкуванням рядків. Водночас, можна так само упорядкувати пари за зростанням чисел: <3, 4, 1, 2>, і це буде змістом іншого індексового файла.

Отже, значеннями елементів індексового файла є номери (або інші позначення) елементів основного файла. Перший елемент індексового файла вказує на найменший із елементів основного файла за деяким їх упорядкуванням, другий – на наступний тощо, останній – на найбільший. Якщо елементи основного файла мають багато полів, то для нього можна створити кілька різних індексових файлів.

Індексові файли дозволяють взагалі не сортувати основний файл. У випадку, коли його елементи складаються сотнями й тисячами байтів, таке сортування надто дороге. Індексові ж файли складаються з цілих, і їх сортування, як правило, можна здійснити, представивши їх зміст у масиві.

Отже, використання індексових файлів дозволяє одночасно розглядати той самий файл як упорядкований за значеннями кількох різних полів його записів. Саме це дозволяє вести швидкий пошук у ньому за кількома різними ключами.

Задачі

2. Написати пpоцедуpу побудови індексового файла за файлом записів.

3. Написати пpоцедуpу виведення записів типізованого файла за зростанням значень указаного поля (з використанням індексового файла).

4. Написати процедуру зміни індексового файла при

а) додаванні б) вилученні

записів основного файла.