Python字符串連接速度

我正在測試不同速度連接方法的速度，通過將字符串表示從1連接到一個大數字（在我的情況下爲20000000）。這三種方法，我測試的是：Python字符串連接速度

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}

改進的方法竟然比天真的方法慢得多！

這是沒有意義的，因爲天真的方法創建新的綁定和複製以前的字符串連同串聯的字符串字符按字符ON EACH ITERATION，這種方法應該採取O（n^2），這應該是多比其他O（n）方法慢。

那麼是什麼讓改進方法如此緩慢呢？我能想到的唯一原因是append方法，但根據this article，append方法使用O（1），所以它絕對不是原因。那麼在改進的Concat（）中需要這麼久？謝謝。

來源

2014-02-05 elgoog

你應該更加小心。您正在計時「追加」，但只期望「連接」的結果。嘗試使用基本「％s％s」％（str1，str2）的函數。這在大多數情況下是最快的。 – cox

@cox，我確實需要計時「追加」，因爲這是我的連接函數所需要的，我用另一個函數編寫了另一個函數，結果表明它是四個中最慢的，比天真的方法慢得多。也許連接只有幾個字符串會更快，但不是連接大量字符串段的情況。 – elgoog

在這種情況下，「加入」可能是一種選擇。 python/C++/...字符串的優點是長度被緩存在對象屬性中。所以對於基本的操作，你可能在Python中比在C中有更好的結果。但是連接是另一個野獸。你要做的是分配/填充內存與數據類型不相關。也許一個cython函數會更快？ – cox

improvedConcat的ncalls列顯示您創建了20000004次函數調用，而其他算法只有少數幾次。函數調用在Python中並不便宜，所以儘量保持這些限制。爲了證明，我做了一個新的測試下你的模式NOP調用，只調用一個空函數的定義：

def foo(): 
    pass 

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

我得到類似的時序結果你的其他測試，這NOP（無操作）測試結果

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

所以你有4.4s的開銷製作函數調用。

來源

2014-02-05 22:29:38 velotron

我想知道如果OP使用'string + = [i]'會有什麼區別。 – 2rs2ts

@ 2rs2ts：「TypeError：無法連接'str'和'list'對象」。我嘗試了map（str，array），範圍而不是xrange，以及生成器表達式而不是列表理解的一些變體，但是並沒有改進rapidConcat。 – velotron

我把總數減少到1，'count = 1; timeit.timeit（'b = improvedConcat（）'，setup ='from__main__ import improvedConcat'，number = 1）'，結果仍然表明改進的方法更慢：'天真：3.40938568115e-05;改進：4.10079956055e-05;最快：3.09944152832e-05'。而且，由於函數調用需要一定的時間，而天真方法中的級聯只能隨着要並置的數量的增加而延長，所以如果'count'足夠大，那麼improveConcat在某些時候將優於naiveConcat。但是當我把'count'設置的更大時，改進的Concat需要更長的時間 – elgoog

Python字符串連接速度

回答

相關問題