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

Question

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

Answer 1

结帐 时间复杂度 py dot org wiki 上的页面。它至少涵盖了集合/字典/列表/等，至少就时间复杂度而言。

Answer 2

雷蒙德·D.海廷格确实如此 一次精彩的演讲 (幻灯片）有关称为“核心 Python 容器 - 底层”的 Python 内置集合。我看到的版本主要集中在 set 和 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 的优化技术编写的；这主要是时间效率的 Big-O 表示法，没有太多内存。