Головна

Тема 3. Статичні структури даних

  1.  A) Структури пакетів прикладних програм
  2.  A. Для остаточного висновку не вистачає даних.
  3.  Системи управління базами даних наступного покоління
  4.  I Створення таблиць бази даних
  5.  III. Опис зовнішніх схем баз даних
  6.  IV. АНАЛІЗ СКЛАДУ І СТРУКТУРИ пасивів балансу.
  7.  SKIP-технологія і криптопротоколів SSL, S-HTTP як основний засіб захисту з'єднання та даних, що передаються в мережі Internet

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

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

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

3.1. вектори

ЛОГИЧЕСКАЯ СТРУКТУРА. Вектор (одновимірний масив) - структура даних з фіксованим числом елементів одного і того ж типу. Кожен елемент вектора має унікальний в рамках заданого вектора номер. Звернення до елементу вектора виконується по імені вектора і номером необхідного елемента.

Машинне подання. Адресації ЕЛЕМЕНТІВ СТРУКТУР. Елементи вектора розміщуються в пам'яті в поспіль розташованих комірках пам'яті. Під елемент вектора виділяється кількість байт пам'яті, яке визначається базовим типом елемента цього вектора. Розмір пам'яті для зберігання вектора визначається твором довжини елемента на число елементів.

У мовах програмування вектор представляється одновимірним масивом з синтаксисом опису виду (Pascal):

Ім'я: array [n..k] of тип;

де n-номер першого елемента, k-номер останнього елемента.

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

Кількість байтів безперервної області пам'яті, зайнятих одночасно вектором, визначається за формулою:

ByteSise = (k - n + 1) * Sizeof (тип)

Звернення до i-того елемента вектора виконується за адресою вектора плюс зміщення до даного елементу. Зсув i-ого елемента вектора визначається за формулою:

ByteNumer = (i- n) * Sizeof (тип),

а адресу його: @ ByteNumber = @ ім'я + ByteNumber.

де @ ім'я - адреса першого елемента вектора.

При доступі до вектору задається ім'я вектора і номер елемента вектора. Таким чином, адреса i-го елемента може бути обчислений як:

@ Ім'я [i] = @ Ім'я + i * Sizeof (тип) - n * Sizeof (тип) (3.1)

Це обчислення не може бути виконано на етапі компіляції, так як значення змінної i в цей час ще невідомо. Отже, обчислення адреси елемента повинно проводитися на етапі виконання програми при кожному зверненні до елементу вектора.

Але для цього на етапі виконання, по-перше, повинні бути відомі параметри формули (3.1): @ Ім'я Sizeof (тип), n, а по-друге, при кожному зверненні повинні виконуватися дві операції множення і дві - складання. Перетворивши формулу (3.1) в формулу (3.2), отримаємо:

@ Ім'я [i] = A0 + i * Sizeof (тип) Щ (3.2)

A0 = @ Ім'я - n * Sizeof (тип) и

Таким чином, число збережених параметрів скорочується до двох, а число операцій - до одного множення і одного складання, так як значення A0 може бути обчислено на етапі компіляції і збережено разом з Sizeof (тип) в дескрипторі вектора. Зазвичай в дескрипторі вектора зберігаються і граничні значення індексів. При кожному зверненні до елементу вектора задане значення порівнюється з граничними і програма аварійно завершується, якщо заданий індекс виходить за допустимі межі. Інформація, що міститься в дескрипторі вектора, дозволяє, по-перше, скоротити час доступу, а по-друге, забезпечує перевірку правильності звернення. Але за ці переваги доводиться платити, по-перше, швидкодією, так як звернення до дескриптора - це команди, по-друге, пам'яттю як для розміщення самого дескриптора, так і для команд, з ним працюють.

3.2. масиви

3.2.1. логічна структура

Масив - така структура даних, яка характеризується:

- Фіксованим набором елементів одного і того ж типу;

- Кожен елемент має унікальний набір значень індексів;

- Кількість індексів визначають рівномірність масиву, наприклад, два індексу - двовимірний масив, три індексу - тривимірний масив, один індекс - одномірний масив або вектор;

- Звернення до елементу масиву виконується по імені масиву і значенням індексів для даного елемента.

