为什么可变字符串比不可变字符串慢？

Question

为什么可变字符串比不可变字符串慢？

编辑：

>>> import UserString
... def test():
...     s = UserString.MutableString('Python')
...     for i in range(3):
...         s[0] = 'a'
... 
... if __name__=='__main__':
...     from timeit import Timer
...     t = Timer("test()", "from __main__ import test")
...     print t.timeit()
13.5236170292



>>> import UserString
... def test():
...     s = UserString.MutableString('Python')
...     s = 'abcd'
...     for i in range(3):
...         s = 'a' + s[1:]
... 
... if __name__=='__main__':
...     from timeit import Timer
...     t = Timer("test()", "from __main__ import test")
...     print t.timeit()
6.24725079536


>>> import UserString
... def test():
...     s = UserString.MutableString('Python')
...     for i in range(3):
...         s = 'a' + s[1:]
... 
... if __name__=='__main__':
...     from timeit import Timer
...     t = Timer("test()", "from __main__ import test")
...     print t.timeit()
38.6385951042

我认为第二个测试中为什么要使用 s = UserString.MutableString('Python') 是显而易见的。

- user422100

---

我不确定它们是否更慢，这取决于你希望用它们做什么。你有特定的使用情境吗？ - Jeremy Friesner

它们本身并不如此。你需要提出一个更加具体的问题。(一般而言，可变字符串在潜在上可能更快，因为你可以进行原地修改而无需复制，但这取决于你正在做什么。很难编造出不可变字符串固有的性能优势。) - Glenn Maynard

“为什么它们运行得更慢？” -> “它们并没有” -> “证明一下”。从这里看来，mais1voto最好解释一下为什么他/她认为它们比较慢。 - RHSeeger

问题更好了，至少我个人认为，因为您的示例显示出您如何看待可变字符串比较慢。顺便说一下，虽然我没有对问题进行投票，但没有解释地投反对票是没有违规的...包括一个解释被认为是一种良好的形式，但这并不是强制性的。 - RHSeeger

我很好奇你想如何找出谁给你点了踩并“举报他们”。 - Tim Pietzcker

Answer 1

在一种假想的语言中，该语言提供可变和不可变两种等效的字符串类型（我无法立即想出一个例子 - 例如，Python和Java仅具有不可变字符串，并通过突变方式间接地使其可变，这样当然会增加间接性并稍微减慢速度;-)。在这种语言中，不存在性能差异的真正原因 - 例如，在C++中，交替使用 std::string 或 const std::string 应该不会造成任何性能差异（尽管编译器可能通过依赖不可变性来更好地优化使用后者的代码，但我不知道任何实际执行此类理论可能优化的编译器）;-)。

在Java和Python中，具有不可变字符串可以且确实允许非常大的优化。例如，如果字符串被散列，则可以缓存哈希值，并且永远不必重新计算哈希值（因为字符串不能更改）-这在Python中特别重要，因为它如此慷慨地使用散列字符串（用于查找集合和字典），甚至“在幕后”也是如此。不需要制作新副本“以防万一”先前的副本已更改-每当需要该字符串时，系统总是可以分配对单个副本的引用。 Python还广泛使用某些字符串的“国际化”，从而可以在常数时间内进行比较和许多类似快速操作-将其视为一种更先进的方式，确保利用字符串的不可变性来缓存执行常常在其上执行的操作的更多结果。

当然，并不是所有编译器都会利用所有可能的优化。例如，当请求一个字符串的切片时，实际上没有必要创建一个新对象并复制数据 - 新切片可能只是引用旧切片的偏移量（和独立存储的长度），对于从中获取许多切片的大字符串来说，这可能是一种巨大的优化。Python并不这样做，因为除非特别注意内存管理，否则这很容易导致“大”的字符串在实际只需要一个小切片时全部保存在内存中 - 但这是另一种实现肯定会选择执行的权衡（要求处理额外的内存管理负担，确保更复杂、更难调试的编译器和运行时代码）。

这里我只是浅尝辄止 - 如果可互换的字符串类型可以同时存在于可变和不可变版本中（我怀疑这就是为什么C++编译器实际上不会费心进行这样的优化，尽管通常非常注重性能）。但通过仅提供不可变字符串作为基本数据类型（因此在真正需要可变字符串时隐含地接受了一些缺点;），像Java和Python这样的语言显然可以获得各种各样的优势 - 其中性能问题只是其中的一组（例如，Python选择允许仅不可变原始类型是可哈希的，不是基于性能的设计决策 - 这更多地涉及到集合和字典行为的清晰性和可预测性！-）。

- Alex Martelli

Answer 2

使用不可变字符串，Python 可以将其内部存储为地址。这意味着，要比较两个字符串，只需比较它们在内存中的地址（除非其中一个未被存储）。同时，请注意，并非所有字符串都可以被存储。我曾经看到过一些无法被存储的构造字符串。

对于可变字符串，字符串比较需要逐个字符进行比较，还需要在不同位置存储相同的字符串（malloc 不是免费的）或添加逻辑来跟踪每个字符串被引用的次数，如果有多个引用者，则需要每次变异都进行复制。

Python 似乎针对字符串比较进行了优化。这是有道理的，因为在大多数情况下，甚至字符串操作也涉及字符串比较，因此对于大多数用例，这是最低公共分母。

另一个不可变字符串的优点是使其成为可哈希的，这是将其用作字典键的要求。想象一下，如果字符串是可变的：

s = 'a'
d = {s : 1}
s = s + 'b'
d[s] = ?

我想Python可以跟踪哪些字典具有哪些字符串作为键，并在字符串被修改时更新它们所有的哈希表，但这只会增加字典插入的负担。不太准确地说，在Python中做任何事情都需要进行字典插入/查找，所以这将是非常糟糕的。它还会增加字符串操作的负担。

- aaronasterling

Answer 3

我不知道它们是否真的慢很多，但它们很多时候使得关于编程的思考更容易，因为对象/字符串的状态不能改变。对于我来说，这是不可变性最重要的属性。

此外，你可能会认为不可变字符串更快，因为它们具有较少的状态（可以改变），这可能意味着更低的内存消耗和CPU周期。

我在谷歌搜索时还发现了这篇有趣的文章，我想引用一下：

“知道一个字符串是不可变的，使得在构建时容易布局-固定和不变的存储需求。”

- Alfred

Answer 4

对于你的问题，显而易见的答案是普通字符串是用C实现的，而MutableString是用Python实现的。

每个可变字符串上的操作都需要经过一个或多个Python函数调用的开销，而且实现本质上是围绕一个不可变字符串的包装器 - 当你修改字符串时，它会创建一个新的不可变字符串并丢弃旧的字符串。你可以在Python lib目录下的UserString.py文件中阅读源代码。

引用Python文档的话：

注意：

此模块中的UserString类仅供向后兼容使用。如果您编写的代码不需要与早于Python 2.2的版本一起工作，请考虑直接从内置的str类型进行子类化，而不是使用UserString（没有内置等效于MutableString）。

此模块定义了一个类，它作为字符串对象的包装器。它是您自己的类似字符串的类的有用基类，可以从中继承并覆盖现有方法或添加新方法。通过这种方式，可以向字符串添加新的行为。

应该注意，与真实字符串或Unicode对象相比，这些类非常低效；特别是对于MutableString。

- Dave Kirby