Python中字符串的时间复杂性

Question

这可能是以前问过的。然而，我无法通过搜索找到答案，因为我可能只是在搜索错误的东西

我有两个相似的函数，只有一个小的不同。从两者的计时来看，一个要比另一个快得多

下面的函数获取一个单词列表，并连接每个单词。你会注意到有一行temp = concat不需要在那里

def concat_with_add(word_list):
    concat = ''
    for word in word_list:
        concat += word
        temp = concat
    return concat

此函数与上面的相同，只有temp = concat未被删除。此功能的速度要快得多

def concat_with_add(word_list):
    concat = ''
    for word in word_list:
        concat += word
    return concat

我读了一篇对此的解释，但我很难理解为什么将concat变量指定给temp变量会使事情变得如此缓慢。有人能用我能理解的方式解释吗

编辑：这就是我计时的方式-

import time

start = time.time()
concat_with_add(random_strings)
end = time.time()
time_add = end - start
    
print(time_add)

词表的长度是100000

使用temp = concat所需的时间是：4.5

没有它的时间是：.02

Answer 1

从语义上讲，行concat += word创建了一个包含concat和word连接的新字符串，然后重新分配concat以引用该新字符串。这将使循环的运行时间是二次的，因为创建这个新字符串在concat和word长度上都是线性的

但是，在实际实现中，CPython对此进行了优化，以改变concat的内容，而不是创建一个新字符串当且仅当concat是该字符串的唯一引用时。将字符串追加到适当位置所需的时间在word（摊销）长度上仅为线性。这会使循环的运行时线性化。但是，正如我所说，只有当concat是字符串的唯一引用时，才能应用这种优化（否则其他变量的值也会改变，这会破坏语义）。因此，使用temp = concat对字符串引入另一个引用会阻止优化