Інше визначення: масив - це вектор, кожен елемент якого - вектор.

Синтаксис опису масиву представляється у вигляді:

Ім'я: Array [n1..k1] [n2..k2] .. [nn..kn] of Тип.

Для випадку двовимірного масиву:

Mas2D: Array [n1..k1] [n2..k2] of Тип, або

Mas2D: Array [n1..k1, n2..k2] of Тип

Наочно двовимірний масив можна представити у вигляді таблиці з (k1-n1 + 1) рядків і (k2-n2 + 1) стовпців.

3.2.2. фізична структура

Багатовимірні масиви зберігаються в безперервній області пам'яті. Кількість елементів масиву і розмір елемента визначають розмір пам'яті для зберігання масиву. Принцип розподілу елементів масиву в пам'яті визначено мовою програмування. Так в FORTRAN елементи розподіляються по стовпцях - так, що швидше змінюється ліві індекси, в Pascal - по рядках - зміна індексів виконується в напрямку справа наліво.

Кількість байтів пам'яті, зайнятих двовимірним масивом, визначається за формулою:

ByteSize = (k1-n1 + 1) * (k2-n2 + 1) * SizeOf (Тип) (3.3)

Адресою масиву є адреса першого байта початкового компонента масиву. Зсув до елементу масиву Mas [i1, i2] визначається за формулою:

ByteNumber = [(i1-n1) * (k2-n2 + 1) + (i2-n2)] * SizeOf (Тип) (3.4)

його адреса: @ByteNumber = @mas + ByteNumber.

3.2.3. операції

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

Відповідно до формулами (3.3), (3.4) і за аналогією з вектором (3.1), (3.2) Для двовимірного масиву з межами зміни індексів:

[B (1) .. E (1)] [B (2) .. E (2)], розміщеного в пам'яті по рядках, адреса елемента з індексами [I (1), I (2)] може бути обчислений як :

Addr [I (1), I (2)] = Addr [B (1), B (2)] +

+ {[I (1) -B (1)] * [E (2) -B (2) +1] + [I (2) -B (2)]} * SizeOf (Тип) (3.5)

Узагальнюючи (3.5) для масиву довільної розмірності:

Mas [B (1) .. E (2)] [B (2) .. E (2)] ... [B (n) .. E (n)]

отримаємо:

Addr [I (1), I (2), ..., I (n)] = Addr [B (1), B (2), ... B (n) -

n n (3.6)

SizeOf (тип) * S [B (m) * D (m)] + SizeOf (тип) * S [I (m) * D (m)]

m = 1 m = 1

де Dm залежить від способу розміщення масиву. При розміщенні по рядках:

D (m) = [E (m + 1) -B (m + 1) +1] * D (m + 1), де m = n-1, ..., 1 і D (n) = 1

при розміщенні по стовпцях:

D (m) = [E (m-1) -B (m-1) +1] * D (m-1), де m = 2, ..., n і D (1) = 1

При обчисленні адреси елемента найбільш складним є обчислення третьої складової формули (3.6), т. К. Перші дві які залежать від індексів і можуть бути обчислені заздалегідь. Для прискорення обчислень множники D (m) також можуть бути обчислені заздалегідь і зберігатися в дескрипторі масиву. Дескриптор масиву, таким чином, містить:

- Початкова адреса масиву - Addr [I (1), I (2), ..., I (n)];

- Число вимірювань в масиві - n;

- Постійну складову формули лінеаризації (перші дві складові формули (3.6);

- Для кожного з n вимірювань масиву:

- Значення граничних індексів - B (i), E (i);

- Множник формули лінеаризації - D (i).

3.2.5. спеціальні масиви

На практиці зустрічаються масиви, які в силу певних причин можуть записуватися в пам'ять не повністю, а частково. Це особливо актуально для масивів настільки великих розмірів, що для їх зберігання в повному обсязі пам'яті може бути недостатньо. До таких масивів відносяться розріджені масиви.

Розріджених МАСИВИ. Розріджений масив - масив, більшість елементів якого рівні між собою, так що зберігати в пам'яті досить лише невелике число значень відмінних від основного (фонового) значення інших елементів.

МАСИВИ З математичний опис РОЗТАШУВАННЯ НЕФОНОВИХ ЕЛЕМЕНТІВ. До даного типу масивів відносяться масиви, у яких розташування елементів зі значеннями, відмінними від фонового, можуть бути математично описані, т. Е. В їх розташуванні є якась закономірність.

Розріджених МАСИВИ СО випадковим розташуванням ЕЛЕМЕНТІВ. До даного типу масивів відносяться масиви, у яких розташування елементів зі значеннями відмінними від фонового, не можуть бути математично описані, т. Е. В їх розташуванні немає будь-якої закономірності.

3.3. безлічі

ЛОГИЧЕСКАЯ СТРУКТУРА. Безліч - така структура, яка представляє собою набір неповторюваних даних одного і того ж типу. Безліч може приймати всі значення базового типу. Базовий тип не повинен перевищувати 256 можливих значень. Тому базовим типом множини можуть бути byte, char і похідні від них типи.

ФІЗИЧНА СТРУКТУРА. Безліч в пам'яті зберігається як масив бітів, в якому кожен біт вказує, чи є елемент належить оголошеному безлічі чи ні. Т. о. максимальне число елементів безлічі 256, а дані типу безліч можуть займати не більше 32-ох байт.

3.3.5. Операції над множинами

Нехай S1, S2, S3: set of byte, Над цими множинами визначені наступні специфічні операції.

1) Об'єднання множин: S2 + S3. Результатом є безліч, що містить елементи обох вихідних множин.

2) Перетин множин: S2 * S3. Результатом є безліч, що містить загальні елементи обох вихідних множин.

