Python string.find()의 성능

바로 직전에 C++ STL의 std::string.find()의 성능을 테스트했다. 그리고 실망했다. 이번에는 요즘 널리 사용되고 있는 스크립트 언어 중 하나인 Python의 문자열을 가지고 테스트를 진행해봤다.

이전 테스트와 동등한 머신에서 WindowsXP/Python2.5을 사용하여 테스트를 수행하였다. Python의 문자열 검색이 일정 길이 이상에선 STL의 문자열 검색보다 월등히 빨랐다. 테스트 범위의 문자열에서 100ms초 이하에 검색이 끝나는 결과를 보여줬다 – 짧은 길이에서는 너무 빨리 결과가 나와서 100번 정도 루프를 돌리고 시간을 측정해야 했다. 그리고 가장 중요한 것, 문자열 길이를 늘려가는 것에 대해(이전 테스트처럼 원본 문자열과 패턴 문자열을 모두 증가) 선형으로 복잡도가 증가했다. Python 라이브러리의 문자열 검색은 단순한 (naive) 구현이 아닌 것.

확인해 본 결과, Python의 문자열 검색 알고리즘은 2.5 버젼에서 개선되었는데(그 이전에도 선형복잡도인듯하지만), Boyer-Moore 알고리즘을 개선한 알고리즘을 구현했다고 한다. 덕분에 저런 멋진 속도가 나온다.

C++은 속도를 중시한 언어이긴하지만 _라이브러리의 완비성(completeness)_은 거의 제공하지 않는다. 반대로 최근에 나온 언어 – 특히 스크립트 언어들 – 는 라이브러리가 완비된 상태로 나온 경우가 대부분이다. 그래서 Python이나 C#, Java 같은 언어에서는 거의 전적으로 라이브러리에 의존하고도 프로그래밍을 할 수 있지만, C++의 문자열 검색같은 부분은 함부로 의존했다가는 조금 곤란할 것이다.