Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Організація таблиць.Таблиця ідентифікаторів.
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Лекція
Предмет:
Інші
Частина тексту файла (без зображень, графіків і формул):
Організація таблиць. Таблиця ідентифікаторів
Перевірка правильності семантики і генерація коду вимагають знання характеристик ідентифікаторів, які використовуються у вхідній програмі. Ці характеристики з'ясовуються з описів та з того, як використовуються ідентифікатори у програмі.
Зокрема, для імен змінних потрібно знати таку інформацію:
тип (цілий, дійсний, символьний тощо);
вид (проста змінна, масив, структура тощо);
адреса під час виконання програми;
вимірність, якщо це ідентифікатор масиву; кількість елементів за відповідним виміром або значення елементів граничних пар;
зв'язок з іншими компонентами, якщо розглядається структура або її компоненти;
формальний параметр чи ні; якщо формальний параметр, то тип відповідності параметрів;
чи оброблявся опис змінної;
чи присвоєне значення даній змінній .
Для імен процедур важлива інша інформація, а саме:
чи є процедура зовнішньою відносно програми;
чи є вона функцією; якщо так, то який її тип;
чи оброблявся її опис;
чи є вона рекурсивною;
чи має вона формальні параметри; якщо так, то які саме.
Ця інформація накопичується у таблиці ідентифікаторів (таблиці символів, таблиці імен). Тому розглянемо проблему організації таблиць, звертаючи особливу увагу на організацію таблиць символів.
Таблиця − це множина записів, організованих таким чином, що кожен запис, а, можливо і його розташування однозначно визначається так званим ключем цього запису. Зазвичай записи складаються з двох полів: ключа, що однозначно визначає цей запис, і тіла запису, що містить власне сам запис.
Ідентифікація записів ключами виправдана тим, що тіло запису може мати досить складну структуру, з якої важко виділити єдино можливу ознаку для розпізнавання запису; у той час ключі мають простішу однорідну структуру і допускають порівняння між собою. Ключ повинен бути унікальним, тобто не може бути двох різних записів у таблиці, які мають однакові ключі.
Для таблиці ідентифікаторів аргументами таблиці є ідентифікатори, а значеннями їх характеристики. Оскільки кількість літер у ідентифікаторах різна, у аргументі часто записують замість самого ідентифікатора покажчик на нього. Це дає можливість мати аргумент фіксованого розміру. У такому випадку ідентифікатори зберігаються у спеціально відведеній ділянці пам'яті. Кількість літер може зберігатись як частина аргументу або безпосередньо перед ідентифікатором.
Так, таблицю
Аргумент Значення
можна зберігати так
Аргумент Значення
або так
Аргумент Значення
Доступ до тіла запису можна здійснити за ключем запису. Тому, розглядаючи методи роботи з таблицями, основну увагу потрібно приділити обробці ключів (аргументів), тільки при необхідності звертаючись до даних, що знаходяться у тілі (значенні) запису (наприклад, щоб з'ясувати, що певному ключу не поставлені у відповідність дані у полі тіла запису). Операції з таблицями, таким чином, будемо визначати в першу чергу стосовно ключів, хоча вони виконуються і над відповідними тілами записів.
Найбільш розповсюдженими операціями над таблицями є: 1) включення нового запису у таблицю; 2) пошук у таблиці запису із заданим ключем; 3) усунення з таблиці запису з вказаним ключем; 4) модифікація запису з вказаним ключем. Ефективність і навіть можливість застосування тої чи іншої операції суттєво залежить від того, яким чином організована таблиця, як вона нарощується, як організовано доступ до окремих записів.
Коли компілятор починає трансляцію вхідної програми, таблиця ідентифікаторів порожня або містить декілька елементів для службових слів і стандартних функцій. У процесі компіляції для кожного нового ідентифікатора елемент додається лише один раз. Але для кожного входження ідентифікатора у вхідній програмі здійснюється пошук відповідного елемента у таблиці ідентифікаторів; інформація, отримана при даному входження, співставляється з раніше отриманою, виконується необхідний контроль і реєстрація нової інформації. Тому важливо вибрати таку організацію таблиці, яка допускала б ефективний пошук і внесення інформації.
Бажано порівнювати різні методи роботи з таблицями за часом пошуку. Ми будемо проводити порівняння за очікуваною кількістю порівнянь, які потрібно виконати, щоб знайти елемент з заданим ключем.
Послідовні таблиці
Таблиця називається послідовною, якщо вона організована так, що можливий лише послідовний доступ до її записів (проглядати зазвичай починають або з першого, або з останнього запису). Логічний порядок слідування елементів таблиці, що визначається черговістю занесення даних, збігається з розташуванням записів у пам'яті. Пошук у цьому випадку вимагає порівняння заданого ключа з ключем кожного елементу таблиці, доки не буде знайдено бажаний елемент.
Обробку записів можна прискорити, якщо записи у послідовній таблиці впорядковані за зростанням (спаданням) ключа. Для знаходження запису достатньо проглянути ту частину таблиці, записи у якій мають менше (або більше) значення ключа, ніж ключ шуканого запису.
Для впорядкованих таблиць у векторній (послідовній) пам'яті ускладнюється (у порівнянні з невпорядкованими) операція включення нового запису. Для розміщення його у таблиці всі вже наявні у таблиці записи потрібно розсунути таким чином, щоб звільнити фрагмент пам'яті, достатній для розміщення нового запису. Для включення нового запису можна запропонувати метод «бульбашки», при якому ключ нового запису порівнюється з біжучим, починаючи з кінця, і біжучий запис зсувається на вільне місце, якщо ключ цього запису більший за ключ нового запису (для таблиці, впорядкованої за зростанням значень ключів).
У послідовній таблиці з EMBED Equation.3 записами, якщо пошук кожного з них однаково ймовірний з ймовірністю EMBED Equation.3 , середня кількість порівнянь для пошуку дорівнює
EMBED Equation.3 .
Таким чином, у середньому доводиться проглядати близько половини таблиці. При великому обсязі таблиці послідовна організація приводить до значних витрат часу. Впорядкованість записів у послідовній таблиці прискорює обробку для деякого заданого діапазону значень ключів, але не зменшує час пошуку окремого запису. Для скорочення часу можна запропонувати розміщувати часто вживані записи на початку таблиці.
Таблиці, організовані як дерева порівнянь
У цьому методі для упорядкування елементів використовуються бінарне дерево, у якому до кожного вузла можна «підвісити» не більше двох піддерев. Кожен із вузлів дерева − це заповнений елемент таблиці, причому перший елемент записується у корінь дерева. При надходженні нового елемента його ключ порівнюється з ключем кореневого елементу. Якщо цей ключ менший за кореневий, новий елемент записується у ліве піддерево, якщо більший − у праве.
Припустимо, що у таблиці потрібно розмістити ідентифікатори
Kl, FR, M, A1, P2, L0
Процес побудови дерева можна проілюструвати таким чином:
K1
Крок 1.
FR
K1
Крок 2. FR < K1, вибираємо ліве піддерево.
K1
FR
M
Крок 3. MN>K1, вибираємо праве піддерево.
K1
FR
M
A1
Крок 4. A1<K1, йдемо по лівій дузі, A1< FR, добудовуємо ліве піддерево (стосовно FR)
Крок 5. P2>K1, йдемо по правій дузі, P2>M, добудовуємо праве піддерево (стосовно M).
K1
FR
M
A1
P2
Крок 6. L0>K1, йдемо по правій дузі, L0<M, добудовуємо праве піддерево (стосовно M).
K1
FR
M
A1
P2
L0
Вигляд побудованого дерева (і кількість порівнянь) суттєво залежить від порядку надходження елементів. Так, у даному прикладі кількість порівнянь при побудові дерева була не більшою за 2. Якщо ж елементи надходили б у такому порядку
A1, FR, K1, L0, M, P2,
то дерево виглядало б так:
A1
FR
K1
L0
M
P2
І кількість порівнянь при включенні елемента з ключем P2 вимагало б 5 порівнянь, а пошук елемента у вже сформованому дереві у гіршому випадку вимагав би 6 порівнянь, тобто ефективність була б такою, як у послідовній невпорядкованій таблиці.
Найшвидше операції включення будуть виконуватись на так званих збалансованих (вирівняних) деревах. Дерево називається збалансованим, якщо всі вершини, у яких будуть розміщатись нові елементи, знаходяться на двох останніх рівнях, тобто кількості вершин лівого і правого піддерев для будь-якого його піддерева відрізняються не більше ніж на 1. Для збалансованого дерева середнє число порівнянь має порядок EMBED Equation.3 . Тому для пришвидшення обробки елементів бажано так формувати дерева, щоб вони були близькими за своїми характеристиками до збалансованих дерев.
Для реалізації методу можна у кожному елементі (записі) виділити два поля покажчиків, одне поле для лівої, а друге для право гілки.
Пошук елементів у такій таблиці і включення нових елементів не буде викликати значних труднощів.
Таблиці з обчислюваними входами. Хеш-адресація
Цей метод організації таблиць передбачає перетворення символу (ключа елементу) у індекс (адресу) елементу в таблиці, тобто адреса запису визначається як деяка функція від ключа запису. Функція EMBED Equation.3 , яка кожному можливому значенню ключа EMBED Equation.3 , ставить у відповідність одне з чисел з множини EMBED Equation.3 або EMBED Equation.3 , якщо EMBED Equation.3 − розмір таблиці (кількість можливих записів), називається хеш-фунцією (функцією розстановки), а сам процес обчислення адреси − хешуванням.
Наприклад, простою хеш-функцією є внутрішнє зображення першої літери символу. Так, якщо код літери A є 41h, літери B − 42h, літери C − 43h, …, то результатом хешування символу ABC буде 41h, CR − 43h, F − 46h.
Таблицю, організовану таким чином, будемо називати хеш-таблицею або таблицею з обчислюваними входами (з прямим доступом). Якщо для різних символів результати хешування різні, час пошуку збігається з часом, витраченим на хешування. Підбір хеш-функції, що забезпечує взаємно однозначну відповідність між ключами та адресами, для багатьох практичних застосувань − задача досить складна. Зазвичай її можна розв'язати лише для таблиць сталого розміру з відомою скінченною множиною значень ключа.
Але якщо для різних символів результати хешування збігаються, виникає так звана колізія. Очевидно, що у одній позиції таблиці можна розмістити лише один запис (один ідентифікатор), тому потрібно знайти у таблиці місце для другого запису з тою самою хеш-функцією. Хороша хеш-функція розподіляє обчислювані адреси рівномірно в межах таблиці, так що колізії виникають не дуже часто. Хеш-функція, розглянута вище, невдала, оскільки всі ідентифікатори, які починаються з одної і тої ж самої букви, посилаються на одну і ту ж саму адресу.
Розглянемо два способи розв'язування ситуації колізії − рехешування і метод ланцюжків.
Рехешування
Нехай EMBED Equation.3 − ключ запису, який потрібно знайти у таблиці, після хешування виникла ситуація, коли запис у таблиці з адресою EMBED Equation.3 вже займає елемент з іншим ключем EMBED Equation.3 . Розглянемо позицію з адресою EMBED Equation.3 (за модулем EMBED Equation.3 ), де EMBED Equation.3 − деяке ціле число. Якщо знову виникає колізія, розглядаємо позицію з адресою EMBED Equation.3 (за модулем EMBED Equation.3 ), для деякого цілого числа EMBED Equation.3 . Це продовжується, поки не знайдеться вільна позиція з адресою (за модулем EMBED Equation.3 ) або ця позиція містить запис з ключем EMBED Equation.3 , ця позиція містить запис з ключем EMBED Equation.3 ця позиція містить запис з ключем EMBED Equation.3 ( EMBED Equation.3 ). У останньому випадку пошук припиняється, оскільки таблиця заповнена.
Таким чином, якщо виникло EMBED Equation.3 колізій, буде виконано EMBED Equation.3 порівнянь з елементами за адресами EMBED Equation.3 (за модулем EMBED Equation.3 ). Числа EMBED Equation.3 повинні вибиратись так, щоб очікувана кількість порівнянь була невеликою, а також був забезпечений доступ до всіх елементів таблиці.
Рехешування пов'язують з терміном розсіяної пам'яті, оскільки заповнені позиції виявляються розсіяними по всій таблиці. Зауважимо, що для того, щоб відрізняти порожні записи від заповнених, всі елементи повинні бути заповнені спочатку деяким значенням, що відрізняється від можливих ключів. Крім того, таблиця повинна бути відразу розрахована на максимальну кількість елементів, оскільки немає простого способу розширити таблицю, якщо вона заповниться, без повторного обчислення хеш-адрес для всіх записаних символів і занесення їх у відповідні нові позиції.
Лінійне рехешування
Найпростіший відомий метод рехешування (і. напевне найменш ефективний) полягає у тому, щоб покласти EMBED Equation.3 . Таким чином, порівнюються послідовні елементи.
Нехай, наприклад, у таблиці ( EMBED Equation.3 ) записані такі елементи
Потрібно записати у таблицю елементи з ключами EMBED Equation.3 і EMBED Equation.3 , якщо EMBED Equation.3 , EMBED Equation.3 .
При спробі записати елемент з ключем EMBED Equation.3 у позицію 4 виникає колізія, позиція 5 вільна, тому EMBED Equation.3 записується у позицію 5. При спробі записати елемент EMBED Equation.3 у позицію 1, виникає колізія; колізія виникає і за адресою 2, позиція 3 вільна, тому таблиця набуває вигляду
Зауважимо, що колізія виникає при розгляді позиції 2 (вторинна колізія), хоча EMBED Equation.3 . Таким чином, якщо у деякій частині таблиці є скупчення елементів, ефективність методу стає низькою.
Інші види рехешування
Вибираючи іншим способом значення елементів послідовності, можна обійти проблему скупчення елементів (наприклад, вибираючи псевдовипадкові числа з певного інтервалу, одержимо випадкове рехешування).
Вибравши EMBED Equation.3 , ми будемо проглядати елементи EMBED Equation.3 (всі значення обчислюються за модулем, що дорівнює довжині таблиці). Цей метод буде вдалим, якщо довжина таблиці EMBED Equation.3 є простим числом; у цьому випадку можна проглянути всі позиції у таблиці. Але у цьому випадку не можна брати EMBED Equation.3 .
Якщо EMBED Equation.3 обчислюються за правилом EMBED Equation.3 , де EMBED Equation.3 − цілі числа, відповідний вид рехешування називається квадратичним. Головна проблема при цьому, як і при інших видах ре хешування, полягає у тому, щоб забезпечити доступ до різних (всіх) елементів таблиці. Зокрема, якщо розмір таблиці EMBED Equation.3 , то кількість елементів, які проглядаються при цьому виді ре хешування, досить мале.
Метод ланцюжків
Метод ланцюжків використовує масив покажчиків hash, початкове значення яких дорівнює 0, власне таблицю символів (ідентифікаторів), яка спочатку є порожньою, і покажчик Point_free, який вказує на першу вільну позицію у таблиці (перед початком роботи Point_free вказує на початок таблиці). Елементи таблиці символів мають додаткове поле − Озн_ланц, у якому записано 0 або адреса іншого елемента таблиці. Початковий стан виглядає так:
Хеш-функція, застосована до чергового символу дає індекс покажчика у hash. Покажчик або дорівнює 0, або вказує на перший елемент таблиці з даним значеннім хеш-функції. Поле Озн_ланц кожного елементу використовується для того, щоб зв'язати у ланцюжок елементи, для яких хешування символу дає однаковий результат.
Нехай у таблицю символів потрібно записати елементи з такими значеннями хеш-функції:
На першомо кроці виконуємо такі дії: 1) записуєм елемент з ключем M у позицію, на яку вказує Point_free (у даному випадку першу позицію); 2) записуєм значення Point_free елемент hash[5]; 3) збільшуємо Point_free на 1.
Після першого кроку маємо:
Поки надходять символи, хешування яких дає різні значення хеш-функції (різні індекси у hash, виконуються дії, як при записі першого елементу. Після чотирьох кроків маємо:
Після четвертого кроку маємо:
Коли надходить символ A1, він посилається на елемент hash[1], який вже використовувався раніше ( значення елементу не дорівнює 0). Символ A1 записується у чергову вільну позицію таблиці, а його індекс (адреса) записується у поле Озн_ланц елемента А. Тому після п'ятого кроку буде така картина:
а після шостого −
Якщо таблиця символів заповнена, можна завжди додати до неї новий блок елементів, оскільки хеш-функція дає індекс у масиві hash, а посилання на елементи таблиці символів здійснюються за допомогою елементів цього масиву (покажчиків) або значень поля Озн_ланц. Таким чином, кількість елементів у таблиці може бути більшою, ніж кількість покажчиків у hash.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора