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

Question

在 C++ 中，如果我要从字符串中删除第一个字符，它看起来像：

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

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

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

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

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

标签： pythonc++time-complexity

Answer 1

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

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

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

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