Boyer-Moore vs KMP

https://lms0806.tistory.com/210

A Fast StringSearching Algorithm 리뷰

이전 포스팅에서 보이어-무어에 대해 설명중인 논문에 대해 설명을 했었습니다.

https://lms0806.tistory.com/211

JAVA에서의 Boyer-Moore

또한 JAVA에서 어떤 부분에서 boyer-moore가 사용중인지에 대해서도 이야기를 했었습니다.

 

이번 시간에는 boyer-moore와 kmp, java의 내부 라이브러리 함수들을 시간측정을 진행해보았습니다.

 

랜덤 데이터

개수 / String (n) / Pattern (m)	브루트포스	Boyer-Moore	KMP	String contains	String indexOf	String lastIndexOf
1,000 / 10,000 / 100	161	50	46	23	16	21
1,000 / 100,000 / 1,000	7,084	99	324	181	172	176
1,000 / 100,000 / 10,000	63,068	107	344	160	160	161
1,000 / 1,000,000 / 10,000	703,791	787	3,032	1,720	1,718	1,735
100,000 / 1,000 / 100	1,179	1,273	411	36	22	179

 

가장 마지막에 찾고자 하는 문자가 있는 경우

개수 / String (n) / Pattern (m)	브루트포스	Boyer-Moore	KMP	String contains	String indexOf	String lastIndexOf
1,000 / 10,000 / 100	520	147	157	456	367	2
1,000 / 100,000 / 1,000	23,189	69	1,016	21,000	21,591	7
1,000 / 100,000 / 10,000	194,189	105	1,177	185,896	203,857	20
10,000 / 1,000,000 / 1,000	29,677	348	2,693	44,380	20,145	181
100,000 / 1,000 / 100	2,341	3,766	692	987	861	28

 

추가로, apache의 StringUtils의 contains도 같은 기능을 지원하지만, 내부 소스를 따라가다보면 결과적으로 String의 indexOf 함수를 사용하는 것을 볼 수 있었습니다.

내부 함수들을 타고타고 가다보니 자연스럽게 contains보다 시간이 더 오래 소모되었습니다.

 

해당 테스트를 진행하면서 사용한 KMP와 boyer-moore 코드는 깃헙에 저장되어 있습니다.

 

Boyer-Moore 알고리즘이 사용중인 곳

• JAVA의 Pattern()
• Golang의 find()
• cpython의 find()
• PostgreSql의 LIKE
• MySql의 LIKE