使用 python 字符串时的时间复杂度[重复]

Question

我正在分析不同方法的字符串连接的复杂性以及我注意到的内容。

%%time
sent = ""
word = "hello "
num = 100000
for _ in range(num):
    sent += word

这个方法需要20ms

%%time
sent_1 = "".join([word] * num)

第二种方法需要 4 毫秒并且

%%time
sent_2 = ""
for _ in range(num//5):
    sent_2 = sent_2 + word + word + word + word + word

第三种方法需要 208 毫秒

sent==sent_1==sent_2

给我 True

有人可以解释为什么我得到这样的结果

Answer 1

sent2 + word + word + word + word + word

创建多个临时

str

对象，大致相当于

t1 = sent2 + word
t2 = t1 + word
t3 = t2 + word
t4 = t3 + word
sent_2= t4 + word

创建所有这些对象（并将一个临时值的不断增长的值复制到另一个）导致二次运行时间。

另一方面，

''.join([word] * num)

将所有字符串一次连接到一个列表中，因此它可以分配 one 结果字符串并在线性时间内将子字符串复制到位。

第一个例子，

for _ in range(num):
    sent += word

应该等同于重复连接。但是，CPython 特别优化了这一点，它认识到在计算

sent

时没有人可以访问

sent + word

的值，因此它“作弊”并就地更新

sent

，没有分配新的字符串分配回

sent

。这意味着您仍然有一个线性时间操作，如

''.join

，但由于在 Python 中而不是在解释器的 C 级别迭代字符串而产生额外的开销。