关于性能：在哪里可以找到Python中内置序列类型的时间和空间复杂度

我一直无法找到这些信息的来源，除非自己亲自检查Python源代码来确定对象的工作方式。有人知道我可以在网上找到吗？

---

在py dot org Wiki上检出TimeComplexity页面。它至少涉及时间复杂度的设置/字典/列表/等。

---

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很便宜。

---

如果您问的是我想问的问题，则可以在此处找到它们……第476页及以后。

它是围绕Python优化技术编写的；主要是时间效率的Big-O表示法，没有太多的内存。

---