ПОРІВНЯЛЬНИЙ АНАЛІЗ ЧАСОВОЇ ЕФЕКТИВНОСТІ АЛГОРИТМІВ ПОШУКУ ПІДРЯДКА
DOI:
https://doi.org/10.34185/1991-7848.itmm.2025.01.045Ключові слова:
інформаційна технологія, машинний експеримент, S- та R-показники, алгоритм пошуку підрядка, часова ефективність алгоритмуАнотація
У статті проведено порівняльний аналіз часової ефективності чотирьох класичних алгоритмів пошуку підрядка (string searching algorithms), що намагаються знайти позицію, де один або декілька текстових рядків (зразків) входять у довший рядок або текст. Порівнювались наступні алгоритми: наївного пошуку (перебору, або ж брут-форс), Кнута-Морріса-Пратта (КМП), Боєра-Мура та Рабіна-Карпа. Дослідження проводилось на трьох різних архітектурах процесорів та з трьома наборами вхідних даних різного обсягу. Алгоритми тестувались за умов як холодного, так і прогрітого кешу. Для зниження впливу сторонніх чинників було реалізовано запуск на одному процесорному ядрі та примусове очищення пам’яті після кожного тесту. Результати експериментів проаналізовано за допомогою розрахунків S- та R-показників ефективності, надано рекомендації щодо доцільності застосування кожного окремого алгоритму в різних умовах.
Посилання
Shynkarenko V. I. Comparative Analysis of Time Efficiency of Functionally Equivalent Algorithms. Problems of Programming, 2001, Vol. 3–4, pp. 31–39.
Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms. MIT Press. – 2009. 1292 p.
Knuth D.E., Morris J.H., Pratt V.R. Fast Pattern Matching in Strings. SIAM Journal on Computing. – 1977. Vol. 6(2). P. 323–350.
Boyer R. S., Moore J. S. A Fast String Searching Algorithm. Communications of the ACM. – 1977. Vol. 20(10). P. 762–772.
Karp R. M., Rabin M. O. Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development. – 1987. Vol. 31(2). P. 249–260.
