python 中获取子字符串是 O(n) 操作吗？

Question

在 C++ 中，如果我要从字符串中删除第一个字符，它将类似于：

string s = "myreallylongstring";
s = s.substr(1);

这将是 O(1)。[如果我错了请纠正我]

然而，在 Python 的“不可变字符串”世界中，这段代码的运行时间复杂度是 O(n) 吗？

s = "myreallylongstring"
s = s[1:]

如果我使用字符列表会更快吗？

Answer 1

在一般情况下，对 Python 中的任何内置类型（除了memoryview）进行切片O(n)（主要例外是不可变实例的完整切片，它通常返回原始实例而不复制它，因为不需要它）。

A listof 个字符没有帮助；list从a的开头删除一个字符O(n)（它必须将其上方的所有内容复制到一个槽中）。Acollections.deque可以想象地改进 big-O（它们可以O(1)从任一端弹出），但它也会比字符串消耗更多的内存和更多的碎片内存。

对于除最大字符串之外的所有字符串，即使存在这些O(n)低效率，您通常也可以接受，因此除非您实际分析并发现它是问题的原因，否则我会坚持使用切片并顺其自然。

也就是说，你对 C++ 的看法是错误的；s = s.substr(1)与 Python 没有什么不同s = s[1:]。它们最终都会复制整个字符串并保存第一个字符，C++ 移动分配回原始字符串，而 Python 将绑定到旧对象的原始名称替换为新对象（功能上非常相似的操作）。s.substr(1)甚至没有使用 的std::string可变性功能；s.erase(0, 1)实际上会就地擦除，改变原始字符串，但这仍然是O(n)因为所有其他字符都必须复制到先前被删除的字符占用的空间中（据std::string我所知，没有实现允许存储从字符串开头的偏移量以查找实际数据，指向数据的指针始终指向第一个分配的字节）。