파이썬 문자열 연산에 대한 고찰

 

파이썬은 매우 편리한 언어이다. 그만큼 자칫하면 실수하기 쉬운 몇몇 기능들이 있다. 그중 하나를 소개하려고 한다.

 

파이썬에서는 문자열을 더할 수 있다. 'SSS' + 'ZZZ' = 'SSSZZZ' 이다. 이것을 O(1) 혹은 그에 준하는 연산이라 생각하면 안된다. 이것이 O(1)인지 아니라는 것을 증명하는 것은 간단하다.

만약 O(1)이라면 더하는 문자열의 길이에 상관없이 비슷한 시간이 걸릴 것이다. 예를 들어 'S'+'S' 와 'SS...S' + 'SS...S' 에 걸리는 시간이 동일하다면 O(1)일 것이다.

 

 

now = time()
word='s'
add='s'
for i in range(1000000):
    word+=add
print(time()-now)

now = time()
word='sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss'
add='sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss'
for i in range(1000000):
    word+=add
print(time()-now)

 

위 코드를 통해 비교해 본 결과 's'+'s'의 경우 0.13초, 'ss..s' + 'ss..s' 1.16초가 걸리게 된다. 길이가 M인 문자열에 길이가 N인 문자열을 붙이는데 걸리는 시간은 O(M)+O(N)이다.

 

파이썬에서는 문자열을 곱할 수 있다. 'SS' * 3 은 'SSSSSS' 이다. 이것을 O(1)이라 착각하면 안된다. 마찬가지로 문자열 길이만큼의 시간이 걸린다.

 

now = time()
s='s'
s*=1000000
print(time()-now)

now = time()
s='sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss'
s*=1000000
print(time()-now)

 

마찬가지로 위와 같은 코드로 로컬로 실행 시간을 구해보았다. 's'*1000000의 경우 0.00027초, 'ss..s' 의 경우 0.15초나 걸렸다. 최종 문자열은 아까 더하는 방식과 같을 텐데 왜 실행 시간이 이렇게나 차이나는 이유는 더해서 구하는 방식은 word의 길이(M) + 더하는 문자열의 길이(N)을 1000000번 반복했기 때문이다. 곱한 경우 O(반복횟수*N)이기 때문이다.

 

착각하기 쉬운 연산이므로 주의하여야 한다.