Python string.find()의 성능

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

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

 

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

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

Published by

rein

나는 ...

6 thoughts on “Python string.find()의 성능”

  1. 본문의 내용과는 그닥상관없지만 ‘제공하는 라이브러리’ 면에 불만이 좀 있는게, C++ 표준 라이브러리가 복잡한 프로그램을 만드는 데 있어서 참고할 게 별로 없다.
    API 디자인면이라든가, 관행이라든가, 먼가 참고할만한 ‘the one standard’ 이런걸 안줌.
    쫌만 큰 프로그램 만들려고해도 이래저래 부족한게 많고.
    소프트웨어의 컴포넌트로는 쓰기좋은데 그 관행을 따라 확장해서 소프트웨러를 덧붙여나갈 대상이 되지 않아.

    그러고보면 그게 ‘프레임워크’ 인지도 ㅋ
    그런게 없는상태에서 프로젝트를 하다보면 어! 스트림 라이브러리가 필요해! 이러고 일주일동안 짬 ㅅㅂ

    그런의미에서 닷넷이나 자바는 한번쯤 써볼 필요가 있음.. C++ 프로그래머라도..

  2. 네 댓글엔 나도 매우 동의한다. 쓰기 편한 컴퍼넌트이긴해도, 그 자체로 어떤 라이브러리 철학을 제시해주진 못하고.

    결정적으로 외부에서 만들어진 라이브러리를 안쓰면 라이브러리 전체가 너무 빈약해

  3. 음…. C#을 주로 쓰다가 이제 막 C++을 주력으로 쓰게 된 저에겐 시사하는 바가 큰 사실이네요. 조심해서 써야겠어요.

  4. 최재훈 / 약간 조심해야하긴 하겠지만 큰 문제는 아닐 것 같기도해요. 테스트 자체를 극단적인 케이스로 해서 진행한데다가 아침에 와서 생각 좀 해보니 지금 테스트한 방법 자체가 파이썬 쪽에 구현된 알고리즘에 너무 유리해요 :)

    그래서 짬나는데로 “임의의 문자열”에 가까운걸 써서 테스트를 해봐야할 것 같습니다.

  5. C#이 좀 재밌는듯. 초기에 – 그러니까 바꿀 수 있을 때 – 최대한 변경을 가하려는거 같아서 약간 롤러코스터 타는 기분이지만;

Leave a Reply