| | | | | |
 |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
한글판 johnsonj 2007.01.27 파이썬에서 효율적인 문자열 결합 방법여러 방법의 수행성능 평가들어가는 말기다란 문자열을 파이썬으로 구축하려면 코드 실행이 아주 느린 경우가 많다. 이 글에서는 다양한 문자열 결합 방법의 계산 성능을 조사해 보겠다. 파이썬에서 문자열 객체는 교환불능이다 - 문자열이 변수에 할당될 때마다 새로운 객체가 메모리에 생성되어 그 값을 대표한다. 이는 펄과 베이직 같은 언어와 대조적이다. 그런 언어에서는 문자열 변수를 제자리에서 변경할 수 있기 때문이다. 여러 짧은 토막들을 모아 기다란 문자열을 구성하는 일반적인 연산은 파이썬에서 매우 비효율적이다. 기존의 문자열의 끝에다 새로운 토막을 덧 붙이는 접근법을 사용한다면 말이다. 문자열의 끝에 덧붙일 때마다, 파이썬은 새로운 문자열 객체를 만들어서 기존의 문자열과 추가된 문자열의 내용을 모두 거기에다 복사해야 한다. 조작하고 있는 문자열이 커질 수록 이 과정은 점점 더 느려진다. 다른 방법은 무엇이 있으며 어떻게 수행성능을 비교할까? 아주 기다란 문자열을 구성하여 효율성이 어떻게 달라지는지 여러 다른 접근법을 테스트해 보기로 하였다. 비교를 위해 테스트 문제가 필요했다. 많은 개수의 토막으로부터 아주 긴 문자열을 구성하고 다른 계산을 별로 하지 않아야 했다. 그래야 수행성능의 평가가 오직 문자열 연산 수행성능에만 의존하기 때문이다. 본인이 사용한 테스트 사례는 0에서부터 좀 커다란 수까지 주욱 일련의 정수를 결합하는 것이다. 이 숫자는 쉽게 바꿀 수 있어서 생산된 문자열의 크기를 달리할 수 있다. 예를 들어 첫 20개의 정수는 다음과 같은 문자열이다: 여섯가지 방법다음 여섯가지 방법을 테스트했다. 이 여섯가지 파이썬 코드는 똑 같은 출력 문자열을 계산한다.방법 1: 유치한 추가방법def method1():
out_str = ''
for num in xrange(loop_count):
out_str += `num`
return out_str
나에게는 이것이 문제에 대한 아주 확실한 접근법이다. 결합 연산자(+=)를 사용하여 각 토막을 문자열에 추가한다. loop_count는 사용할 문자열의 개수를 제공한다. 역인용부호( 방법 2: MutableString 클래스def method2():
from UserString import MutableString
out_str = MutableString()
for num in xrange(loop_count):
out_str += `num`
return out_str
파이썬 라이브러리에는 MutableString이라는 클래스가 있다. 문서에 의하면 이 클래스는 교육적 목적을 위한 것이라고 한다. 교환 불능 문자열에 append 연산자는 문자열을 재할당하지 않거나 복사를 하지 않을 것이다. 테스트에서 이 방법은 방법 1보다 훨씬 더 수행성능이 나빴다. UserString.py 소스를 들여다 보다가 MutableString을 위한 저장소가 그냥 문자열 유형의 클래스 멤버이고 실제로 MutableString은 방법 3: 문자 배열def method3():
from array import array
char_array = array('c')
for num in xrange(loop_count):
char_array.fromstring(`num`)
return char_array.tostring()
이 방법은 거의 시도해 본 적이 없지만 언제인가 메일링 리스트에서 그 제안을 본 적이 있다. 그래서 한 번 시험해 보기로 했다. 그 아이디어는 문자 배열을 사용하여 문자열을 저장하는 것이다. 배열은 파이썬에서 교환가능하며, 그래서 제자리에서 변경할 수 있다. 기존의 배열 내용을 복사할 필요가 없다. 이 경우 기존의 배열 요소를 변경하는 것에는 관심이 없다. 단지 새로운 배열 요소들을 그 배열의 끝에 추가하고 싶을 뿐이다. 방법 4: 문자열 리스트를 구축한 다음, 그것을 결합하는 법def method4():
str_list = []
for num in xrange(loop_count):
str_list.append(`num`)
return ''.join(str_list)
이 접근법은 자주 문자열 결합에 아주 파이썬스러운 방법이라고 제안된다. 먼저 구성 문자열 각각을 담고 있는 리스트가 구축된다. 다음 단 한번의 join 연산으로 문자열이 구성된다. 문자열에는 추가된 모든 리스트 요소들이 담긴다.
마지막 줄에 좀 웃기게 생긴 파이썬 관용구가 하나 있다 - 빈 문자열로 식별되는 객체의 join 메쏘드를 호출한다. 문자열 기호상수에다 메쏘드를 호출하는 언어는 별로 많지 않다. 좀 기분이 그러면, 대신에 다음과 같이 작성해도 된다: 방법 5: 의사 파일에 쓰는 방법def method5():
from cStringIO import StringIO
file_str = StringIO()
for num in xrange(loop_count):
file_str.write(`num`)
return file_str.getvalue()
cStringIO 모듈은 StringIO라는 클래스를 제공한다. 마치 파일처럼 움직이지만, 문자열로 저장된다. 파일에 추가하는 것이 확실히 쉽다 - 파일의 끝에다 그냥 추가하기만 하면 된다. 그 것이 이 모듈에 똑 같이 적용된다. 비슷한 모듈로 그냥 StringIO이 있지만, 그것은 파이썬으로 구현되었고 반면에 cStringIO는 C로 구현되었다. 뒤의 것이 확실히 빠르다. 이 객체를 사용하여 한 번에 하나씩 문자열을 구축한 다음 흥미롭게도 자바에서 문자열 객체는 파이썬과 똑같이 교환불능이다. 자바에는 StringBuffer라는 클래스가 있다. 이 클래스가 파이썬 StringIO나 배열 접근법보다 약간 더 강력하다. 왜냐하면 문자열의 추가와 더불어 하부-문자열의 삭제와 삽입도 지원하기 때문이다. 방법 6: 리스트 통합(List comprehensions)def method6(): return ''.join([`num` for num in xrange(loop_count)])
이 방법이 코드가 제일 짧다. 더욱 놀라운 것은 속도도 제일 빠르다는 것이다. 아주 간결하고 또한 이해하기도 아주 쉽다. 리스트 통합을 사용하여 숫자 리스트를 작성한 다음 그것들을 모두 하나로 조립하자. 이보다 더 쉬울 수는 없을 것이다. 이것은 실제로는 그저 방법 4를 축약한 버전이다. 메모리도 거의 같은 양을 소비한다. 그럼에도 더 빠른 이유는 회돌이를 돌 때마다 매번 결과계산하는 동안 파이썬이 문자열을 구축하는데 든 시간과 파이썬이 사용한 메모리 양을 모두 보고 싶었다. 메모리는 별로 들지 않았지만, 두 가지 이유로 그것이 중요한 요인이 될 수 있다. 파이썬은 고정된 자원 한계를 강요하는 시스템에서 실행될 수도 있다. 예를 들어, 공유 웹 호스팅 환경에서, 머신은 각 프로세스마다 메모리 크기를 제한하도록 환경이 구성되어 있을 수 있다. 전형적으로 커널은 메모리가 할당량을 초과하면 프로세스를 죽일 것이다. 그런 일은 CGI 스크립트에 성가신 일이며, 오랫동안-생존한 서버 프로세스에는 정말 불행한 일이다. 그래서 그런 경우 메모리 사용이 예상치 못하게 확대되는 것을 막는 일이 중요하다. 다른 이유는 아주 큰 문자열을 처리할 때, 인터프리터의 메모리 할당을 늘리면 가상 메모리 시스템이 그 프로세스를 디스크로 페이지 아웃시킬 가능성이 있다. 그러면 수행성능은 정말로 급격하게 떨어질 것이다. 가장 빠른 알고리즘을 발견하면 세상에서 문제가 되지 않는다 - 메모리를 너무 많이 사용하면 무지하게 느려질 것이다. 메모리를 더 사용하는 알고리즘을 사용한다면, 페이징의 가능성이 줄어들고 좀 수행성능의 예측 가능성을 높일 수 있을 것이다.
독자적인 파이썬 프로세스를 사용하여각 메쏘드들을 따로 따로 테스트하도록 노력하였다. 결과: 2만개의 정수첫 테스트에서 20,000개의 정수가 86kb 길이의 문자열로 결합되었다.
결과: 50만 개의 정수다음으로 500,000개의 정수를 2,821 kB 길이의 문자열로 결합하여 각 방법을 수행하도록 시도하였다. 이는 훨씬 더 심각한 테스트이다. 이 계산에 사용된 데이터 구조에 적응하기 위하여 파이썬 인터프리터 프로세스의 크기가 커지기 시작한다.
이 테스트를 방법 1과 2를 사용하여 완벽하게 실행하려고 고민하지 않았다. 이 방법들은 각 추가 연산 때마다 전체 소스 문자열을 복사한다. 그래서 수행성능은 O(n^2)이 될 것이다. 이런 방법들을 사용하여 50만개의 정수를 결합하려면 몇 분이나 걸릴 것이다. 이 테스트에 대한 결과를 앞의 그래프와 비교해서, 초당 결합의 숫치가 방법 3, 4 & 6에 대하여 더 느리다는 것을 주목하자. 그렇게 놀라운 일은 아니다 - 이 테스트에서 각 정수의 문자열 표현은 약간 더 길다 - 보통 4자리가 아니라 5자리이다. 첫 번째 테스트에서 방법 3은 앞의 두 방법보다 10배 더 수행성능이 좋다. 그러나 더 길게 테스트하면 그렇게 잘 늘어나지 않았다. 이제 앞의 수행성능의 60% 이하로 작동한다. 그렇지만 기타 방법들 보다 메모리를 덜 사용한다. 분명히 파이썬은 훌륭하게 일을 한다. 배열을 효율적으로 저장하고 이 경우에 임시 문자열들을 쓰레기 수거한다. 20,000 회의 테스트에서 방법 4의 수행성능이 유치하게 추가하는 방법보다 20배 이상 더 좋다. 500,000 회의 테스트에서도 아주 성능이 좋다. 흥미롭게도 방법 5는 장기적인 테스트에서 성능이 더 좋았다. 방법 6은 여전히 전체적으로 승자이지만, 방법 5는 이제 초당 결합 횟수가 더 많고 거의 방법 6에 필적한다. 더 길게 테스트를 하면, 방법 5가 방법 6을 앞지를 것이라고 추측할 수 있다. 프로세스 크기에서의 차이점도 주목하자. 방법 6에 대한 계산 말미에서 인터프리터는 22,844kB의 메모리를 사용하고, 계산중인 문자열에 비해 크기가 8배이다. 반면에, 방법 3과 방법 5는 그 보다 절반 보다 적게 사용한다. 결론실제 프로그래밍이라면 나는 방법 6을 사용하겠다. 빠르고 이해하기도 쉽기 때문이다. 그렇지만 추가할 각 값들을 돌려주는 표현식을 작성할 수 있어야 한다. 어떤 경우는 그것이 편리하지 않은 경우가 있다 - 예를 들어 여러 다른 조각 코드가 출력을 만들어 낼 경우에 말이다. 그런 경우라면 방법 4와 방법 5 중에 고르면 된다. 방법 4는 유연성에서 탁월하다. 모든 조각썰기 연산자를 문자열 리스트에 사용하여 삽입과 삭제 그리고 변경할 수 있다. 추가하는데 수행성능은 아주 좋은 편이다. 방법 5는 효율성에서 뛰어나다. 리스트 방법(4 & 6)보다 메모리를 덜 사용하고 아주 많은 연산에는 리스트 통합보다도 더 빠르다 (대략 700,000번 이상). 수 없이 문자열을 추가할 거라면 cStringIO이 취할 방법이다. 측정 테크닉각 방법을 실행하는데 걸린 시간을 측정하는 것은 상대적으로 어렵지 않았다. 파이썬 라이브러리의 타이밍 모듈을 사용하여 경과 시간을 측정하였다. 머신에서 실행중인 다른 프로세스와 대조하여 파이썬 프로세스가 사용한 CPU 시간은 측정하지 않았다. 그러나 머신은 그 시간에 여유가 있었고 그래서 별 차이가 없을 것이라고 생각한다.
사용된 메모리의 측정은 약간 힘들었다. 파이썬은 현재 할당된 객체의 크기를 관제하는 방법을 제공하지 않는다. 그래서 나는 유닉스의 'ps' 명령어를 사용하여 할당된 메모리 크기를 관제하기로 걸정하였다. 프로세스 크기는 실행중에 달라지기 때문에 최대 할당 메모리를 측정하였다. 그렇게 하기 위하여 계산이 끝나는 때에 맞추어 'ps' 프로세스를 실행하였다. 내가 사용한 코드는 여기에 있다. from cStringIO import StringIO xrange vs. rangexrange 대신에 range를 사용하여 숫자 리스트를 미리 계산해 보려고 해 보았다. 약간 놀랍게도 range는 어느 경우에나 약간 더 빠른 정도였다. 그 차이는 가장 빠른 메쏘드에서 대략 1%였다. 이것이 일반적으로 xrange 대신에 range를 사용할 만한 정당한 이유라고는 생각하지 않는다. range가 더 많은 메모리를 요구하고, xrange를 순회해서 1%가 더 시간이 든다해도 문제가 될 가능성이 더 높기 때문이다. 아민 리고(Armin Rigo)는 최근 xrange가 별도의 언어 구성물로서 제거가 가능하다고 주장하였다. 파이썬이 적절한 정황에 따라 지원 저장소(반복자나 리스트)를 사용하는 객체를 돌려줄 정도로 충분히 똑똑하다면 말이다. 나는 이 주장이 언어 디자인의 관점에서 매력적이라고 느낀다. 물론 나는 그런 최적화를 구현하는게 얼마나 힘든지 알지 못한다. 앞으로 할 일이와 같은 일들에 관하여 다른 프로그래밍 언어와 비교하는게 좋다. 확실하게 말하면 perl, php, Java 그리고 C 가 좋겠다. 또 문자열 크기를 늘려가며 일련의 테스트를 실행하고 그런 결과들을 그래프로 나타내는 것도 재미있을 것이다. Revisions
|
