Домашняя работа по предмету «Операционные Системы» на тему хеширование.
Цель данной работы – найти наиболее эффективный алгоритм хеширования для конкретного текста.
Общее описание алгоритма:
f(T) – примарная функция от слова Т.
h = f(T) % TS - целочисленный остаток от деления значения примарной функции на размер хеш-таблицы TS
h = это номер строки, куда будет записано слово Т. В случае, если эта строка уже занята, возникает коллизия.
g2 = f % DIV – функция для выхода из коллизии, вычисляется как остаток от деления примарной функции на число DIV, от 2х до TS-1.
Критерий эффективности алгоритма – число Total Cost, которое является суммой размера таблицы TS и количеством возникших коллизий Collisions. Total Cost = TS+ Collisions Чем меньше число, тем более эффективным считается алгоритм.
Ход работы:
Мне достался следующий кусок английского текста:
These schemes reflect various approaches to memory management, and the effectiveness of the different algorithms depends on the situation. Since main memory is usually too small to accommodate all data and programs, and since it cannot store data permanently , the computer system must pro-vide secondary storage to back up main memory. Most modern computer systems use disks as the primary on-line storage medium for information, both programs and data. The file system provides the mechanism for on-line storage of and access to both data and programs residing on the disks. These chapters describe the classic internal algorithms and structures of storage management.
Программа анализа показывает, что здесь 111 слово, максимальная длина слова – 13 букв.
Количество уникальных слов – 65. Следовательно, минимальный размер хеш-таблицы =65, но это настолько идеальный вариант, что я его даже не рассматривал.
После нескольких попыток работы в веб симуляторе было принято решение использовать готовую программу для перебора всех возможных вариантов TS и DIV для конкретной функции. Я использовал программу «hashcalc» написанную Алексеем Тепляковым в 2008 году для подобной цели. Каждый раз при запуске необходимо вручную вводить минимум и максимум TS, минимум DIV, а также номер конкретной функции f(T) из тех, что присутствуют в файле «hash. c».
Я вводил такие данные: minTS 70, maxTS 160, minDV 70. Так как для экспериментов важна только примарная функция, то я решил дописать «обертку» над уже существующей программой. Основная ее функция – подстановка конкретных значений minTS, maxTS, minDV. А также перебор номера функций от TestCount до 1. Написание обертки заняло около 4х дней, вероятно, если бы я просто руками перебирал функции, это заняло бы максимум 4 часа, но я уверен, что моя работа не напрасна.
Полученная в результате программа – мощный инструмент для исследования разных алгоритмов хеширования и выхода из коллизии.
В своей работе я использовал 4 разных примарных функций разной сложности.
f1= asc(word, 0) * 1 + asc(word, 1) * 2 + ... + asc(word, N) * (N+1);
f2= asc (word, 0) * 5 + asc (word, 1) * 9 + asc (word, 2) * 13;
f3= asc (word, 0) * 15 + asc (word, -1);
f4= asc (word, 0) * 1 + asc (word, 1)*12;
В своей работе я использовал 4 разных набора констант для выхода из коллизий.
case 1:
3; 5; 7; 11; 13; 17; 29;
case 2:
1; 3; 7; 4; 5; 6; 8;
case 3:
10; 20; 30; 40; 50; 60; 70;
case 4:
8; 1; 2; 3; 4; 6; 7;
Результат симуляции первой функции и первого набора констант для выхода из коллизии.
Case 1, f1: Test results: 3548 of 4095 tests were successful. Best parameters for current hash function found are:
Hash table size = 107, divisor = 84; (produced 16 collisions with total cost of 123)
И далее по аналогии.
Case 1, f2: Test results: 3205 of 4095 tests were successful. Best parameters for current hash function found are:
Hash table size = 103, divisor = 73; (produced 29 collisions with total cost of 132)
Case 1, f3: Test results: 2827 of 4095 tests were successful. Best parameters for current hash function found are:
Hash table size = 104, divisor = 81; (produced 51 collisions with total cost of 155)
Case 1, f4: Test results: 2653 of 4095 tests were successful. Best parameters for current hash function found are:
Hash table size = 95, divisor = 80; (produced 68 collisions with total cost of 163)
Case 2, f1: Test results: 3512 of 4095 tests were successful. Best parameters for current hash function found are:
Hash table size = 94, divisor = 91; (produced 30 collisions with total cost of 124)
Case 2, f2: Test results: 3282 of 4095 tests were successful. Best parameters for current hash function found are:
Hash table size = 109, divisor = 87; (produced 27 collisions with total cost of 136)
Case 2, f3: Test results: 2396 of 4095 tests were successful. Best parameters for current hash function found are:
Hash table size = 104, divisor = 99; (produced 54 collisions with total cost of 158)
Case 2, f4: Test results: 2335 of 4095 tests were successful. Best parameters for current hash function found are:
Hash table size = 103, divisor = 75; (produced 54 collisions with total cost of 157)
Case 3, f1: Test results: 2690 of 4095 tests were successful. Best parameters for current hash function found are:
Hash table size = 81, divisor = 77; (produced 35 collisions with total cost of 116)
Case 3, f2: Test results: 1960 of 4095 tests were successful. Best parameters for current hash function found are:
Hash table size = 103, divisor = 76; (produced 37 collisions with total cost of 140)
Case 3, f3: Test results: 1673 of 4095 tests were successful. Best parameters for current hash function found are:
Hash table size = 104, divisor = 71; (produced 45 collisions with total cost of 149)
Case 3, f4: Test results: 962 of 4095 tests were successful. Best parameters for current hash function found are:
Hash table size = 103, divisor = 82; (produced 74 collisions with total cost of 177)
Case 4, f1: Test results: 3454 of 4095 tests were successful. Best parameters for current hash function found are:
Hash table size = 81, divisor = 74; (produced 41 collisions with total cost of 122)
Case 4, f2: Test results: 3205 of 4095 tests were successful. Best parameters for current hash function found are:
Hash table size = 99, divisor = 79; (produced 31 collisions with total cost of 130)
Case 4, f3: Test results: 2685 of 4095 tests were successful. Best parameters for current hash function found are:
Hash table size = 92, divisor = 85; (produced 63 collisions with total cost of 155)
Case 4, f4: Test results: 2447 of 4095 tests were successful. Best parameters for current hash function found are:
Hash table size = 103, divisor = 75; (produced 50 collisions with total cost of 153)
Результаты представлены в таблице:
f1 f2 f3 f4
case 1 123/3548 132/3205 155/2827 163/2653
case 2 124/3512 136/3282 158/2396 157/2335
case 3 116/2690 140/1960 149/1673 177/962
case 4 122/3454 130/3205 155/2685 153/2447
В этой таблице первое значение – эффективность алгоритма, второе значение – количество удачных тестов из 4095.
Анализ полученных результатов.
Из таблицы хорошо видно, что функция f1 является более эффективной нежели f2. А f2 в свою очередь более эффективна чем f3. Самой не эффективной функцией является f4.
С константами выхода из коллизии не все так очевидно, как с примарными функциями. Но можно заметить, что количество удачных тестов для «case 3» сильно меньше, чем для других наборов. Возможно это место для будущих исследователей.
Просмотрев 16 результатов можно заметь, что Hash table size принимает значения от 81 до 107. А divisor лежит в пределах от 71 до 99; количество коллизий – от 16 до 74.
Полученные данные могут быть использованы в будущем, для уменьшения общего колличества тестов.
Наиболее эфективным алгоритмом для моего текста является первая функция и третий набор констант для выхода из коллизий.
Ниже представлен текст для веб-симулятора.
|f=0; for (g1=0; g1<(T. length); g1++) f += (asc(T, g1)*(g1+1));g2=f%77;
|h1=g2+10;
|h2=h1+10;
|h3=h2+10;
|h4=h3+10;
|h5=h4+10;
|h6=h5+10;
|h7=h6+10;
Результат веб-симулятора:
No of words: 111
Table size: 81
Words processed:111 (from 111)
Comparisons: 81
Collisions: 35
Words in table: 65
Load factor: 80.2%
Average probes: 1.32
Cost:116
Далее представлена хеш-таблица и зашифрованный текст.
Hash table:
(0) - depends
(1) -
(2) - approaches
(3) - as
(4) -
(5) - main
(6) -
(7) - on
(8) -
(9) - provides
(10) - internal
(11) - is
(12) -
(13) - it
(14) - to
(15) -
(16) - both
(17) - since
(18) - must
(19) -
(20) - information
(21) - These
(22) -
(23) - too
(24) - cannot
(25) - system
(26) - mechanism
(27) - computer
(28) - secondary
(29) - memory
(30) - storage
(31) - management
(32) - programs
(33) -
(34) - store
(35) -
(36) - on-line
(37) - primary
(38) - disks
(39) - data
(40) -
(41) -
(42) - residing
(43) - usually
(44) - ,
(45) - back
(46) - .
(47) - algorithms
(48) - classic
(49) - reflect
(50) - and
(51) - permanently
(52) - systems
(53) - up
(54) - use
(55) - Most
(56) -
(57) - small
(58) - various
(59) - pro-vide
(60) - the
(61) - describe
(62) - chapters
(63) - structures
(64) -
(65) - different
(66) - Since
(67) - medium
(68) - file
(69) - schemes
(70) - all
(71) - accommodate
(72) - of
(73) -
(74) - access
(75) - situation
(76) - The
(77) -
(78) - modern
(79) - effectiveness
(80) - for
Encoded text: 21 69 49 58 2 14 29 31 44 50 60 79 72 60 65 47 0 7 60 75 46 66 5 29 11 43 23 57 14 71 70 39 50 32 44 50 17 13 24 34 39 51 44 60 27 25 18 59 28 30 14 45 53 5 29 46 55 78 27 52 54 38 3 60 37 36 30 67 80 20 44 16 32 50 39 46 76 68 25 9 60 26 80 36 30 72 50 74 14 16 39 50 32 42 7 60 38 46 21 62 61 60 48 10 47 50 63 72 30 31 46
Выводы: Данная работа показывает, как ленивые студенты двигаются по пути к совершенству, изобретая и развивая все новые и новые инструменты для облегчения своей работы. Однако, как бы не развивались средства автоматизации, самого главного – человеческого разума они не заменят. Именно человек придумывает новые примарные функции, наборы для выхода их коллизий, развивает средства автоматизации.
На этом считаю свою работу завершенной.
