얼마 전에 jstrane군이 std::string.find()가 느리다고 불평하면서 linux/g++로 성능을 테스트해서 포스팅한 것이 있다. 그런 의미에서(?) Win32/VC++ 환경에서도 테스트를 진행해봤다. 옆의 그래프가 WindowsXP/VC++2005를 가지고 테스트한 결과다. (테스트 설계는 jstrane 블로그를 참조하자; naive 입력에 대해서 최악의 성능을 뽑아내는 방식이다)
(그래프를 클릭하면 원본으로 연결됨)
길이에 대한 std::string.find()의 성능 그래프가 아름다운(…) 2차곡선을 그리고 있다. 즉, 원본 문자열의 길이가 m, 찾으려는 패턴의 길이가 n일 때 O(mn)의 성능을 보여준다는 것이다.
jstrane이 테스트한 경우에도 그랬지만 STL의 string.find() 함수 구현이 naive한 형태이기 때문에 생기는 문제다. 그러니 성능이 매우 중요한 문자열 찾기라면 Knuth-Morris-Pratt 알고리즘이나 Boyer-Moore 알고리즘을 상황에 맞게 써 줘야 할 것이다. STL이라고 만능의 무기는 아닌 것이다 :D
역시 MS VC++ 2005 의 STL 구현도 비슷하군요. 아마 Dinkumware 겠지요? 이제 남은건 STLPort 정도가 있으려나 … 파이썬 라이브러리도 테스트 해보면 재밌을거 같은데 귀찮음이 몰려오네요. orz
근데 생각해보면 *별로 길지 않고 / 전처리 시간도 아까운 횟수에서* 복잡한 알고리즘을 쓰는 것도 참 의미없어 보이긴하다 -_-a
뭐 그냥저냥 짧은 길이에선 O(mn) 시간 복잡도가 나와도 버틸만하니;