看一下python的 cpython 實(shí)現(xiàn)（cpython就是python的c實(shí)現(xiàn)版本）

l = []
l.append(1)
l.append(2)
l.append(3)

列表對象的c語言結(jié)構(gòu)體

Cpython 中的列表實(shí)現(xiàn)類似于下面的 C 結(jié)構(gòu)體。ob_item 是指向列表對象的指針數(shù)組。allocated 是申請內(nèi)存的槽的個(gè)數(shù)。

列表初始化

看看初始化一個(gè)空列表的時(shí)候發(fā)生了什么，例如：l = []。

arguments: size of the list = 0
returns: list object = []
PyListNew:
    nbytes = size * size of global Python object = 0
    allocate new list object
    allocate list of pointers (ob_item) of size nbytes = 0
    clear ob_item
    set list's allocated var to 0 = 0 slots
    return list object

要分清列表大小和分配的槽大小，這很重要。列表的大小和 len(l) 的大小相同。分配槽的大小是指已經(jīng)在內(nèi)存中分配了的槽空間數(shù)。通常分配的槽的大小要大于列表大小，這是為了避免每次列表添加元素的時(shí)候都調(diào)用分配內(nèi)存的函數(shù)。下面會(huì)具體介紹。

append操作

向列表添加一個(gè)整數(shù)：l.append(1) 時(shí)發(fā)生了什么？調(diào)用了底層的 C 函數(shù) app1()。

arguments: list object, new element
returns: 0 if OK, -1 if not
app1:
    n = size of list
    call list_resize() to resize the list to size n+1 = 0 + 1 = 1
    list[n] = list[0] = new element
    return 0

下面是 list_resize() 函數(shù)。它會(huì)多申請一些內(nèi)存，避免頻繁調(diào)用 list_resize() 函數(shù)。列表的增長模式為：0，4，8，16，25，35，46，58，72，88……

python的這個(gè)值是怎么來的呢
So just checking very quickly, Ruby (1.9.1-p129) appears to use 1.5x when appending to an array, and Python (2.6.2) uses 1.125x plus a constant: (in Objects/listobject.c):
換個(gè)說法，每當(dāng)來了一個(gè)新要求的大小（比如插入操作中的原大小+1,或刪除操作中原大小-1）：newsize，這時(shí)python并不直接對list的空間進(jìn)行調(diào)整。而是作個(gè)比較，若新要求的大小在總?cè)萘恐?，總?cè)萘康囊话胫蟿t，不進(jìn)行調(diào)整。

/* This over-allocates proportional to the list size, making room
* for additional growth.  The over-allocation is mild, but is
* enough to give linear-time amortized behavior over a long
 * sequence of appends() in the presence of a poorly-performing
* system realloc().
* The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
*/
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);

/* check for integer overflow */
if (new_allocated > PY_SIZE_MAX - newsize) {

     PyErr_NoMemory();
     return -1;

} else {

     new_allocated += newsize;

}

arguments: list object, new size
returns: 0 if OK, -1 if not
list_resize:
    new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6) = 3
    new_allocated += newsize = 3 + 1 = 4
    resize ob_item (list of pointers) to size new_allocated
    return 0

現(xiàn)在分配了 4 個(gè)用來裝列表元素的槽空間，并且第一個(gè)空間中為整數(shù) 1。如下圖顯示 l[0] 指向我們新添加的整數(shù)對象。虛線的方框表示已經(jīng)分配但沒有使用的槽空間。

列表追加元素操作的平均復(fù)雜度為 O(1)。

繼續(xù)添加新的元素：l.append(2)。調(diào)用 list_resize 函數(shù)，參數(shù)為 n+1 = 2， 但是因?yàn)橐呀?jīng)申請了 4 個(gè)槽空間，所以不需要再申請內(nèi)存空間。再添加兩個(gè)整數(shù)的情況也是一樣的：l.append(3)，l.append(4)。下圖顯示了我們現(xiàn)在的情況。

insert操作

在列表偏移量 1 的位置插入新元素，整數(shù) 5：l.insert(1,5)，內(nèi)部調(diào)用ins1() 函數(shù)。

arguments: list object, where, new element
returns: 0 if OK, -1 if not
ins1:
    resize list to size n+1 = 5 -> 4 more slots will be allocated
    starting at the last element up to the offset where, right shift each element 
    set new element at offset where
    return 0

虛線的方框依舊表示已經(jīng)分配但沒有使用的槽空間?，F(xiàn)在分配了 8 個(gè)槽空間，但是列表的大小卻只是 5。

列表插入操作的平均復(fù)雜度為 O(n)。

Pop 操作

取出列表最后一個(gè)元素 即l.pop()，調(diào)用了 listpop() 函數(shù)。在 listpop() 函數(shù)中會(huì)調(diào)用 list_resize 函數(shù)，如果取出元素后列表的大小小于分配的槽空間數(shù)的一半，將會(huì)縮減列表的大小。

arguments: list object
returns: element popped
listpop:
    if list empty:
        return null
    resize list with size 5 - 1 = 4. 4 is not less than 8/2 so no shrinkage
    set list object size to 4
    return last element

列表 pop 操作的平均復(fù)雜度為 O(1)。

