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

Question

我一直无法找到这个信息的来源，我自己也无法通过Python源代码来确定对象的工作方式。有谁知道我在哪里可以找到这个在线？

Answer 1

签出python org wiki上的TimeComplexity页面。至少在时间复杂度方面，它涵盖了set/dicts/lists /等。

Answer 2

如果你问我认为你的问题，你可以找到它们Here ...第476页。

它是围绕Python的优化技术编写的;它主要是时间效率的Big-O符号，没有太多的记忆。

Answer 3

Raymond D. Hettinger对an excellent talk（slides）做了关于Python的内置集合，名为'Core Python Containers - Under Hood'。我看到的版本主要集中在set和dict，但list也被覆盖。

也有一些照片来自EuroPython在a blog相关的幻灯片。

这里是我的笔记上list摘要：

• 房屋项目，如指针数组。下标花费O（1）次。追加成本O（1）时间。插入成本O（n）时间。
• 试图避免memcpy由于过度分配而增长。许多小名单将浪费大量空间，但大型名单永远不会浪费超过12.5％的空间。
• 一些操作预先大小。给出的例子是range(n),map(),list(),[None] * n和切片。
• 收缩时，只有在浪费50％的空间时，数组才会变为realloc。 pop便宜。