Материал: Інформатика_1 (методи побудови алгоритмівта та їх аналіз)

Завдання

1. Розробити програму побудови ідеально збалансованого де­рева, елементами якого є цілі числа, що читаються з текстово­го файла. Передбачитй виведення вмісту побудованого дерева на екран монітора.

2. Розробити програму побудови ідеально збалансованого де­рева, елементами якого є слова, що читаються з текстового файла. Передбачитй виведення вмісту побудованого дерева на екран монітора.

3. Розробити програму побудови дерева пошуку, елементами якого є цілі числа, що читаються з текстового файла. Пе­редбачитй виведення вмісту побудованого дерева на екран мо-нітора.

4. Розробити програму побудови дерева пошуку, елементами якого є слова, що читаються з текстового файла. Передбачитй виведення вмісту побудованого дерева на екран монітора.

5. Розробити діалогову меню-орієнтовану програму роботи з елементами дерева пошуку за такими пунктами:

1. записати новий елемент у дерево;

2. прочитати заданий елемент із дерева;

3. вивести вміст дерева на екран монітора;

4. завершити роботу з деревом.

6. Протестувати розроблену програму в завданні 5, спостері- гаючи за вмістом побудованого дерева пошуку, за такою схемою:

95

• записати новий елемент у дерево;

• прочитати елемент дерева пошуку, що є термінальною вершиною;

• прочитати елемент дерева пошуку, що мае лише правого нащадка;

• прочитати елемент дерева пошуку, що мае лише лівого нащадка;

• прочитати елемент дерева пошуку, що мае двох нащадків і не е коренем дерева;

• прочитати елемент дерева пошуку, що мае двох нащадків і е коренем дерева.

7. Зробити письмовий аналіз виконання завдань 5, 6.

ХЕШ-ТАБЛИЦЯ

3 англійської мови слово hash перекладаеться «рубати», «кришити». Такий переклад справді відповідає ідеі', покладе-ній в основу структури даних «хеш-таблиця».

Ми з вами вже знаемо, що у випадку обробки великої кіль-кості інформації з її елементів можна утворити список. У цій структурі даних визначені операції пошуку, додавання та ви-лучення елементів, що носять назву «словникових». Однак список е структурою послідовного доступу, що зі збільшенням кількості елементів списку значно погіршує в часі виконання зазначених операцій. Який вихід у цьому разі можна запро-понувати? Зрозуміло, що чим менший список, тим швидше у ньому здійснюється пошук. Тому давайте розіб'ємо його на частини. Тепер послідовність пошуку буде такою: спочатку треба лише визначити, в якій із цих частин міститься шуканий елемент, а потім знайти його.

Наступний матеріал буде присвячений питаниям визначен-ня алгоритмів поділу інформації на окремі частини та прин­ципу організацїї такої побудови інформащї.

Розглянемо задачу створення словника. За традицією всі слова, наприклад, українського словника розбиті на групи за алфавітом: першою е група слів на літеру «А», потім на літеру «Б» і т. д. Тому знайти потрібне слово у словнику просто. Однак у будь-якому словнику кожна така група містить різну кіль-кість слів, і це визначає нерівномірний розподіл слів у трупах. А тому в одних трупах, наприклад у словах на літеру «Є», по­шук здійснюватиметься швидше, а в інших - набагато довше, наприклад у словах на літеру «А». Давайте запам'ятаемо цю особливість побудови словників, на яку ми зараз звернули ува-гу, і повернемося до цього факту трохи пізніше.

96

Щоб не склалася думка про те, що подібний поділ на групи можна використовувати лише для елементів, якими є слова, наведемо приклади іншої інформації, що може оброблятися по-дібним чином. Можна розглядати також числову інформацію, інформацію про кадри підприємства, про учнівський колектив школи, множину ідентифікаційних кодів громадян держави тощо. Якщо наведена на початку словникова інформація є мно-жиною елементів типу string, то наступна - будь-який число-вий тип, а останні приклади є інформацією, що описуються ти­пом record.

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

Введемо поняття ключа key(x) елемента х, що призначений для його ідентифікації. Найчастіше елемент динамічної мно­жини - це запис, що складається з кількох полів. Саме одним із полів і є ключ даного елемента. Інші поля - це додаткова ін-формація про елемент: його значения, покажчик на наступний за ним елемент, на попередній елемент тощо.

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

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

