і критерії оцінки не дозволяють нам напевно сказати, який з алгоритмів буде швидше працювати. Тому, для додаткової оцінки проведемо їх експериментальний аналіз, тобто виміряємо час, за яке алгоритм виконує конкретно поставлене завдання.
Є декілька текстових файлів, містять 10000 записів види:
рядок
підрядок (наявна в цьому рядку)
місце входження
довжина підрядка
з різними максимальними довжинами рядків та подстрок.
Алфавітом є 66 російських великих і малих літер.
Нехай це будуть рядка довжиною не більше 10, 100, 250 символів.
Проведемо пошук подстрок у рядках для кожного з алгоритмів і виміряємо час роботи програми. При цьому будемо враховувати наступне:
В· Рядки попередньо завантажуємо в оперативну пам'ять (у вигляді масиву), причому час зчитування в масив не враховується. Передобробка (створення таблиць переходу) входить до загальний час.
В· Кожен алгоритм запускається 5 разів, час вибирається найменше.
Стенд для експерименту.
Процесор Intel Pentium IV 2,66 Ггц
1024 Мб ОЗУ
Компілятор Borland Delphi Enterprise, version 6.0 (Build 6.163)
Фрагмент коду тестує програми наведемо в лістингу 7.
В
LoadFromFile ('C: String_250.txt');
{Відбувається завантаження в масив}
Tick: = GetTickCount
;
{Запам'ятовуємо текцщее значення змінної Tick }
Poisk;
{Процедура в якій відбувається пошук 10000 разів}
Tick: = GetTickCount-Tick;
{Отримуємо різницю - час в мілісекундах}
WriteLn ('Za vremja', Tick, ' ms ');
В В В В В
Зрозуміло, що такий замір часу дасть нам вельми розпливчасті результати, оскільки безпосередньо залежить від характеристик і завантаження процесора. Тому під час проведення експерименту, відключалися всі сторонні та фонові програми, які не впливають на роботу програми. При запуску однієї і тієї ж задачі ми можемо отримати різне час, тому відбувається кілька запусків, з яких вибирається найкращий результат.
2.2. Результати та аналіз експерименту.
Експеримент проводився для чотирьох алгоритмів - представників класів алгоритмів. Так як всі алгоритми ставилися в однакові умови, то можна провести їх порівняльний аналіз. Зауважимо, що даний аналіз застосуємо тільки для даних параметрів пошуку, і при інших умовах може відрізнятися. p> Результати експерименту занесемо в таблицю (Табл. 3).
Алгоритм
Час виконання
Довжина ≤ 10
Довжина ≤ 100
Довжина ≤ 250
Послід. пошук
15
93
234
Алгоритм Рабіна
(Хеш - сума кодів)
15
63
93
КМП
5
30
50
БМ
31
31
32
Як і передбачалося, алгоритм Бойєр - Мура впорався з експериментальної завданням швидше за інших. Слід, однак, зауважити, що його ефективність зростає лише зі збільшенням довжини рядка і, відповідно, довжини зразка. Так при довжині рядка меншою або рівною 10 символів, він показав себе гірше, ніж послідовний пошук. Аналогічні результати показує і алгоритм КМП, як для коротких, так і для довгих слів. Його можна використовувати як універсальний, коли невідомі довжини рядка і зразка. p> Алгоритм Рабіна, при його схожості з послідовним працює швидше, а його простота і малі трудовитрати на реалізацію, роблять його привабливим для використання в неспеціальних програмах.
Найгірший результат показав алгоритм послідовного пошуку. Як передбачалося лише при невеликому збільшенні довжини рядка, він працює в рази повільніше інших алгоритмів.
У даний експеримент не включений алгоритм пошуку за допомогою кінцевого автомата, тому що ми використовуємо алфавіт, що складається з 66 букв російського алфавіту, і побудований автомат був би занадто громіздкий. Ефективність цього алгоритму зростає при малій кількості букв в алфавіті.
Висновок.
Ми...
