Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розробка та дослідження ефективності методів пошуку даних
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2016
Тип роботи:
Лабораторна робота
Предмет:
Алгоритми та методи обчислень
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки
Національний університет “Львівська політехніка”
Кафедра ЕОМ
/
Звіт
з лабораторної роботи № 2
з дисципліни: “Алгоритми та методи обчислень”
на тему: “Розробка та дослідження ефективності методів пошуку даних”
Мета лабораторної роботи
Дослідити ефективність методів пошуку на прикладі різних методів організації хеш-таблиць. Вивчити основні методи побудови хеш-таблиць, дослідити переваги і недоліки, властиві різним методам, оцінити ефективність і провести порівняння ефективностей.
Теоретичні відомості
Одним з поширених прикладів застосування хеш-таблиць є побудова і пошук в таблиці ідентифікаторів програми. Головною характеристикою будь-якого елемента вхідної програми є його ім'я. Саме з іменами змінних, констант, функцій і інших елементів вхідної мови оперує розробник програми - тому і компілятор повинен вміти аналізувати ці елементи по їхніх іменах.
Таким чином, завдання компілятора полягає в тому, щоб зберігати деяку інформацію, пов'язану з кожним елементом вхідної програми, і мати доступ до цієї інформації за ім'ям елемента. Для рішення цього завдання компілятор організує спеціальні сховища даних, що називаються таблицями ідентифікаторів або таблицями символів. Таблиця ідентифікаторів складається з набору полів даних (записів), кожне з яких відповідає одному елементу вхідної програми. Запис містить всю необхідну компілятору інформацію про даний елемент і ця інформація може доповнюватись під час роботи компілятора. Кількість записів залежить від способу організації таблиці ідентифікаторів, але їх не може бути менше, ніж елементів у програмі. В принципі, компілятор може працювати не з однією, а з декількома таблицями ідентифікаторів - їх кількість і структура залежать від реалізації компілятора.
Компілятор поповнює записи в таблиці ідентифікаторів під час аналізу вхідної програми і знаходження в ній нових елементів, що вимагають розміщення в таблиці. Пошук інформації в таблиці виконується щоразу, коли компілятору потрібні відомості про той або інший елемент програми. Причому варто помітити, що пошук елемента в таблиці буде виконуватися компілятором значно частіше, ніж розміщення в ній нових елементів. Так відбувається тому, що опис нових елементів у вхідній програмі, як правило, зустрічаються набагато рідше, ніж ці елементи використовуються. Крім того, кожному додаванню елемента в таблицю ідентифікаторів завжди буде передувати операція пошуку - щоб переконатися, що такого елемента в таблиці немає.
Індивідуальне завдання
Варіант 12
Написати програму, що отримує на вході послідовність слів (ключів), будує дві хеш-таблиці цих слів, виконує операції додавання нових слів в побудовані хеш-таблиці та вилучення заданих елементів з таблиць, виводить на екран вміст кожної таблиці, здійснює багаторазовий пошук довільних слів в цих хеш-таблицях, порівнює ефективності різних методів організації хеш-таблиць.
h(key) = [7*(кількість символів в ключі)] % m;
Розв'язання колізій при хешуванні здійснити квадратичного зондування з функцією повторного хешування:
hi(key) = ( h(key) + 3 · i 2 ) % m;
Вміст файлу “data.txt”:
Mazurenko Stanislav Volodymyrovych 04 11 1997 MTS 0 9 9 6 7 5 3 3 9 7 Lvivska Lviv Vidkryta 1 601 IKTA EOM KI-24 08 03 2016
Код програми
#include <iostream>
#include <fstream>
#include <conio.h>
using namespace std;
const int n = 28;
const int m = 37;
inline int hash_func_1()
{
return n % m;
}
inline int hash_func_2(int index)
{
return (hash_func_1() + 3 * index * index) % m;
}
inline int hash_func_3(int index)
{
return (hash_func_1() + index) % m;
}
void print_hash_table(char array[m][n])
{
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
cout << array[i][j];
}
cout << endl;
}
}
void main()
{
char hash_table_1[m][n];
char hash_table_2[m][n];
char buffer[n][n];
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
hash_table_1[i][j] = NULL;
hash_table_2[i][j] = NULL;
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
buffer[i][j] = NULL;
}
}
ifstream fin("data.txt");
for (int i = 0; i < n; i++)
{
fin >> buffer[i];
}
fin.close();
for (int i = 0; i < n; i++)
{
int index = 1;
int buff;
bool flag = false;
do
{
buff = hash_func_2(index);
if (!hash_table_1[buff][0])
{
flag = true;
for (int j = 0; j < n; j++)
{
hash_table_1[buff][j] = buffer[i][j];
}
}
else
index++;
} while (!flag);
}
cout << "--------------------Begin of hash table 1--------------------------------------" << endl;
print_hash_table(hash_table_1);
cout << "--------------------End of hash table 1----------------------------------------" << endl;
for (int i = 0; i < n; i++)
{
int index = 1;
int buff;
bool flag = false;
do
{
buff = hash_func_3(index);
if (!hash_table_2[buff][0])
{
flag = true;
for (int j = 0; j < n; j++)
{
hash_table_2[buff][j] = buffer[i][j];
}
}
else
index++;
} while (!flag);
}
cout << "--------------------Begin of hash table 2--------------------------------------" << endl;
print_hash_table(hash_table_2);
cout << "--------------------End of hash table 2----------------------------------------" << endl;
cout << "Add new item to hash table 2:" << endl;
char str[n];
for (int j = 0; j < n; j++)
{
str[j] = 0;
}
cin >> str;
int g = 0;
g = hash_func_3(1);
for (int j = 0; j < n; j++)
{
hash_table_2[g][j] = str[j];
}
cout << "--------------------Begin of hash table 2--------------------------------------" << endl;
print_hash_table(hash_table_2);
cout << "--------------------End of hash table 2----------------------------------------" << endl;
_getch();
}
Результат виконання програми
/
/
/
Висновок
Я дослідив ефективність методів пошуку на прикладі різних методів організації хеш-таблиць.
30.03.2016 11:12
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора