Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розробка та дослідження ефективності методів пошуку даних
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2012
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Інші
Група:
КІ-25
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет “Львівська Політехніка”
Кафедра ЕОМ
Звіт
До лабораторної роботи №7
На тему “ Розробка та дослідження ефективності методів пошуку даних ”
Завдання
Написати програму, що отримує на вході послідовність слів (ключів), будує дві хеш-таблиці цих слів, виконує операції додавання нових слів в побудовані хеш-таблиці та вилучення заданих елементів з таблиць, виводить на екран вміст кожної таблиці, здійснює багаторазовий пошук довільних слів в цих хеш-таблицях, порівнює ефективності різних методів організації хеш-таблиць.
Список вхідних слів довжиною n=28 задати у вигляді текстового файла data.txt . Файл data.txt має містити таку інформацію (всі слова (або числа) записуються латинськими літерами підряд через кому):
прізвище, ім'я, побатькові,
день, місяць,рік народження,
назва компанii мобільного зв'язку,
підряд через пробіл всі цифри мобільного телефона, починаючи з кода оператора (всього 10 цифр),
назва області, міста і вулиці в адресі прописки,
номер будинку і квартири в адресі прописки,
абревіатура інститута, кафедри, групи,
день, місяць,рік виконання лабораторної роботи.
Весь вхідний список слів розмістити в першій хеш-таблиці розмірністю m=37, метод побудови якої вибрати згідно з варіантом. Також весь вхідний список слів розмістити у другій хеш-таблиці, метод побудови якої вибрати самостійно. Забороняється вибирати хеш-функції, що співпадають з прикладами хеш-функції, наведених в цих методичних вказівках. При виборі хеш-функції намагатись, щоб ефективність організації другої таблиці була вищою, ніж першої.
Забезпечити виконання програмою на вимогу користувача операцій додавання та вилучення елементів з хеш-таблиць.
В процесі роботи з таблицями на вимогу користувача програма повинна виводити на екран вміст кожної хеш-таблиці.
Код програми
#include <iostream>
#include <string>
#include <fstream>
#include <string>
using namespace std;
int func_hesh1_met_1(char a[]);
int func_hesh1_met_2(char *a,int i);
int func_hesh2_met_3(char *a,int i);
int add(char Hesh2_m1[37][128],char str[128]);
int main(){
char Hesh1_m1[37][128];
char Hesh2_m1[37][128];
char a[28][128];
int i=0;
int j=0;
int n=128;
for(i=0;i<37;i++){
for(j=0;j<128;j++){
Hesh1_m1[i][j]=NULL;
Hesh2_m1[i][j]=NULL;}}
for(i=0;i<28;i++){
for(j=0;j<128;j++){
a[i][j]=0;}}
ifstream file("data.txt");
for(int i=0;i<28;i++){
file >> a[i];
}
file.close();
//хеш таблиця номер 1
for(int i=0;i<28;i++)
{
int indx=1;
int buff;
int g=0;
do{
buff=func_hesh1_met_2(a[i],indx);
if(Hesh1_m1[buff][0]==NULL)
{
g=1;
for(j=0;j<128;j++){
Hesh1_m1[buff][j]=a[i][j]; }
}
else
indx++;}
while(g!=1);}
for(i=0;i<37;i++){
cout<<endl;
for(j=0;j<28;j++){
cout<<Hesh1_m1[i][j];}}
cout<<endl<<"XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"<<endl;
//хеш таблиця номер 2
for(int i=0;i<28;i++){
int indx=1;
int buff;
int g=0;
do{
buff=func_hesh2_met_3(a[i],indx);
if(Hesh2_m1[buff][0]==NULL){
g=1;
for(j=0;j<128;j++){
Hesh2_m1[buff][j]=a[i][j];}}
else
indx++;}
while(g!=1);}
for(i=0;i<37;i++){
cout<<endl;
for(j=0;j<28;j++){
cout<<Hesh2_m1[i][j];}}
cout<<endl<<"ADD-XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"<<endl;
char str[128];
for(j=0;j<128;j++){
str[j]=0;}
cin>>str;
int g=0;
g=add(Hesh2_m1,str);
for(j=0;j<128;j++){
Hesh2_m1[g][j]=str[j];}
for(i=0;i<37;i++){
cout<<endl;
for(j=0;j<28;j++){
cout<<Hesh2_m1[i][j];}}
cout<<endl;
return 0;}
int func_hesh1_met_1(char a[]){
return (a[0]%37);}
int func_hesh1_met_2(char *a,int i) {
return ((func_hesh1_met_1(a)+i + 4*i^2) % 37);}
int func_hesh2_met_3(char *a,int i) {
return ((func_hesh1_met_1(a)+i) % 37);}
int add(char Hesh2_m1[37][128],char str[128]){
int buff;
buff=func_hesh2_met_3(str,1);
return buff;}
Перша хеш таблиця
/
Друга хеш таблиця
/
Друга хеш таблиця після додавання елемента
/
Пошук існуючого елемента в хеш таблиці Пошук неіснуючого елемента в хеш таблиці
Аналіз ефективності.
На основі вигляду першої хеш таблиці можна зробити висновок про те, що вона буде більш ефективною. Це можна визначити підрахувавши кількість утворених кластерів.
В першій хеш таблиці є 8 кластерів, і найбільший з них має 11 елементів.
В другій хеш таблиці утворилося 4 кластери, і найдовший з них має 22 елементи.
Ефективнішою таблицею буде перша, оскільки негативно на швидкість пошуку впливає довжина кластера, яка впливає на максимальну кількість порівнянь.
В першій хеш таблиці максимальна довжина кластера 11 елементів, відповідно необхідно виконати в найгіршому випадку 11 порівнянь
В другій хеш таблиці максимальна довжина кластера 22 елементи, відповідно в найгіршому випадку необхідно буде виконати 22 порівняння.
Отже перша хеш таблиця є більш ефективною ніж друга.
Висновок: я дослідив ефективність методів пошуку на прикладі різних методів організації хеш-таблиць, та вивчив основні методи побудови хеш-таблиць, дослідив переваги і недоліки, властиві різним методам, оцінив ефективність і провів порівняння ефективностей.
25.11.2012 18:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора