Shell's Home

Jan 18, 2012 - 1 minute read - Comments

python的字符串相加效率

今天文章被人纠了错,就跑去人家主页上逛。结果看到有篇文章说字符串相加速度的,看看结论很奇怪。就做了一下实验。原文可以看这里。我们只讨论python部分的行为。首先是论证我观点的测试,无关部分就跳过了,大家应当可以自行补上。

def f():
    s = ''
    for i in range(3):
        s += '123'
        print id(s)
    return s

f()
f()

输出:

138190216
138276992
138276992
138190216
138276992
138276992

至少在几十的规模,这个结论还是成立的。说明对象确实被缓存了,这导致了字符串相加的多次测试中,后续次数都没有实际的执行字符串分配动作。召dis来问之。

14           0 LOAD_CONST               1 (u'')
             3 STORE_FAST               0 (s)

15           6 SETUP_LOOP              46 (to 55)
             9 LOAD_GLOBAL              0 (range)
            12 LOAD_CONST               2 (3)
            15 CALL_FUNCTION            1
            18 GET_ITER            
       >>   19 FOR_ITER                32 (to 54)
            22 STORE_FAST               1 (i)

16          25 LOAD_FAST                0 (s)
            28 LOAD_CONST               3 (u'123')
            31 INPLACE_ADD         
            32 STORE_FAST               0 (s)

17          35 LOAD_GLOBAL              1 (print)
            38 LOAD_GLOBAL              2 (id)
            41 LOAD_FAST                0 (s)
            44 CALL_FUNCTION            1
            47 CALL_FUNCTION            1
            50 POP_TOP             
            51 JUMP_ABSOLUTE           19
       >>   54 POP_BLOCK           

18     >>   55 LOAD_FAST                0 (s)
            58 RETURN_VALUE        

我们看到s是local变量,这个符合我们的预期。但是后续确实发生了add,而string的+算法,我们可以参考Objects/stringobject.c:1015这里,string_concat函数的内容。这里没有加速过程,即使有,也只有发生在len(a) == 0 or len(b) == 0的情况下。对于123的求和无法说明原因。

这里我只能做一个假定,我们发现的id相等,其实可能是由于内存重分配的结果。一个对象被回收后,是存放在对象池中的,再分配的时候,可能按照规则被重新分配。当然这只能是一个推测,实际证明必须在python源码中修改并且重编译,我就不找这个麻烦了。

另一个问题,实验的时候,只是把固定字符串更换为随机字符串而已,长度也没有发生变化。预期的结果应当是+=的速度变慢,结果+=速度不变。问题是join的速度加快算是怎么回事?关于join,我们可以参考Objects/stringobject.c:1574,这里说明了join的工作流程,也没有任何加速!

唯一的解释,就是append的工作速度慢到超乎正常人类的想像,实验证明了这点。

def g():
    a = []
    for i in range(1000):
        a.append('1234567890')
        # s = ''.join(a)
print Timer('g()', 'from __main__ import g').timeit(10000)

结果是0.91,append动作比join慢10倍。

Tags: program python

计算机自动化的方向 龙年新年

comments powered by Disqus