我在哪里可以找到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")进行了精彩的演讲(幻灯片).我看到的版本主要集中在set和dict,但list也被覆盖.

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

以下是我的笔记摘要list:

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