3) Перевірка на входження елемента в безліч: a in S1. Результатом цієї операції є значення логічного типу - true, якщо елемент a входить в безліч S1, false - в протилежному випадку.

3.4. Записи (структури)

3.4.1. Логічне і машинне подання записів

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

У пам'яті ця структура запису може бути представлена ??в одному з двох видів:

а) у вигляді послідовності полів, які займають безперервну область пам'яті. При такій організації досить мати один покажчик на початок області і зміщення відносно початку.

б) у вигляді зв'язного списку з покажчиками на значення полів запису. При такій організації має місце швидке звернення до елементів, але дуже неекономічний витрата пам'яті для зберігання.

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

3.4.2. Операції над записами

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

Ім'я змінної-запису. Ім'я поля

Над обраним полем записи можливі будь-які операції, допустимі для типу цього поля. Більшість мов програмування підтримує деякі операції, що працюють із записом, як з єдиним цілим, а не з окремими її полями. Це операції присвоювання одного запису значення іншої однотипної записи і порівняння двох однотипних записів на рівність / нерівність. У тих же випадках, коли такі операції не підтримуються мовою явно, вони можуть виконуватися над окремими полями записів або ж записи можуть копіюватися і порівнюватися як неструктуровані області пам'яті.

3.4.3. Записи з варіантами

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

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

3.6. таблиці

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

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

Об'єктивним критерієм, що дозволяє оцінити ефективність того чи іншого алгоритму, є, так званий, порядок алгоритму. порядком алгоритму називається функція O (N), що дозволяє оцінити залежність часу виконання алгоритму від обсягу переробляються даних (N - кількість елементів в масиві або таблиці). Ефективність алгоритму тим вище, чим менше час його виконання залежить від обсягу даних. Більшість алгоритмів з точки зору порядку зводяться до трьох основних типів:

- Статечні - O (Na);

- Лінійні - O (N);

- Логарифмічні - O (loga(N)).

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

В подальшому викладі все опису алгоритмів дані для роботи з таблицею, що складається із записів R [1], R [2], ..., R [N] з ключами K [1], K [2], ..., K [N]. У всіх випадках N - кількість елементів таблиці.

3.6.1. Операції логічного рівня над таблицями. Пошук

3.6.1.1. Послідовний або лінійний пошук

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

Для послідовного пошуку в середньому потрібно (N + 1) / 2 порівнянь. Таким чином, порядок алгоритму - лінійний - O (N).

3.6.1.2. бінарний пошук (Дихотомический, двійковий)

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

Для того, щоб знайти потрібний запис в таблиці, в гіршому випадку потрібно log2(N) порівнянь.