У термінах введеного поняття ключа елемента можна гово­рити про розв'язання поставлено! задачі. Платформою для цьо­го буде створення масиву, порядковии номер якого збігається з ключей елемента задано* множини, а вмістом - покажчик на цей елемент, тобто його адреса в пам'яті комп'ютера: А[кеу(х)] = х. У цьому разі доступ до елементів буде набагато швидшим, а саме — прямим. Такий спосіб організації вхідної інформації називається прямою адресацією (мал. 34).

4 Інф..|іиатіп.іі 'І Юіел 97

о

1

2 3

4 б б 7 8

9

Мал. 34

На малюнку сірим кольором позначені ті елементи масиву, які мають посилання на nil, тобто у множині немає елементів, ключ яких збігається з цим порядковим номером елемента масиву А. Однак зрозуміло, що при великій кількості вхідної інформації можуть виникнути проблеми з розміщенням у па-м'яті. Саме в цьому і полягає досить очевидний недолік прямої адресації:

• коли множина всіх можливих ключів велика, то зберігати в пам'яті такий масив непрактично, а інколи й неможливо;

• якщо число реально існуючих у таблиці записів менше за кількість її елементів, то в цьому випадку пам'ять використо-вується неефективно.

Розглянемо іншу стратегію організації збереження інфор-мації. Нехай існує такий алгоритм визначення ключів елемен-тів, при якому всю їх множину можна поділити на групи, в яких елементи мають однаковий ключ. Назвемо ці групи сег­ментами. Для того щоб зберігати елементи сегментів, вико-ристаємо списки. Отримаємо фактично масив посилань на ад-реси списків елементів, що мають однаковий ключ.

Використанням ідеї застосування списків для елементів з однаковими ключами ми вирішили колиию, яка полягає у то­му, що декілька елементів матимуть однаковий ключ.

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

На малюнку 35 видно, що не всі ключі, передбачені в ма-сиві А, притаманні елементам задано!' множини.

98

Мал. 35

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

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

Проаналізувавши всі можливі ситуації щодо поділу елемен-тів заданої множини на групи, можна дійти висновку, що в найгіршому випадку при хешуванні списками може трапи-тися, що ключі всіх елементів збігаються і таблиця зводиться до одного списку довжини N. Зрозуміло, що в такому разі хе­шування беззмістовне.

Яким чином інформація, що міститься у хеш-таблиці, відоб-ражаеться на пам'ять комп'ютера? Ми, фактично, поділили всю множину елементів на окремі підмножини (списки), роз-містили їх у динамічній пам'яті і записали адреси їх початків у одновимірний масив. Отже, в пам'яті комп'ютера буде роз-мщений одновимірний масив, елементами якого будуть зна­чения адрес початків відповідних списків. Якщо реалізація хеш-таблиці проходитиме в середовищі Turbo Pascal 7.0, то кожний елемент такого масиву займатиме 4 байти, а довжина його може бути майже 16 000 елементів. Саме стільки списків може бути використано і в хеш-таблиці. Зважаючи на те, що кожний список реалізується в окремому сегменті розміром 64 Кб, можна уявити собі і розміри задано! множини значень, для обробки яких застосована хеш-таблиця.

I

99

Тепер перейдемо до розгляду питания про принцип ПОДілу заданої множини елементів на групи.

Нехай якимось чином ми визначили, що при загальній кількості слів N списків елементів може бути не більш як т. Пронумеруємо їх від 0 до т - 1. Зазначимо, що у випадку рів-номірного розподілу в списках може бути по N/m елементів. Тоді схематично базова структура при відкритому хешуванні виглядатиме так (мал. 36):

О

1

от-1

Мал. 36

Надалі будемо казати, що масив, який називаеться таб­лицею сегментів (hash table) і проіндексований номерами сег-ментів О, 1, ..., т ~ 1, містить заголовки для т списків.

Опис хеш-таблиці виглядатиме так:

type segment = "seg; seg = record

element: integer; next: segment; end; hash = array[0.. 99] of segment;

Перейдемо до обговорення питания про визначення найоп-тимальнішого алгоритму поділу задано! множини елементів на сегменти-списки, тобто максимально рівномірного їх розподі-лу по списку.

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

Нагадаемо приклад розподілу слів у словнику, що був наве­дений вище. При поділі слів на групи за першою літерою ці гру­пи матимуть різну кількість слів і пошук у них здійснювати-меться не однаково швидко. Чи можна ці слова поділити за якоюсь іншою ознакою? Так, можна.

