кількості тактів процесора, за яке виконувався пошук тих чи іншим алгоритмом. p align="justify"> Було складено випадковим чином 10 разів три текстових файлу з малих літер латинського алфавіту, довжиною в 1000, 10000 та 100000 символів. У кожному з цих файлів виконувався пошук підрядка, отриманої алгоритмом, що складається з наступних кроків:
Обчислення випадкової довжини підрядка
Для текстового файлу, довжиною 1000 символів обчислювалася випадкова довжина шуканої підрядка від 10 до 50 символів; для текстового файлу, довжиною 10000 символів випадкова довжина підрядка від 100 до 500 символів; і для файлу, довжиною 100000 символів випадкова довжина фрагмента обчислювалася з діапазону від 1000 до 5000 символів;
Обчислення випадкової позиції початку шуканої підрядка у файлі
Для кожного текстового файлу отримували випадкову позицію підрядка з діапазону від 0 до S.Length-X.Length, де S.Length - довжина текстового файлу і X.Length - довжина шуканої підрядка.
Кожен алгоритм виконував пошук однієї і тієї ж підрядка по 10 разів. І в підсумку вибирався найкращий результат серед усіх спроб. p align="justify"> Так як всі алгоритми перебували в рівних умовах, то можна провести порівняльний аналіз. Зауважимо, що отримані дані застосовні тільки для даних параметрів пошуку, і в інших умовах можуть відрізнятися. p align="justify"> Середньостатистичні результати експериментів наведені в Таблиці 1 і проілюстровані на рис. 3. Повний звіт про всі експериментах представлений у Таблиці 2, в Додатку Є.
Таблиця 1. Середньостатистичні результати тестування алгоритмів пошуку
Алгоритм поіскаВремя роботи алгоритму, такти процессора1000 сімволов10 тис. сімволов100 тис.В
Рис. 3. Результати тестування алгоритмів. br/>
З Таблиці 2 видно, що алгоритм Бойєр-Мура впорався з експериментальної завданням швидше за інших. Однак його ефективність зростає із збільшенням довжини вихідної рядки і шуканої підрядка. Тому на вхідному файлі з 1000 символами він показав результат не багато краще за інших алгоритмів. p align="justify"> Алгоритм Кнута-Морріса-Пратта виконав завдання швидше Рабіна-Карпа і Послідовного пошуку, проте істотно поступився Бойєр-Муру. Але до плюса цього алгоритму можна віднести відносно невеликий розкид часу роботи, незалежно від вхідних даних. Що не можна сказати про алгоритм Бойєр-Мура. p align="justify"> Алгоритм Рабіна-Карпа, практично не відрізняється за тимчасовими показниками від алгоритму послідовного пошуку, але його простота і малі трудовитрати на реалізацію, роблять його привабливим для використання в неспеціальних програмах. Також варто відзначити, що він більш ефективно працює на великих алфавітах, де випадкові збіги хеш-функцій практично відсутні, чого не можна відзначити для даного експерименту. br/>
Ви...
