为什么Python字典更新如此缓慢？

Question

我有一个Python程序，它从文件中读取行并将它们放入字典中。简单来说，它看起来像这样：

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'])

它只用了几秒钟就完成了。

我认为它的+=使程序变慢了，但实际上并不是这样。请看以下测试结果。

我知道我们可以使用列表的append和join来提高连接字符串的性能。但我从未想过在添加和赋值与append和join之间存在如此大的性能差距。

所以我决定做一些更多的测试，最终发现是字典更新操作使程序变得异常缓慢。以下是脚本：

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中期，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所说，这似乎只是一个优化问题。

- WKPlus

---

你应该先创建一个拼接的字符串，然后将其赋值给字典，而不是在字典上使用 += 操作符来拼接字符串。 - Alex Fung

最好使用timeit模块进行此类基准测试。 - bruno desthuilliers

这与 update 无关，而是可能涉及某种优化，如果只有一个对给定字符串的引用。将第三个循环更改为 x = buf3.pop('1'); x+ = WORD; buf3['1'] = x，结果几乎没有什么区别：0.00136399269104 0.00481796264648 0.00717210769653 0.00203800201416。 - niemmi

不仅仅是字典。使用列表buf5 = ['']和buf5 [0] + = WORD，您会得到类似的缓慢响应。更新是缓慢的。 - muru

@muru 是的，juanpa.arrivillaga的评论可能是正确的，这是一个优化问题，你的测试证明了这一点。 - WKPlus

@niemmi 深入挖掘源代码发现这是CPython在内部进行的优化：https://hg.python.org/cpython/file/2.7/Objects/unicodeobject.c#l443 - Ashwini Chaudhary

Answer 1

+=在构建大型字符串时表现非常糟糕，但在CPython的某些情况下可能是高效的。^如下所述

要确保更快的字符串连接，请使用str.join()。

---

来自Python性能技巧下的字符串拼接部分：

避免这种情况：

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

使用s = "".join(list)代替。前者在构建大字符串时是一个非常常见且灾难性的错误。

---

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

来自Note 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 in comments在评论中正确猜测）。

- Ashwini Chaudhary

---

我认为不是这样，根据我的测试， s3-s2 很小，而 s4-3 更大。 - WKPlus

@WKPlus 所以，最近版本的CPython（我记不清具体是哪个版本，应该是大于2.6）对字符串的+=赋值进行了优化，否则它将是一个二次时间操作。在s2中，我认为解释器能够进行优化，但在s3中却不能，可能是因为你将字符串作为字典值访问。 - juanpa.arrivillaga

我非常希望看到一个分析解释器代码并证明在一种情况下前提条件（引用计数等）得到满足，在第二种情况下则没有的答案。结果观察到的行为是优化或未优化的字符串连接。 - Łukasz Rogalski

@juanpa.arrivillaga 我又做了一个测试，添加了一个无关紧要的临时字符串引用，发现它会减慢程序速度。 - WKPlus

@ŁukaszRogalski 用 dis 来查看也许会更有启发性。 - juanpa.arrivillaga