std::string.find() 의 성능

얼마 전에 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이라고 만능이 아니다.