我在哪裏可以找到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便宜。