为什么python dict更新疯狂？

Question

我有一个python程序,它从文件中读取行并将它们放入dict中,简单来说,它看起来像:

data = {'file_name':''}
with open('file_name') as in_fd:
    for line in in_fd:
        data['file_name'] += line

我发现它需要几个小时才能完成.

然后,我对程序做了一些改动:

data = {'file_name':[]}
with open('file_name') as in_fd:
    for line in in_fd:
        data['file_name'].append(line)
    data['file_name'] = ''.join(data['file_name'])

它在几秒钟内完成.

我认为这+=会使程序变慢,但似乎没有.请查看以下测试的结果.

我知道我们可以使用list append和join来提高concat字符串的性能.但我从未想过追加和加入以及添加和分配之间存在这样的性能差距.

所以我决定做更多的测试,最后发现它是dict更新操作使程序疯狂地慢.这是一个脚本:

import time
LOOPS = 10000
WORD = 'ABC'*100

s1=time.time()
buf1 = []
for i in xrange(LOOPS):
    buf1.append(WORD)
ss = ''.join(buf1)

s2=time.time()
buf2 = ''
for i in xrange(LOOPS):
    buf2 += WORD

s3=time.time()
buf3 = {'1':''}
for i in xrange(LOOPS):
    buf3['1'] += WORD

s4=time.time()
buf4 = {'1':[]}
for i in xrange(LOOPS):
    buf4['1'].append(WORD)
buf4['1'] = ''.join(buf4['1'])

s5=time.time()
print s2-s1, s3-s2, s4-s3, s5-s4

在我的笔记本电脑(mac pro 2013 mid,OS X 10.9.5,cpython 2.7.10)中,它的输出是:

0.00299620628357 0.00415587425232 3.49465799332 0.00231599807739

受到juanpa.arrivillaga评论的启发,我对第二个循环做了一些改动:

trivial_reference = []
buf2 = ''
for i in xrange(LOOPS):
    buf2 += WORD
    trivial_reference.append(buf2)  # add a trivial reference to avoid optimization

更改后,现在第二个循环需要19秒才能完成.所以它似乎只是一个优化问题,正如juanpa.arrivillaga所说.

Answer 1

+=在构建大型字符串时执行非常糟糕,但在CPython中可以在单例中高效.^{如以下所说的}

对于肯定拍摄更快的字符串连接使用str.join().

从Python Performance Tips下的String Concatenation部分:

避免这个:

s = ""
for substring in list:
    s += substring

请s = "".join(list)改用.在构建大型字符串时,前者是一个非常常见和灾难性的错误.

为什么s += x比s['1'] += x或更快s[0] += x？

从注6:

CPython的实现细节:如果s和t都是字符串,一些Python实现如CPython的通常可以执行就地优化形式的分配s = s + t或s += t.如果适用,此优化使得二次运行时间的可能性大大降低.此优化依赖于版本和实现.对于性能敏感的代码,最好使用str.join()确保版本和实现之间一致的线性级联性能的 方法.

在CPython的情况下的优化是,如果字符串只有一个引用,那么我们可以就地调整它.

/*请注意,我们不必为非共享Unicode对象修改*unicode,因为我们可以就地修改它们.*/

现在后两者不是简单的就地添加.事实上,这些根本不是就地添加.

s[0] += x

相当于:

temp = s[0]  # Extra reference. `S[0]` and `temp` both point to same string now.
temp += x
s[0] = temp

例:

>>> lst = [1, 2, 3]
>>> def func():
...     lst[0] = 90
...     return 100
...
>>> lst[0] += func()
>>> print lst
[101, 2, 3]  # Not [190, 2, 3]

但一般来说,从不使用s += x串联字符串,总是使用str.join字符串集合.

计时

LOOPS = 1000
WORD = 'ABC'*100


def list_append():
    buf1 = [WORD for _ in xrange(LOOPS)]
    return ''.join(buf1)


def str_concat():
    buf2 = ''
    for i in xrange(LOOPS):
        buf2 += WORD


def dict_val_concat():
    buf3 = {'1': ''}
    for i in xrange(LOOPS):
        buf3['1'] += WORD
    return buf3['1']


def list_val_concat():
    buf4 = ['']
    for i in xrange(LOOPS):
        buf4[0] += WORD
    return buf4[0]


def val_pop_concat():
    buf5 = ['']
    for i in xrange(LOOPS):
        val = buf5.pop()
        val += WORD
        buf5.append(val)
    return buf5[0]


def val_assign_concat():
    buf6 = ['']
    for i in xrange(LOOPS):
        val = buf6[0]
        val += WORD
        buf6[0] = val
    return buf6[0]


>>> %timeit list_append()
1000 loops, best of 3: 1.31 ms per loop
>>> %timeit str_concat()
100 loops, best of 3: 3.09 ms per loop
>>> %run so.py
>>> %timeit list_append()
10000 loops, best of 3: 71.2 us per loop
>>> %timeit str_concat()
1000 loops, best of 3: 276 us per loop
>>> %timeit dict_val_concat()
100 loops, best of 3: 9.66 ms per loop
>>> %timeit list_val_concat()
100 loops, best of 3: 9.64 ms per loop
>>> %timeit val_pop_concat()
1000 loops, best of 3: 556 us per loop
>>> %timeit val_assign_concat()
100 loops, best of 3: 9.31 ms per loop

val_pop_concat在这里很快,因为通过使用pop()我们正在从列表中删除引用到该字符串,现在CPython可以就地调整它(在评论中由@niemmi正确猜测).