可以看到 pop 操作后槽空間 4 依然指向原先的整數(shù)對象，但是最為關(guān)鍵的是現(xiàn)在列表的大小已經(jīng)變?yōu)?4。

繼續(xù) pop 一個(gè)元素。在 list_resize() 函數(shù)中，size – 1 = 4 – 1 = 3 已經(jīng)小于所分配的槽空間大小的一半，所以縮減分配的槽空間為 6，同時(shí)現(xiàn)在列表的大小為 3。

可以看到槽空間 3 和 4 依然指向原先的整數(shù)，但是現(xiàn)在列表的大小已經(jīng)變?yōu)?3。

再從縮小來看，當(dāng)newsize小于allocated/2時(shí)，意味著需要縮小空間大小了（節(jié)約內(nèi)存）。
該縮小多少呢，同樣是基于上面那個(gè)函數(shù)。由它計(jì)算出一個(gè)增量來，在什么基礎(chǔ)上增呢？
allocated/2，對就是在這個(gè)基礎(chǔ)上，因?yàn)橐坏┯捎趧h除操作導(dǎo)致newsize恰好小于allocated/2時(shí)，就會(huì)執(zhí)行縮小list空間大小的操作。這樣，即節(jié)省了內(nèi)存，又不至于減少內(nèi)存過少，導(dǎo)致效率降低（想像一下，如果每次小于allocated/2時(shí)，就縮小為allocated/2，那么如果對于那么刪除后立即執(zhí)行插入操作效率就很不理想了。）
以上這個(gè)策略，可以實(shí)現(xiàn)不會(huì)過去頻繁地調(diào)用realloc這個(gè)低效率的函數(shù)。

Remove 操作

Python 的列表對象有個(gè)方法，刪除指定的元素： l.remove(5)。底層調(diào)用 listremove() 函數(shù)。

arguments: list object, element to remove
returns none if OK, null if not
listremove:
    loop through each list element:
        if correct element:
            slice list between element's slot and element's slot + 1
            return none
    return null

為了做列表的切片并且刪除元素，調(diào)用了 list_ass_slice() 函數(shù)，它的實(shí)現(xiàn)方法比較有趣。我們在刪除列表位置 1 的元素 5 的時(shí)候，低位的偏移量為 1 同時(shí)高位的偏移量為 2.

arguments: list object, low offset, high offset
returns: 0 if OK
list_ass_slice:
    copy integer 5 to recycle list to dereference it
    shift elements from slot 2 to slot 1
    resize list to 5 slots
    return 0

another one

列表是python中簡單而重要的數(shù)據(jù)結(jié)構(gòu)
list_sample = [1, 2, 3]

超預(yù)分配的量大概只有總量的八分之一，保證不太浪費(fèi)的情況下，也有線性的攤分復(fù)雜度。
new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6)

當(dāng)增加或刪除都有可能引起allocated的變化，當(dāng)目前的allocated滿足
allocated >= newsize && newsize >= (allocated >> 1)
這個(gè)關(guān)系時(shí)，allocated不變，不然更新分配值
allocated = new_allocated + newsize

由于python列表中的元素可以是任意的對象。
在底層實(shí)現(xiàn)上，由于對象大小未知，并不能像數(shù)組那樣連續(xù)排在內(nèi)存里。
python列表維護(hù)了一個(gè)指針數(shù)組，每個(gè)指針指向不同的對象，
這也造成了一些弊端，例如列表中對象大小一樣的時(shí)候就很虧了，浪費(fèi)空間不說，
跟C的數(shù)組相比，它離散的對象位置不能很好地利用CPU高速緩存，造成了遍歷需要更多的CPU周期。
當(dāng)然也有優(yōu)點(diǎn)，例如在某個(gè)位置insert一個(gè)新的元素時(shí)，只要挪動(dòng)部分指針的值就OK了。

一些操作的時(shí)間復(fù)雜度：
append:O(len(append_str))
insert:O(len(str) + len(insert_str))

tuple與list有什么區(qū)別？最重要的區(qū)別就是tuple是immutable，而list是mutable，
那么也就是說tuple大小將不會(huì)改變，就不用像list那樣搞預(yù)分配了，更節(jié)省內(nèi)存。

很多人說tuple比list快，真的如此嗎？
Python代碼

size = 1000000  

a = []  
for i in xrange(0, size):  
    a.append(i)  
b = tuple(a)  

for t in xrange(0, 32):  
    sum = 0  
    for e in b:  
        sum += e  

分別遍歷list和tuple，跑得的時(shí)間是6.925s和6.771s
從實(shí)測看來，這個(gè)結(jié)論是不明顯的。

list和tuple在c實(shí)現(xiàn)上是很相似的，對于元素?cái)?shù)量大的時(shí)候，
都是一個(gè)數(shù)組指針，指針指向相應(yīng)的對象，找不到tuple比list快的理由。
但對于小對象來說，tuple會(huì)有一個(gè)對象池，所以小的、重復(fù)的使用tuple還有益處的。

為什么要有tuple，還有很多的合理性。
實(shí)際情況中的確也有不少大小固定的列表結(jié)構(gòu)，例如二維地理坐標(biāo)等；
另外tuple也給元素天然地賦予了只讀屬性。

認(rèn)為tuple比list快的人大概是把python的tuple和list類比成C++中的數(shù)組和列表了。