Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розробка та дослідження ефективності методів пошуку даних
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2013
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Інші
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Національний університет “Львівська політехніка”
Кафедра ЕОМ
Звіт
з лабораторної роботи № 5
на тему:
" Розробка та дослідження ефективності методів пошуку даних"
з дисципліни:
"AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ"
Львів – 2013
Мета роботи.
Дослідити ефективність методів пошуку на прикладі різних методів організації хеш-таблиць. Вивчити основні методи побудови хеш-таблиць, дослідити переваги і недоліки, властиві різним методам, оцінити ефективність і провести порівняння ефективностей.
1. Постановка задачі.
а) Анкетні дані (вміст файлу data.txt).
Pelenskiy,Vitaliy,Igorovuch,4,8,1994,Kyivstar,0,9,6,0,7,1,6,8,5,9,Lvivska,Komarno,Zelena,31,1,IKTA,EOM,KI-24,13,5,2013
б) Індивідуальне завдання.
Вибір варіанта індивідуального завдання:
Введемо позначення: DN = 4– день народження
MN = 8– місяць народження
RN = 1994 - рік народження
А1 = 80 – ASCII-код першої літери прізвища – велика латинська літера
А2 = 101 – ASCII-код другої літери прізвища – мала латинська літера
Вибір хеш-функції
№ варіанта = ( 4 + 1994 + 80 ) % 20 + 1 = 19
19. h(key) = [добуток АSCII-кодів перших трьох символів ключа (якщо ключ містить менше трьох символів, то відсутні символи вважати рівними першому символу) ] % m;
Розв'язання колізій при хешуванні
№ варіанта = ( 4 + 1994 + 101 ) % 25 + 1 = 25
25. методом відкритої адресації з функцією повторного хешування
hi(key) = ( h(key) + i ) % m
та шляхом зміни структури хеш-таблиці (кожну комірку хеш-таблиці замінити блоком з трьох комірок);
Організація хеш-таблиці №2
№ варіанта = ( 8 + 1994 + 80 ) % 11+ 1 = 4
4. методом закритого хешування;
2. Завдання 1. Організація хеш-таблиці №1.
2.1. Обчислення хеш-значень
(написати вигляд хеш-функції та стратегію розв'язання колізій; докладно показати приклади знаходження хеш-значень для перших 10 слів з вхідного файлаdata.txt).
Розв’язання колізії:
unsigned h(const string key, const size_t m) // обчислення хеш-значення у разі колізії
{
if (key.size() >= 3)
return (key[0]*key[1]*key[2]) % m;
if (key.size() == 2)
return (key[0]*key[1]*key[0]) % m;
if (key.size() == 1)
return (key[0]*key[0]*key[0]) % m;
}
unsigned hi(const string key, const unsigned m, const unsigned i)
{
return (h(key, m) + i) % m; // виклик функціїh(m) для хеш-значення
}
bool Add(Hash *hash, const string key) // обчислення хеш-значення
{
unsigned k = h(key, hash->m);
unsigned ki, i = 1;
if (hash->data[k][0] == "" || hash->data[k][0] == " ")
{
hash->data[k][0] = key;
return 1;
}
else if (hash->data[k][1] == "" || hash->data[k][1] == " ")
{
hash->data[k][1] = key;
return 1;
}
else if (hash->data[k][2] == "" || hash->data[k][2] == " ")
{
hash->data[k][2] = key;
return 1;
}
else
{
ki = hi(key, hash->m, i);
while (ki != k && hash->data[ki][0] != "" && hash->data[ki][0] != " " && hash->data[ki][1] != "" && hash->data[ki][1] != " " && hash->data[ki][2] != "" && hash->data[ki][2] != " ")
ki = hi(key, hash->m, ++i);
if (ki != k)
{
if (hash->data[ki][0] == "" || hash->data[ki][0] == " ")
{
hash->data[ki][0] = key;
return 1;
}
if (hash->data[ki][1] == "" || hash->data[ki][1] == " ")
{
hash->data[ki][1] = key;
return 1;
}
if (hash->data[ki][2] == "" || hash->data[ki][2] == " ")
{
hash->data[ki][2] = key;
return 1;
}
}
else
{
cout << "All memory used!" << endl;
return 0;
}
}
}
void Show(const Hash const *hash)
{
cout << "________________________________________________________________________________" << endl;
for (unsigned i = 0; i < hash->m; ++i)
cout << i+1 << "\t\t" << hash->data[i][0] << " " << hash->data[i][1] << " " << hash->data[i][2] << endl;
cout << "________________________________________________________________________________" << endl;
return;
}
bool Delete(Hash *hash, const string key)
{
unsigned k, ki, i = 1;
k = h(key, hash->m);
if (key == hash->data[k][0])
{
hash->data[k][0] = " ";
return true;
}
if (key == hash->data[k][1])
{
hash->data[k][1] = " ";
return true;
}
if (key == hash->data[k][2])
{
hash->data[k][2] = " ";
return true;
}
ki = hi(key, hash->m, i);
while (ki != k && hash->data[ki][0] != "" && hash->data[ki][1] != "" && hash->data[ki][2] != "")
{
if (hash->data[ki][0] == key)
{
hash->data[ki][0] = " ";
return true;
}
if (hash->data[ki][1] == key)
{
hash->data[ki][1] = " ";
return true;
}
if (hash->data[ki][2] == key)
{
hash->data[ki][2] = " ";
return true;
}
ki = hi(key, hash->m, ++i);
}
return false;
}
string Find(const Hash const *hash, const string key)
{
unsigned k, ki, i = 1;
k = h(key, hash->m);
if (hash->data[k][0] == key)
return hash->data[k][0];
if (hash->data[k][1] == key)
return hash->data[k][1];
if (hash->data[k][2] == key)
return hash->data[k][2];
ki = hi(key, hash->m, i);
while (ki != k && hash->data[ki][0] != "" && hash->data[ki][1] != "" && hash->data[ki][2] != "")
{
if (hash->data[ki][0] == key)
return hash->data[ki][0];
if (hash->data[ki][1] == key)
return hash->data[ki][1];
if (hash->data[ki][2] == key)
return hash->data[ki][2];
ki = hi(key, hash->m, ++i);
}
return "";
}
string * FileRead(const char const *FileName)
{
const size_t n = 28;
string *buf = new string[n];
unsigned i;
ifstream fin;
fin.open(FileName, ios_base::in);
i = 0;
while (fin >> buf[i++])
continue;
fin.close();
return buf;
}
Приклади знаходження хеш-значень для перших 10 слів з вхідного файла data.txt:
вміст data.txt:
Pelenskiy,Vitaliy,Igorovuch,4,8,1994,Kyivstar,0,9,6,0,7,1,6,8,5,9,Lvivska,Komarno,Zelena,31,1,IKTA,EOM,KI-24,13,5,2013
h(Pelenskiy) = [80*101*108] % 37 = 32
h(Vitaliy) = [ 86* 105*116] % 37 = 10
h(Igorovuch) = [ 73*103*111] % 37 = 0
h(4) = [ 52*52*52 ] % 37 = 8
h(8) = [ 56*56*56] % 37 = 14
h(1994) = [49*57*57] % 37 = 27
h(Kyivstar) = [75*121*105] % 37 = 14
h(0) = [48*48*48] % 37 = 36
h(9) = [57*57*57] % 37 = 8
h(6) = [54*54*54] % 37 = 29
2.2. Побудова хеш-таблиці
(для порахованих в попередньому пункті 10 хеш-значень намалювати хеш-таблицю без повторень, тобто однакові слова розміщувати в таблицю тільки один раз; слова, що приймали участь у колізіях, підкреслити; визначити кількість кластерів в побудованій таблиці та довжину найбільшого кластера).
0
Igorovuch
1
2
3
4
5
6
7
8
4
9
9
10
Vitaliy
11
12
13
14
8
Kyivstar
15
16
17
18
19
20
21
22
23
24
25
26
27
1994
28
29
6
30
31
32
Pelenskiy
33
34
35
36
0
Кількість кластерів: 7
Довжина найбільшого: 2
2.3. Пошук ключа
(словесно описати процес пошуку в побудованій хеш-таблиці ключа key, де key - передостаннє слово в файлі data.txt ; записати послідовність ключів, з якими відбувається порівняння під час пошуку).
Словесний опис:
Потрібно ввестиз клавіатури key, функція find() викликає хеш-функцію, яка визначає і повертає для заданого key хеш-значення, яке find() порівнює значення в таблиці із заданим key, якщо значення однакові, успішний пошук, інакше,find() викликає функцію яка шукає нове хеш-значення(вільне в таблиці) і це триває доти доки не дійде до порожньої комірки.
Послідовність ключів, з якими відбувається порівняння під час пошуку («5» - передостаннє слово в файлі data.txt):
такий key в таблиці повторюється 3 рази.Знайдеться з першого разу.
2.4. Результати роботи програми з першою хеш-таблицею
(вивести вигляд побудованої хеш-таблиці, вигляд хеш-таблиці після додавання нового елемента, вигляд хеш-таблиці після вилучення одного елемента).
Вигляд побудованої хеш-таблиці:
/
Вигляд хеш-таблиці після додавання нового елемента "element":
/
Вигляд хеш-таблиці після вилучення одного елемента "13":
/
3. Завдання 2. Організація хеш-таблиці №2.
3.1. Обчислення хеш-значень
(написати вигляд хеш-функції та стратегію розв'язання колізій; докладно показати приклади знаходження хеш-значень для перших 10 слів з вхідного файлаdata.txt).
Розв’язання колізії:
unsigned h(const string key, const size_t m) // обчислення хеш-значення
{
unsigned sum = 0;
for (unsigned i = 0; i < key.size() ; ++i)
sum += key[i];
return sum % m;
}
unsigned hi(const string key, const unsigned m, const unsigned i, unsigned cof) // обчислення хеш- значення у разі колізії
{
return (h(key, m) + cof*i) % m;
}
Приклади знаходження хеш-значень для перших 10 слів з вхідного файлаdata.txt:
вміст data.txt:
Pelenskiy,Vitaliy,Igorovuch,4,8,1994,Kyivstar,0,9,6,0,7,1,6,8,5,9,Lvivska,Komarno,Zelena,31,1,IKTA,EOM,KI-24,13,5,2013
h(Pelenskiy) = [80+101+108+101+110+115+107+105+121] % 37 = 23
h(Vitaliy) = [86+105+116+97+108+105+121] % 37 = 35
h(Igorovuch) = [73+103+111+114+111+118+117+99+104] % 37 = 25
h(4) = [52] % 37 = 15
h(8) = [56] % 37 = 19
h(1994) = [49+57+57+52] % 37 = 30
h(Kyivstar) = [75+121+105+118+115+116+97+114] % 37 = 10
h(0) = [48] % 37 = 11
h(9) = [57] % 37 = 20
h(6) = [54] % 37 = 17
3.2. Побудова хеш-таблиці
(для порахованих в попередньому пункті 10 хеш-значень намалювати хеш-таблицю без повторень, тобто однакові слова розміщувати в таблицю тільки один раз; слова, що приймали участь у колізіях, підкреслити; визначити кількість кластерів в побудованій таблиці та довжину найбільшого кластера).
0
1
2
3
4
5
6
7
8
9
10
Kyivstar
11
0
12
13
14
15
4
16
17
6
18
19
8
20
9
21
22
23
Pelenskiy
24
25
Igorovuch
26
27
28
29
30
1994
31
32
33
34
35
Vitaliy
36
Кількість кластерів: 8
Довжина найбільшого: 2
3.3. Пошук ключа
(словесно описати процес пошуку в побудованій хеш-таблиці ключа key, де key - передостаннє слово в файлі data.txt ; записати послідовність ключів, з якими відбувається порівняння під час пошуку).
Пошук здійснюється по аналогії до першої таблиці, але він триває доти, доки не знайдеться елемент, інакше його немає в таблиці.
3.4. Результати роботи програми з першою хеш-таблицею
(вивести вигляд побудованої хеш-таблиці, вигляд хеш-таблиці після додавання нового елемента, вигляд хеш-таблиці після вилучення одного елемента, послідовність пошуку ключа key в хеш-таблиці, значення Сni Сm).
Вигляд побудованої хеш-таблиці:
/
Вигляд хеш-таблиці після додавання нового елемента
/
Вигляд хеш-таблиці після вилучення одного елемента:
/
Послідовність пошуку ключа key в хеш-таблиці
Для першої таблиці:
Для другої таблиці:
С1
=
1
C1
=
1
С2
=
1
C2
=
2
С3
=
1
C3
=
3
С4
=
1
C4
=
4
С5
=
1
C5
=
5
С6
=
1
C6
=
6
С7
=
2
C7
=
8
С8
=
1
C8
=
9
С9
=
2
C9
=
11
С10
=
1
C10
=
12
С11
=
2
C11
=
14
С12
=
1
C12
=
15
С13
=
1
C13
=
16
С14
=
2
C14
=
18
С15
=
1
C15
=
19
С16
=
1
C16
=
20
С17
=
2
C17
=
22
С18
=
2
C18
=
24
С19
=
2
C19
=
26
С20
=
3
C20
=
29
С21
=
1
C21
=
30
С22
=
3
C22
=
33
С23
=
3
C23
=
36
С24
=
3
C24
=
39
С25
=
3
C25
=
42
С26
=
1
C26
=
44
С27
=
2
C27
=
46
С28
=
1
C28
=
47
С1
=
1
C1
=
1
С2
=
1
C2
=
2
С3
=
1
C3
=
3
С4
=
1
C4
=
4
С5
=
1
C5
=
5
С6
=
1
C6
=
6
С7
=
1
C7
=
7
С8
=
1
C8
=
8
С9
=
1
C9
=
9
С10
=
1
C10
=
10
С11
=
1
C11
=
11
С12
=
1
C12
=
12
С13
=
2
C13
=
14
С14
=
1
C14
=
15
С15
=
3
C15
=
19
С16
=
1
C16
=
20
С17
=
5
C17
=
25
С18
=
1
C18
=
26
С19
=
3
C19
=
29
С20
=
8
C20
=
37
С21
=
1
C21
=
38
С22
=
3
C22
=
41
С23
=
1
C23
=
42
С24
=
1
C24
=
43
С25
=
1
C25
=
44
С26
=
1
C26
=
45
С27
=
12
C27
=
57
С28
=
15
C28
=
72
4. Аналіз ефективності побудованих методів організації хеш-таблиць.
4.1. Графіки С=f(α) (графік С=f1(α) для хеш-таблиці №1 і графік С=f2(α) для хеш-таблиці №2).
Для таб. 1
α1
=
1
/
37 =
0,027
α2
=
2
37 =
0,054
α3
=
3
/
37 =
0,081
α4
=
4
/
37 =
0,108
α5
=
5
/
37 =
0,135
α6
=
6
/
37 =
0,162
α7
=
7
/
37 =
0,189
α8
=
8
/
37 =
0,216
α9
=
9
/
37 =
0,243
α10
=
10
/
37 =
0,270
α11
=
11
/
37 =
0,297
α12
=
12
/
37 =
0,324
α13
=
13
/
37 =
0,351
α14
=
14
/
37 =
0,378
α15
=
15
/
37 =
0,405
α16
=
16
/
37 =
0,432
α17
=
17
/
37 =
0,459
α18
=
18
/
37 =
0,486
α19
=
19
/
37 =
0,514
α20
=
20
/
37 =
0,541
α21
=
21
/
37 =
0,568
α22
=
22
/
37 =
0,595
α23
=
23
/
37 =
0,622
α24
=
24
/
37 =
0,649
α25
=
25
/
37 =
0,676
α26
=
26
/
37 =
0,703
α27
=
27
/
37 =
0,730
α28
=
28
/
37 =
0,757
Для таб. 1
/
Для таб. 2
/
4.2. Графіки С=f(m) (графік С=f1(m) для хеш-таблиці №1 і графік С=f2(m) для хеш-таблиці №2
4.3. Висновки про ефективність (порівняти ефективності побудованих методів організації хеш-таблиць).
Хеш- таблиця №2 є ефективнішою тому , що при заповненні цієї таблиці та при пошуку будь-якого елемента виникає менша кількість колізій навіть при меншому розмірі таблиці завдяки зміні хеш-функції та функції рехешування на більш ефективні.
Висновки.
На цій лабораторній роботі я ослідив ефективність методів пошуку на прикладі різних методів організації хеш-таблиць. Вивчив основні методи побудови хеш-таблиць, дослідив переваги і недоліки, властиві різним методам, оцінив ефективність і провів порівняння ефективностей.
Додатки
HashTable.h
#pragma once
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
struct Hash
{
string **data;
size_t m;
};
unsigned h(const string key, const unsigned m);
unsigned hi(const string key, const unsigned m, const unsigned i);
bool Add(Hash *hash, const string key);
void Show(const Hash const* hash);
bool Delete(Hash *hash, const string key);
string Find(const Hash const *hash, const string key);
string * FileRead(const char const *FileName);
HashTableOther.сpp
#include "HashTable.h"
unsigned h(const string key, const size_t m)
{
if (key.size() >= 3)
return (key[0]*key[1]*key[2]) % m;
if (key.size() == 2)
return (key[0]*key[1]*key[0]) % m;
if (key.size() == 1)
return (key[0]*key[0]*key[0]) % m;
}
unsigned hi(const string key, const unsigned m, const unsigned i)
{
return (h(key, m) + i) % m;
}
bool Add(Hash *hash, const string key)
{
unsigned k = h(key, hash->m);
unsigned ki, i = 1;
if (hash->data[k][0] == "" || hash->data[k][0] == " ")
{
hash->data[k][0] = key;
return 1;
}
else if (hash->data[k][1] == "" || hash->data[k][1] == " ")
{
hash->data[k][1] = key;
return 1;
}
else if (hash->data[k][2] == "" || hash->data[k][2] == " ")
{
hash->data[k][2] = key;
return 1;
}
else
{
ki = hi(key, hash->m, i);
while (ki != k && hash->data[ki][0] != "" && hash->data[ki][0] != " " && hash->data[ki][1] != "" && hash->data[ki][1] != " " && hash->data[ki][2] != "" && hash->data[ki][2] != " ")
ki = hi(key, hash->m, ++i);
if (ki != k)
{
if (hash->data[ki][0] == "" || hash->data[ki][0] == " ")
{
hash->data[ki][0] = key;
return 1;
}
if (hash->data[ki][1] == "" || hash->data[ki][1] == " ")
{
hash->data[ki][1] = key;
return 1;
}
if (hash->data[ki][2] == "" || hash->data[ki][2] == " ")
{
hash->data[ki][2] = key;
return 1;
}
}
else
{
cout << "All memory used!" << endl;
return 0;
}
}
}
void Show(const Hash const *hash)
{
cout << "________________________________________________________________________________" << endl;
for (unsigned i = 0; i < hash->m; ++i)
cout << i+1 << "\t\t" << hash->data[i][0] << " " << hash->data[i][1] << " " << hash->data[i][2] << endl;
cout << "________________________________________________________________________________" << endl;
return;
}
bool Delete(Hash *hash, const string key)
{
unsigned k, ki, i = 1;
k = h(key, hash->m);
if (key == hash->data[k][0])
{
hash->data[k][0] = " ";
return true;
}
if (key == hash->data[k][1])
{
hash->data[k][1] = " ";
return true;
}
if (key == hash->data[k][2])
{
hash->data[k][2] = " ";
return true;
}
ki = hi(key, hash->m, i);
while (ki != k && hash->data[ki][0] != "" && hash->data[ki][1] != "" && hash->data[ki][2] != "")
{
if (hash->data[ki][0] == key)
{
hash->data[ki][0] = " ";
return true;
}
if (hash->data[ki][1] == key)
{
hash->data[ki][1] = " ";
return true;
}
if (hash->data[ki][2] == key)
{
hash->data[ki][2] = " ";
return true;
}
ki = hi(key, hash->m, ++i);
11.04.2014 14:04-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора