python - 在哪里可以找到 Python 中内置序列类型的时间和空间复杂度

Question

我一直无法找到这些信息的来源，没有自己查看 Python 源代码以确定对象是如何工作的。有谁知道我在哪里可以在网上找到这个？

Answer 1

查看 py dot org wiki 上的TimeComplexity页面。至少就时间复杂度而言，它涵盖了 set/dicts/lists/etc。

Answer 2

Raymond D. Hettinger 就Python 的内置集合（称为“Core Python Containers - Under the Hood”）进行了精彩的演讲（幻灯片）。我看到的版本主要集中在setand dict，但list也被覆盖了。

博客中还有一些来自 EuroPython 的相关幻灯片的照片。

以下是我的笔记摘要list：

• 将项目存储为指针数组。下标花费 O(1) 时间。追加成本摊销 O(1) 时间。插入花费 O(n) 时间。
• 试图memcpy通过过度分配来避免增长。许多小列表会浪费大量空间，但大列表永远不会浪费超过 12.5% 的过度分配。
• 一些操作预先调整大小。给出的示例是range(n)、map()、list()、[None] * n和切片。
• 缩小时，数组realloc仅在浪费 50% 的空间时才被编辑。pop很便宜。

Answer 3

如果你问我认为你在问什么，你可以在这里找到它们……第 476 页及以后。

它是围绕 Python 的优化技术编写的；它主要是时间效率的大 O 符号，没有太多内存。