Lab №1. Substring search problem

Results for goodXXX.txt

5 observations for each algorithm

Время представлено с точностью в 5 знаков

---

Имя файла	Метод	Среднее время работы в сек.	Число операций	Размер файла
good_t_1.txt	BoyerMoore	1e-05	75	694
good_t_1.txt	KarpRabin	0.0001	710	694
good_t_1.txt	KnuttMorrisPratt	4e-05	684	694
good_t_1.txt	BruteForce	3e-05	634	694
good_t_2.txt	BoyerMoore	1e-05	122	1158
good_t_2.txt	KarpRabin	0.00017	1090	1158
good_t_2.txt	KnuttMorrisPratt	4e-05	865	1158
good_t_2.txt	BruteForce	3e-05	696	1158
good_t_3.txt	BoyerMoore	4e-05	481	3438
good_t_3.txt	KarpRabin	0.00045	3062	3438
good_t_3.txt	KnuttMorrisPratt	0.00016	2892	3438
good_t_3.txt	BruteForce	0.0001	2075	3438
good_t_4.txt	BoyerMoore	7e-05	544	10714
good_t_4.txt	KarpRabin	0.00169	10745	10714
good_t_4.txt	KnuttMorrisPratt	0.0006	9798	10714
good_t_4.txt	BruteForce	0.00045	9615	10714

Вывод

В данном случае наилучшее время работы и наименьшее число операций у алгоритма Бойера-Мура

Results for badXXX.txt

5 observations for each algorithm

Время представлено с точностью в 5 знаков

---

Имя файла	Метод	Среднее время работы в сек.	Число операций	Размер файла
bad_t_1.txt	BoyerMoore	0.0	11	10
bad_t_1.txt	KarpRabin	0.0	13	10
bad_t_1.txt	KnuttMorrisPratt	0.0	30	10
bad_t_1.txt	BruteForce	0.0	19	10
bad_t_2.txt	BoyerMoore	1e-05	101	100
bad_t_2.txt	KarpRabin	2e-05	271	100
bad_t_2.txt	KnuttMorrisPratt	1e-05	300	100
bad_t_2.txt	BruteForce	4e-05	911	100
bad_t_3.txt	BoyerMoore	0.00012	1001	1000
bad_t_3.txt	KarpRabin	0.00012	901	1000
bad_t_3.txt	KnuttMorrisPratt	0.00012	3000	1000
bad_t_3.txt	BruteForce	0.00401	90101	1000
bad_t_4.txt	BoyerMoore	0.00059	5001	5000
bad_t_4.txt	KarpRabin	0.00055	4001	5000
bad_t_4.txt	KnuttMorrisPratt	0.00068	15000	5000
bad_t_4.txt	BruteForce	0.18524	4001001	5000

Вывод

В целом, выводы аналогичны, но на больших файлах заметно, что алгоритм Рабина-Карпа показывает себя несколько лучше

Team Members

• Alexander Slavutin
• Pavel Semkin

Copyright (C) 2020-2021, Bolik&Lolik Inc. , all rights reserved.