3.6.2. Операції логічного рівня над таблицями. Сортування

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

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

1). Наявний ресурс пам'яті: чи повинні вхідний і вихідний безлічі розташовуватися в різних областях пам'яті або вихідна безліч може бути сформовано на місці вхідного. В останньому випадку наявна область пам'яті повинна в ході сортування динамічно перерозподілятися між вхідним і вихідним множинами; для одних алгоритмів це пов'язано з великими витратами, для інших - з меншими.

2). Вихідна впорядкованість вхідного безлічі: у вхідному безлічі можуть потрапляти впорядковані ділянки. У граничному випадку вхідна множина може виявитися вже впорядкованим. Одні алгоритми не враховують вихідної впорядкованості і вимагають одного і того ж часу для сортування будь-якої (в тому числі і вже упорядкованого) безлічі даного обсягу, інші виконуються тим швидше, чим краще впорядкованість на вході.

3). Тимчасові характеристики операцій: при визначенні порядку алгоритму час виконання вважається зазвичай пропорційним числу порівнянь ключів. Однак, порівняння числових ключів виконується швидше, ніж строкових, операції пересилання, характерні для деяких алгоритмів, виконуються тим швидше, чим менше обсяг записи, і т. П. Залежно від характеристик записи таблиці може бути обраний алгоритм, що забезпечує мінімізацію числа тих чи інших операцій.

4). Складність алгоритму. Простий алгоритм вимагає меншого часу для його реалізації і ймовірність помилки в реалізації його менше.

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

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

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

3). Стратегія розподілу. Вхідний безліч розбивається на ряд підмножин (можливо, меншого обсягу) і сортування ведеться всередині кожного такого підмножини.

4). Стратегія злиття. Вихідна безліч виходить шляхом злиття маленьких впорядкованих підмножин.

Далі наводиться огляд (далеко не повний) методів сортування, згрупованих по стратегіях, що застосовуються в їх алгоритмах.

3.6.2.1. сортування вибіркою

СОРТУВАННЯ ПРОСТИЙ вибірки. Даний метод реалізує практично "дослівно" сформульовану вище стратегію вибірки.

Обмінного сортування ПРОСТИЙ вибірки. Вхідний і вихідний безліч розташовуються в одній і тій же області пам'яті; вихідна - на початку області, вхідний - в залишилася її частини. У початковому стані вхідна множина займає всю область, а вихідна безліч - пусте. У міру виконання сортування вхідна множина звужується, а вихідний - розширюється.

Бульбашкового сортування. Вхідний безліч проглядається, при цьому попарно порівнюються сусідні елементи множини. Якщо порядок їх прямування не відповідає заданому критерію впорядкованості, то елементи міняються місцями. В результаті одного такого перегляду при сортуванні по зростанню елемент з найбільшим значенням ключа переміститься ("спливе") на останнє місце в множині. При наступному проході на своє місце "спливе" другий за величиною ключа елемент і т. Д. Для постановки на свої місця N елементів слід зробити N-1 проходів. Вихідна безліч, таким чином, формується в кінці сортованої послідовності, при кожному наступному проході його об'єм збільшується на 1, а обсяг вхідного безлічі зменшується на 1.

Сортування Шелла. Модифікація бульбашкового сортування. Тут виконується порівняння ключів, віддалених один від одного на деякій відстані d. Початковий розмір d зазвичай вибирається порівнянним з половиною загального розміру сортованої послідовності. Виконується бульбашкова сортування з інтервалом порівняння d. Потім величина d зменшується вдвічі і знову виконується бульбашкова сортування, далі d зменшується ще удвічі і т. Д. Остання бульбашкова сортування виконується при d = 1.

3.6.2.2. сортування включенням

СОРТУВАННЯ ПРОСТИМИ ВСТАВКАМИ. Цей метод - "дослівна" реалізації стратегії включення. Порядок алгоритму сортування простими вставками - O (N ^ 2), якщо враховувати тільки операції порівняння. Але сортування вимагає ще і в середньому N2./4 переміщень, що робить її в такому варіанті значно менш ефективною, ніж сортування вибіркою.

