python - 元组比列表快是因为它们是可散列的吗？

不，可哈希与更快无关。

为了从可散列的集合中访问元素，它需要恒定的时间。

你让事情倒退了。在使用哈希表（如 a ）的集合中查找可哈希元素的时间set是恒定的。但这是关于元素是可散列的，而不是集合，它是关于使用散列表而不是数组的集合，它是关于按值而不是按索引查找它们。

通过索引查找数组中的值（无论该值或数组是否可散列）需要恒定的时间。按值搜索数组需要线性时间。（除非，例如，它已排序并且您通过二等分进行搜索。）

你的老师只说对了一部分——但他们可能一直在简化事情以避免陷入血淋淋的细节。

对于某些操作，元组比列表快的原因有三个。

但值得注意的是，这些差异通常很小，而且通常难以预测。¹几乎总是，你只想使用更有意义的那个，如果你偶尔发现一个瓶颈，几个 % 会有所作为，把它拿出来看看timeit两个版本。

首先，有一些操作针对这两种类型进行了不同的优化。当然，对于不同的实现，甚至同一实现的不同版本，这都是不同的，但有一些来自 CPython 3.7 的示例：

在对元组列表进行排序时，有一个特殊unsafe_tuple_compare的不适用于列表。
==当比较or的两个列表时!=，有一个特殊的is测试来缩短比较，这有时会加快速度，但会减慢速度。对一大堆代码进行基准测试表明，这对于列表是值得的，但对于元组则不然。

对于这些选择，可变性通常不会考虑在内；它更多的是关于通常如何使用这两种类型（列表通常是同质类型但任意长度，而元组通常是异质类型和一致长度）。然而，它并不是完全不相关的——例如，一个列表可以包含它自己（因为它们是可变的）而一个元组不能（因为它们不是）阻止了至少一个小的优化被应用于列表。²

其次，同一个编译单元中的两个相等的元组常量可以合并为同一个值。至少 CPython 和 PyPy 通常会这样做。这可以加快某些事情的速度（如果没有别的，当要缓存的数据较少时，您可以获得更好的缓存局部性，但有时这意味着更大的节省，例如能够使用is测试）。

而这个是关于可变性的：编译器只有在知道它们是不可变的时才允许合并相等的值。

第三，相同大小的列表更大。分配更多内存、使用更多缓存行等会稍微减慢速度。

这也是关于可变性的。列表最终必须有增长空间；否则，调用appendN 次需要N**2时间。但是元组不必append。

_{1.在某些类型的问题中，有一些案例经常出现，以至于一些一直在处理这些问题的人学习并记住了它们。有时，您会在 Stack Overflow 上看到一个优化问题的答案，有人插话说：“使用元组而不是列表，这可能会快 3% 左右”，而且他们通常是对的。}

_{2. 另外，我可以想象一种情况，像 PyPy 中的 JIT 编译器可以使用元组更好地加快速度。如果您使用相同的值连续运行相同的代码一百万次，您将获得相同答案的一百万份副本 - 除非值更改。如果该值是两个对象的元组，PyPy 可以添加警卫以查看其中任何一个对象是否发生变化，否则只需重用最后一个值。如果它是一个包含两个对象的列表，PyPy 将不得不为这两个对象和列表添加保护，这会增加 50% 的检查。这是否真的发生，我不知道；每次我试图追溯 PyPy 优化的工作原理并从那里进行概括时，我都证明是错误的，我最终得出的结论是 Armin Rigo 是一个向导。}

python - 元组比列表快是因为它们是可散列的吗？

问题描述

解决方案

推荐阅读