파이썬 문자열 연결 속도

Question

문자열 표현을 1에서 많은 수 (내 경우 20000000)로 연결하여 다른 속도 연결 방법의 속도를 테스트하고 있습니다. 결과 아무튼 나는 순진보다 빠를하는 개선 된 방법을 볼 것으로 예상하고

import cProfile 

count = 20000000 

def profileWrapper(f): 
    def wrapper(*args, **argv): 
     pr = cProfile.Profile() 
     pr.enable() 
     string = f(*args, **argv) 
     pr.create_stats() 
     pr.print_stats() 
     return string 
    return wrapper 

@profileWrapper 
def naiveConcat(): 
    global count 
    string = '' 
    for i in xrange(count): 
     string += `i` 
    return string 

@profileWrapper 
def improvedConcat(): 
    global count 
    string = [] 
    for i in xrange(count): 
     string.append(`i`) 
    return ''.join(string) 

@profileWrapper 
def fastestConcat(): 
    global count 
    return ''.join([`i` for i in xrange(count)]) 

print 15 * "=", "naiveConcat", 15 * "=" 
naiveConcat() 
print 15 * "=", "improvedConcat", 15 * "=" 
improvedConcat() 
print 15 * "=", "fastestConcat", 15 * "=" 
fastestConcat() 

, 그것은 '가장 빠른 방법보다 훨씬 느린 안 :하지만, 내가 테스트입니다 세 가지 방법이 있습니다 다음과 같이 보입니다 :

=============== naiveConcat =============== 
     3 function calls in 3.951 seconds 

    Ordered by: standard name 

    ncalls tottime percall cumtime percall filename:lineno(function) 
     1 0.000 0.000 0.000 0.000 cProfile.py:90(create_stats) 
     1 3.951 3.951 3.951 3.951 str_concat.py:18(naiveConcat) 
     1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 


=============== improvedConcat =============== 
     20000004 function calls in 6.990 seconds 

    Ordered by: standard name 

    ncalls tottime percall cumtime percall filename:lineno(function) 
     1 0.000 0.000 0.000 0.000 cProfile.py:90(create_stats) 
     1 5.196 5.196 6.990 6.990 str_concat.py:26(improvedConcat) 
20000000 1.322 0.000 1.322 0.000 {method 'append' of 'list' objects} 
     1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 
     1 0.473 0.473 0.473 0.473 {method 'join' of 'str' objects} 


=============== fastestConcat =============== 
     4 function calls in 3.043 seconds 

    Ordered by: standard name 

    ncalls tottime percall cumtime percall filename:lineno(function) 
     1 0.000 0.000 0.000 0.000 cProfile.py:90(create_stats) 
     1 2.539 2.539 3.043 3.043 str_concat.py:34(fastestConcat) 
     1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects} 
     1 0.504 0.504 0.504 0.504 {method 'join' of 'str' objects} 

개선 된 방법은 순진한 방법보다 훨씬 느립니다.

순진한 방법이 새로운 바인딩을 생성하고 각 문자열에 연결된 문자열 문자와 함께 이전 문자열을 복사하기 때문에이 방법은 의미가 없습니다.이 방법은 O (n^2) O (n) 인 다른 방법보다 느립니다.

그래서 개선 된 방법이 너무 느립니까? 내가 생각할 수있는 유일한 이유는 append 메서드이지만, this article에 따르면 append 메서드는 O (1)을 사용하므로 명확히 이유가 아닙니다. 그럼 개선 된 콘택()에서 오래 걸리는 것은 무엇입니까? 고맙습니다.

Answer 1

개선 된Concat의 ncalls 열은 20000004 건의 함수 호출을 수행했음을 보여줍니다. 다른 알고리즘과 비교해 보면 소수에 불과합니다. 함수 호출은 파이썬에서 아주 저렴하지 않으므로 제한적으로 유지하십시오.

def foo(): 
    pass 

@profileWrapper 
def nop(): 
    for i in xrange(count): 
     foo() 
    return '' 

내가 다른 시험과 비슷한 타이밍 결과를 얻을,이 NOP (연산 없음)

에서 테스트 결과 : 나는 단지 빈 함수 정의를 호출 NOP라는 패턴, 다음과 같은 새로운 테스트를 만들어 보여주기 위해

=============== nop =============== 
20000003 function calls in 4.386 seconds 

그래서 함수 호출을하는 오버 헤드가 4.4 초 있습니다.