當前位置:成語大全網 - 新華字典 - Python中list的實現

Python中list的實現

原文鏈接

這篇文章介紹了Python中list是如何實現的。

在Python中list特別有用。讓我們來看下list的內部是如何實現的。

來看下面簡單的程序,在list中添加壹些整數並將他們打印出來。

正如妳所看到的,list是可以叠代的。

Python中list是用下邊的C語言的結構來表示的。 ob_item 是用來保存元素的指針數組,allocated是 ob_item 預先分配的內存總容量

讓我們來看下當初始化壹個空list的時候發生了什麽 L = []

非常重要的是知道list申請內存空間的大小(後文用allocated代替)的大小和list實際存儲元素所占空間的大小( ob_size )之間的關系, ob_size 的大小和 len(L) 是壹樣的,而allocated的大小是在內存中已經申請空間大小。通常妳會看到allocated的值要比 ob_size 的值要大。這是為了避免每次有新元素加入list時都要調用realloc進行內存分配。接下來我們會看到更多關於這些的內容。

我們在list中追加壹個整數:L.append(1)。發生了什麽?調用了內部的C函數app1()

來讓我們看下 list_resize() , list_resize() 會申請多余的空間以避免調用多次 list_resize() 函數,list增長的模型是:0, 4, 8, 16, 25, 35, 46, 58, 72, 88, …

開辟了四個內存空間來存放list中的元素,存放的第壹個元素是1。妳可以從下圖中看到L[0]指向了我們剛剛加進去的元素。虛線的框代表了申請了但是還沒有使用(存儲元素)的內存空間

現在我們在列表的第壹個位置插入壹個整數5:L.insert(1, 5),看看內部發生了什麽。調用了ins1()

當妳彈出list的最後壹個元素:L.pop()。調用listpop(), list_resize 在函數listpop()內部被調用,如果這時 ob_size (譯者註:彈出元素後)小於allocated(譯者註:已經申請的內存空間)的壹半。這時申請的內存空間將會縮小。

Pop的時間復雜度是O(1)

Python list對象有壹個方法可以移除壹個指定的元素。調用listremove()。

切開list和刪除元素,調用了 list_ass_slice() (譯者註:在上文slice list between element's slot and element's slot + 1被調用),來看下 list_ass_slice() 是如何工作的。在這裏,低位為1 高位為2(譯者註:傳入的參數),我們移除在1號內存空間存儲的數據5

Remove的時間復雜度為O(n)

文中list的sort部分沒有進行翻譯

核心部分