python - Python字符串添加优化失败案例

Question

问题

为什么，在 CPython 中，

def add_string(n):
    s = ''
    for _ in range(n):
        s += ' '

需要线性时间，但是

def add_string_in_list(n):
    l = ['']
    for _ in range(n):
        l[0] += ' '

需要二次时间吗？

---

证明:

Timer(partial(add_string, 1000000)).timeit(1)
#>>> 0.1848409200028982
Timer(partial(add_string, 10000000)).timeit(1)
#>>> 1.1123797750042286

Timer(partial(add_string_in_list, 10000)).timeit(1)
#>>> 0.0033865350123960525
Timer(partial(add_string_in_list, 100000)).timeit(1)
#>>> 0.25131178900483064

---

我所知道的

当要添加的字符串的引用计数为 1 时，CPython 对字符串添加进行了优化。

这是因为 Python 中的字符串是不可变的，因此通常无法编辑它们。如果对一个字符串存在多个引用并且它发生了变化，两个 引用都会看到更改后的字符串。这显然是不希望的，因此多个引用不会发生突变。

但是，如果只有一个对字符串的引用，则改变该值只会更改该引用的字符串，而该引用希望它被更改。您可以这样测试这是否是一个可能的原因:

from timeit import Timer
from functools import partial

def add_string_two_references(n):
    s = ''
    for _ in range(n):
        s2 = s
        s += ' '

Timer(partial(add_string_two_references, 20000)).timeit(1)
#>>> 0.032532954995986074
Timer(partial(add_string_two_references, 200000)).timeit(1)
#>>> 1.0898985149979126

我不确定为什么这个因子只有 30 倍，而不是预期的 100 倍，但我相信这是开销。

---

我不知道的事

那么为什么列表版本会创建两个引用呢？这甚至是阻止优化的原因吗？

您可以检查它是否没有以任何不同方式对待普通对象:

class Counter:
    def __iadd__(self, other):
        print(sys.getrefcount(self))

s = Counter()
s += None
#>>> 6

class Counter:
    def __iadd__(self, other):
        print(sys.getrefcount(self))

l = [Counter()]
l[0] += None
#>>> 6

Answer 1

在基于列表的方法中，从列表的索引 0 开始的字符串在被放回索引 0 的列表之前被获取和修改。
对于这短暂的时刻，解释器在列表中仍然有旧版本的字符串，无法执行就地修改。
如果你看一下Python's source然后您会看到不支持就地修改列表的元素。因此对象(在本例中为字符串)必须从列表中检索、修改然后放回。
换句话说 list类型与 str 完全无关类型支持 +=运营商。

并考虑以下代码:

l = ['abc', 'def']
def nasty():
    global l
    l[0] = 'ghi'
    l[1] = 'jkl'
    return 'mno'
l[0] += nasty()

l 的值是['abcmno', 'jkl']这证明'abc'从列表中取出，然后 nasty()执行修改列表的内容，字符串 'abc'和 'mno'连接起来，结果分配给 l[0] .如果nasty()在访问 l[0] 之前被评估就地修改它，那么结果将是 'ghimno' .