Boyer-Moore vs KMP
https://lms0806.tistory.com/210
A Fast StringSearching Algorithm 리뷰
해당 논문은 boyer–moore 알고리즘 이라고 불리는 kmp와 비슷한 알고리즘에 대하여 설명하고 있습니다. 보이어무어 알고리즘은 불필요한 것은 건너뛰고, 검색을 빠르게 하자는 것에서 KMP와 유사
lms0806.tistory.com
이전 포스팅에서 보이어-무어에 대해 설명중인 논문에 대해 설명을 했었습니다.
https://lms0806.tistory.com/211
JAVA에서의 Boyer-Moore
해당 글은 보이어 무어 알고리즘을 사용하고 있는 JAVA의 내부 코드에 대해 이야기하고자 합니다.Boyer-Moore에 대해서는 해당 글 참조 부탁드립니다.https://lms0806.tistory.com/210 A Fast StringSearching Algorit
lms0806.tistory.com
또한 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 알고리즘이 사용중인 곳