Підрядок | Алгоритм | Стаття 1 (сек) | Стаття 2 (сек) |
---|---|---|---|
алгоритмів | Boyer-Moore | 0.013954 | 0.154882 |
алгоритмів | KMP | 0.025298 | 0.402018 |
алгоритмів | Rabin-Karp | 0.064253 | 0.904445 |
неіснуючий підрядок для тестування | Boyer-Moore | 0.223007 | 0.348797 |
неіснуючий підрядок для тестування | KMP | 1.36795 | 2.00499 |
неіснуючий підрядок для тестування | Rabin-Karp | 3.40861 | 5.62853 |
Результати тестів швидкодії різних алгоритмів пошуку рядку показують наступні висновки:
- Цей алгоритм виявився найшвидшим для пошуку підрядка "алгоритмів" у обох статтях. Його час виконання у Статті 1 становить 0.013954 секунд, а у Статті 2 — 0.154882 секунд.
- Для підрядка "неіснуючий підрядок для тестування" Boyer-Moore також був найшвидшим, але час виконання значно зріс до 0.223007 секунд у Статті 1 і 0.348797 секунд у Статті 2. Це пояснюється тим, що Boyer-Moore краще працює з короткими підрядками.
- Цей алгоритм був повільнішим за Boyer-Moore у всіх тестах, але швидшим за Rabin-Karp для підрядка "алгоритмів". У Статті 1 його час виконання становить 0.025298 секунд, а у Статті 2 — 0.402018 секунд.
- Для підрядка "неіснуючий підрядок для тестування" KMP був повільнішим: 1.36795 секунд у Статті 1 і 2.00499 секунд у Статті 2. Це свідчить про те, що KMP може бути менш ефективним для довгих підрядків.
- Цей алгоритм показав найгірші результати у всіх тестах. Для підрядка "алгоритмів" його час виконання становив 0.064253 секунд у Статті 1 і 0.904445 секунд у Статті 2.
- Для підрядка "неіснуючий підрядок для тестування" час виконання був значно більшим: 3.40861 секунд у Статті 1 і 5.62853 секунд у Статті 2. Це показує, що Rabin-Karp є менш ефективним для довгих підрядків і для великих текстів.
Boyer-Moore є найефективнішим алгоритмом для пошуку коротких і довгих підрядків у великих текстах. Він має найменші часи виконання у всіх тестах.
KMP займає середнє місце між Boyer-Moore і Rabin-Karp за швидкодією. Він показав добрі результати для коротких підрядків, але значно повільніший для довгих підрядків.
Rabin-Karp є найменш ефективним алгоритмом у даних тестах. Його час виконання значно перевищує Boyer-Moore і KMP у всіх випадках.