Бульбашкового сортування ВСТАВКАМИ. Вхідний і вихідний безлічі знаходяться в одній послідовності, причому вихідна - в початковій її частині. У початковому стані можна вважати, що перший елемент послідовності вже належить впорядкованого вихідного безлічі, інша частина послідовності - невпорядковане вхідний. Перший елемент вхідного безлічі примикає до кінця вихідного безлічі. На кожному кроці сортування відбувається перерозподіл послідовності: вихідний безліч збільшується на один елемент, а вхідний - зменшується. Це відбувається за рахунок того, що перший елемент вхідного безлічі тепер вважається останнім елементом вихідного. Потім прокрутити вихідного безлічі від кінця до початку з перестановкою сусідніх елементів, які не відповідають критерію впорядкованості. Перегляд припиняється, коли припиняються перестановки. Це призводить до того, що останній елемент вихідного безлічі "випливає" на своє місце в множині.

СОРТУВАННЯ впорядкованості двійкового дерева. Алгоритм складається з побудови упорядкованого двійкового дерева і подальшого його обходу. Якщо немає необхідності в побудові всього лінійного впорядкованого списку значень, то немає необхідності і в обході дерева, в цьому випадку застосовується пошук в упорядкованому довічним дереві. Алгоритми роботи з впорядкованими двійковими деревами розглянуті в темі 6. Порядок алгоритму - O (N * log2N)), але в конкретних випадках все залежить від упорядкованості вихідної послідовності, який впливає на ступінь збалансованості дерева

3.6.2.3. сортування розподілом

Порозрядному ЦИФРОВИЙ СОРТИРОВКИ. Алгоритм вимагає подання ключів сортованої послідовності у вигляді чисел в деякій системі числення P. Число проходів сортування дорівнює максимальному числу значущих цифр в числі - D. У кожному проході аналізується значуща цифра в черговому розряді ключа, починаючи з молодшого розряду. Всі ключі з однаковим значенням цієї цифри об'єднуються в одну групу. Ключі в групі розташовуються в порядку їх надходження. Після того, як вся вихідна послідовність розподілена по групах, групи розташовуються в порядку зростання пов'язаних з групами цифр. Процес повторюється для другої цифри і т. Д., Поки не будуть вичерпані значущі цифри в ключі. Підстава системи числення P може бути будь-яким, в окремому випадку 2 або 10. Для системи числення з основою P потрібно P груп.

ШВИДКА СОРТИРОВКИ Хоаром. Даний алгоритм відноситься до розподільних і забезпечує показники ефективності O (N * log2 (N)) навіть при найгіршому вихідному розподілі.

Використовуються два індексу - i і j - з початковими значеннями 1 і N відповідно. Ключ K [i] порівнюється з ключем K [j]. Якщо ключі відповідають критеріям впорядкованості, то індекс j зменшується на 1 і проводиться таке порівняння. Якщо ключі не відповідають критеріям, то записи R [i] і R [j] міняються місцями. При цьому індекс j фіксується і починає змінюватися індекс i (збільшуватися на 1 після кожного порівняння). Після наступної перестановки фіксується i і починає змінюватися j і т. Д. Прохід закінчується, коли індекси i і j стають рівними. Запис, що знаходиться на позиції зустрічі індексів, стоїть на своєму місці в послідовності. Ця запис ділить послідовність на два підмножини. Всі записи, розташовані зліва від неї мають ключі, менші ніж ключ цього запису, все записи праворуч - великі. Той же самий алгоритм застосовується до лівого подмножеству, а потім до правого. Записи підмножини розподіляються за двома ще меншим підмножини і т. Д., І т. Д. Розподіл закінчується, коли отримане підмножина буде складатися з єдиного елемента - таке підмножина вже є впорядкованим.

3.6.2.4. сортування злиттям

Алгоритми сортування злиттям, як правило, мають порядок O (N * log2 (N)), але відрізняються від інших алгоритмів більшою складністю і вимагають великого числа пересилань. Алгоритми злиття застосовуються в основному, як складова частина зовнішньої сортування. Тут же для розуміння принципу злиття приведений простий алгоритм злиття в оперативній пам'яті.

