问题

为什么,在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)
#>>> …