100

Зрозуміло, що найефективнішим пошук буде в тому разі, якщо сегменты матимуть максимально рівні розміри. Як ми вже зазначали вище, якщо задана множина складається з N елементів, тоді середня довжина списків повинна бути N/m. Причому чим ближче буде т до N, тим меншими будуть роз-міри сегментів і тим швидше здійснюватиметься пошук необ­идного елемента.

Надалі будемо говорити, що деякий елемент х і-го списку -це елемент заданої множини, для якого h(x) • і. Тобто існує деяка залежність — хеш-функція h(x), що для кожного елемен­та визначає порядковии номер сегмента-списку, в якому він міститься.

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

h(x) = xmodm.

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

Розглянемо приклад побудови хеш-таблиці для множини з 2000 елементів. Як визначити просте число, яке б підійшло найкращим чином? Якщо нас зможе влаштувати варіант, коли у кожному сегменті буде в середньому три елементи, то в якос-ті значения т можна взяти 701. Це можна пояснити тим, що 701 ~ 2000/3 і воно не є степенем двійки: h(x) = х mod 701.

Ще один алгоритм побудови хеш-функції базується на ме­тод! множення і полягае в наступному. Нехай кількість хеш-значень дорівнює т. Зафіксувавши константу К в інтервалі (0; 1), визначимо функцію так:

h (х) = trunc(m * frac(K * х)), де frac(K * х) - дробова частина К * х.

Яким же повинно бути значения константи К7 Взагалі метод множення спрацьовує при будь-яких значеннях К, але деякі з них можуть бути кращими за інші. Дональд Кнут, автор відо-мого тритомного видання «Мистецтво програмуваиня для ЕОМ», у результаті своїх досліджень дійшов висновку, що най-

>/5-1 кращим буде значения К 0,6180339887...

Наведемо приклад обчислення значения хеш-функщї ме­тодом множення для х = 123 456 і т = 10 000:

101

h( 123456) =trunc( 10000 " frac(0. 6180339887 * 123456)) = trunc( 10000 * frac (76300. 0041089472)) = trunc( 10000 " 0. 0041089472) = 41.

Зрозуміло, що при застосуванні обох алгоритмів обчислення хеш-значень вони попадатимуть до інтервалу цілих чисел [0; т - 1].

Хеш-функція для елементів множини, що є цілими числа­ми, в термінах Pascal-програми буде такою:

function h (х: integer): 0.. m - 1; begin

h := <метод обчислення функції> end;

У випадку, коли елементами множини є слова, можна запропонувати такий алгоритм побудови хеш-функції: підсу-муємо всі цілочислові коди символів кожного елемента-слова, використовуючи стандартну функцію ord(x), і до результату підсумовування застосуємо певний алгоритм:

function h (х: string): 0.. m - 1; vari, sum: integer; begin

sum := 0;

for i := 1 to length(x) do sum := sum + ord(x[i]); h := <метод обчислення функції > end;

Шдсумуємо наведені пояснения. За задании ключем х і хеш-функцією h(x) можна визначити номер сегмента i, якому на-лежить пей ключ. А це, у свою чергу, дає нам змогу визначити адресу початку списку А[і], в якому розміщені елементи даного сегмента.

Перейдемо до розгляду основних операцій над елементами хеш-таблиць.

Перш за все необхідно підготувати масив посилань на сег­мента, де знаходяться списки елементів множини:

procedure MakeNull (var A: hash); var i: integer; begin

for i := 0 to m - 1 do A[i] := nil end;

Пошук елемента в хеш-таблиці здійснюється за такою послі-довністю дій:

102

function find (x: string; A: hash): boolean; var current: segment; begin

{Визнзчення адреси початку сегмента, де може знаходитись х.} current := A[h (х) ];

find := true; {Початкове значения функції - true.}

while (current <> nil) and (current".element <> x) do

current := current".next; {Пошук у списку елемента х.}

{Якщо елемент не знайдено, повертасмо false.} if current = nil then find := false; end;

Запис, або вставления, нового елемента в хеш-таблицю за відсутності його в ній раціональніше робити у відповідний сег­мент на самому його початку:

procedure ins (х: string; var A: hash);

{Оскільки хеш-таблиця зміниться, використовуємо var A.} var і: word;