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字符串连接速度

回答

相关问题