在许多语言中，散列映射/关联数组有许多不同的实现，每一种都适用于不同的任务。据我所知，在 Python 中只有 dict。
所以我想我想知道的是，是否有任何应用程序对自定义数据结构有意义？还是它总是比使用 Python 的内置数据结构之一慢？
问问题
672 次
1 回答
1
这可能应该在评论中，但太长了......
Python 字典被实现为hash table。哈希表很适合平均检索项目（ O(1) ）。如果它们总体上很好，那么当有很多碰撞时它们的性能就会下降。冲突是指计算的两个不同键的哈希值相同。所以在最坏的情况下，如果所有的键都具有相同的散列，它们的搜索操作的复杂性是 O(n) - 这相当于线性搜索。
但是关联数组可以通过使用其他几种数据结构来实现。值得注意的是二叉搜索树（不是那么好：平均为 O(log n)，最差为 O(n)）或B-tree（更好：平均为 O(log n) ，最差为 O(log n)）。AFAIK 标准 Python 库不提供任何这些。通过谷歌搜索，它似乎有各种实现。
这导致了您问题的核心：“是否有任何应用程序对自定义数据结构有意义？或者它是否总是比使用 Python 的内置数据结构之一慢？”。就我自己而言，我认为任何这些数据结构的任何纯 Python 实现都可能慢慢地成为原生 Python 字典。如果您有非常特殊的需求，您可以考虑在 C 级别实施这些需求。但如果你有这样的限制，也许 Python 一开始并不是最好的选择。
于 2013-06-19T20:31:18.397 回答