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

Question

我一直找不到这个信息的来源，除了自己去查看Python的源代码，想弄清楚这些对象是怎么工作的。有没有人知道我可以在哪里在线找到这些信息？

Answer 1

如果你问的问题是我想的那样，你可以在这里找到相关内容……从第476页开始。

这本书主要讲的是Python的优化技巧；里面大部分是关于时间效率的“大O”表示法，而不是太多关于内存的内容。

Answer 2

Raymond D. Hettinger 做了一个很棒的演讲，内容是关于 Python 内置的集合，叫做《核心 Python 容器 - 内部原理》。我看到的版本主要讲了 set 和 dict，不过 list 也有提到。

在 一个博客 上，还有一些 EuroPython 会议相关幻灯片的照片。

以下是我对 list 的笔记总结：

• 它把项目存储为指针的数组。通过下标访问的时间是 O(1)，也就是很快。添加新元素的时间平均也是 O(1)，但插入元素的时间是 O(n)，也就是比较慢。
• 在扩展时，它会通过过度分配来避免使用 memcpy。很多小列表会浪费很多空间，但大列表的空间浪费不会超过大约 12.5%。
• 有些操作会提前设置大小。比如 range(n)、map()、list()、[None] * n 和切片操作。
• 在缩小列表时，只有当空间浪费达到 50% 时，数组才会被 realloc。而 pop 操作是很便宜的。

Answer 3

去看看这个时间复杂度的页面，里面讲了关于集合、字典、列表等等的内容，至少在时间复杂度方面是这样。