СОРТУВАННЯ попарне злиття. Вхідний безліч розглядається, як послідовність підмножин, кожне з яких складається з єдиного елемента і, отже, є вже впорядкованим. На першому проході кожні два сусідніх одноелементні безлічі зливаються в одне двоелементною впорядкована множина. На другому проході двоелементний безлічі зливаються в 4-елементні впорядковані множини і т. Д. В кінці кінців виходить одне велике впорядковане безліч.

3.6.3. Прямий доступ і хешування

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

3.6.3..1. Таблиці прямого доступу

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

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

3.6.3.2. Таблиці з довідниками

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

3.6.3.3. Хешировать таблиці і функції хешування

Оскільки пам'ять є одним з найдорожчих ресурсів обчислювальної системи, з міркувань її економії доцільно призначати розмір простору записів рівним розміру фактичного безлічі записів або перевершує його незначно. У цьому випадку ми повинні мати деяку функцію, що забезпечує відображення точки з простору ключів в точку в просторі записів, т. Е., Перетворення ключа на адресу записи: r = H (k), де - r адреса записи, k - ключ. Така функція називається функцією хешування (функція перемішування, функція рандомізації).

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

Якщо функція H, яка перетворює ключ на адресу, може породжувати колізії, то однозначної зворотної функції: k = H '(r), що дозволяє відновити ключ за відомою адресою, існувати не може. Тому ключ повинен обов'язково входити до складу записи хешировать таблиці як один з її полів.

До функції хешування в загальному випадку висуваються такі вимоги:

 * Вона повинна забезпечувати рівномірний розподіл відображень фактичних ключів по простору записів;

 * Вона повинна породжувати якомога менше колізій для даного фактичного безлічі записів;

 * Вона не повинна відображати будь-який зв'язок між значеннями ключів в зв'язок між значеннями адрес;

 * Вона повинна бути простою і швидкою для обчислення.

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

3.6.3.3.1. Проблема колізій в хешировать таблицях

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

ПОВТОРНЕ хешуванні. Повторне хешування передбачає наступне: якщо при спробі запису в таблицю виявляється, що необхідне місце в таблиці вже зайнято, то значення записується в ту ж таблицю на якесь інше місце. Інше місце визначається за допомогою вторинної функції хешування H2, аргументом якої в загальному випадку може бути і вихідне значення ключа і результат попереднього хешування: r = H2 (k, r '), де r' - адреса, отриманий при попередньому застосуванні функції хешування. Якщо отриманий в результаті застосування функції H2 адреса також виявляється зайнятим, функція H2 застосовується повторно - до тих пір, поки не буде знайдено вільне місце.

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

ЗАГАЛЬНА ОБЛАСТЬ переповнених. Для таблиці виділяються дві області пам'яті: основна область і область переповнень. Функція хешування на виході дає адресу записи або пакета в основний області. При вставці запису, якщо її "законне" місце в основній області вже зайнято, запис заноситься на перше вільне місце в області переповнення. При пошуку, якщо "законне" місце в основній зайнято записом з іншим ключем, виконується лінійний пошук в області переповнення.

РОЗДІЛЬНІ ЛАНЦЮЖКИ переповнених. У структуру кожного запису додається ще одне поле - покажчик на наступний запис. Через ці покажчики записи з ключами-синонімами зв'язуються в лінійний список, початок якого знаходиться в основній таблиці, а продовження - поза нею. При вставці запису в таблицю по функції хешування обчислюється адреса записи (або пакета) в основній таблиці. Якщо це місце в основній таблиці вільно, то запис заноситься в основну таблицю. Якщо ж місце в основній таблиці зайнято, то запис розташовується поза нею. Пам'ять для такого запису з ключем-синонімом може виділятися або динамічно для кожного нового запису, або для синоніма призначається елемент з заздалегідь виділеної області переповнення. Після розміщення записи-синоніма поле покажчика із запису основної таблиці переноситься в поле покажчика синоніма, а на його місце в запису основної таблиці записується покажчик на тільки що розміщений синонім.




 Тема 1. Структури даних і алгоритми |  Тема 5. Динамічні структури даних. зв'язкові списки |  Тема 6. Нелінійні структури даних |  Тема 7. Файлові структури даних |

© 2016-2022  um.co.ua - учбові матеріали та реферати