python - 这两个Python代码的时间复杂度差异是多少？

Question

我想在 python 中进行字符串赋值。然而，在Python中，'str'对象不支持项目分配。如果我想做这个作业，s[head] = s[tail]，我会想到两个想法:
1.
s[:head]+s[tail]+s[(head+1):tail]+s[head]+s[(tail+1):]
2.

temp = list(s)
temp[head] = temp[tail]
s = ''.join(temp)

我的问题是这两者之间的时间复杂度是多少？当我尝试一些大型示例时，我发现第二个解决方案比第一个解决方案更快，但我不知道为什么。谁能帮我解释一下吗？

Answer 1

当您使用 + 连接 2 个字符串时，必须分配一个新的字符串对象，并且必须将 2 个源字符串复制到其中。

因此，在第一个选项中，您将通过切片创建 5 个新字符串，然后在串联操作期间再创建 4 个字符串。总共有 9 次字符串分配和复制操作，然后需要取消分配 8 个中间字符串。

在第二个选项中，您可以从字符串创建列表，修改列表项之一，然后加入结果列表。 str.join 方法比一对一串联更高效，因为它分两个阶段进行。在第一阶段，它扫描列表中的字符串以确定目标字符串所需的总长度，分配该字符串，然后在第二阶段，它再次扫描列表以复制字符串数据。 (FWIW，这使得将列表理解传递给 .join 比传递等效的生成器表达式更有效，因为 .join 必须按顺序将 gen exp 运行到列表中执行 2 次扫描)。

自 Python 2.5 (IIRC) 以来，字符串连接已得到优化，以提高 a = a + b 和 a = b + a 连接的速度，但优化并不多对于更一般的情况可以这样做，即使是我刚才提到的简单情况，当字符串长度大于 1000 左右时，它也比使用 .join 慢得多。

但是，这些操作的确切速度取决于您使用的 Python 版本。当然，为了公平地比较 + 与 .join，我们需要对它们执行相同操作进行计时，而您的算法不会这样做。

正如 Stefan 在评论中指出的那样，对于您的算法 .join 实际上可能会更慢，即使对于大字符串也是如此。底线是:编码时要注意一般的 Python 习惯用法，但一般规则不能代替测量。因此，请对在软件+硬件上运行的典型数据上运行的实际代码进行速度测试。如果可行，请使用最新版本的 Python。 (OTOH，某些字符串操作在 Python 2 上实际上可以更快，因为它们是使用 ASCII/Latin1 字节字符串而不是完整的 Unicode 字符串完成的)。