看一下python的 cpython 實(shí)現(xiàn)（cpython就是python的c實(shí)現(xiàn)版本）
l = []
l.append(1)
l.append(2)
l.append(3)
列表對(duì)象的c語(yǔ)言結(jié)構(gòu)體
Cpython 中的列表實(shí)現(xiàn)類似于下面的 C 結(jié)構(gòu)體疮鲫。ob_item 是指向列表對(duì)象的指針數(shù)組八秃。allocated 是申請(qǐng)內(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ì)多申請(qǐng)一些內(nèi)存惠啄，避免頻繁調(diào)用 list_resize() 函數(shù)。列表的增長(zhǎng)模式為：0任内，4撵渡，8，16死嗦，25趋距，35，46越除，58节腐，72，88……
python的這個(gè)值是怎么來(lái)的呢
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è)說(shuō)法摘盆，每當(dāng)來(lái)了一個(gè)新要求的大幸砣浮（比如插入操作中的原大小+1,或刪除操作中原大小-1）：newsize，這時(shí)python并不直接對(duì)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è)用來(lái)裝列表元素的槽空間坦弟，并且第一個(gè)空間中為整數(shù) 1。如下圖顯示 l[0] 指向我們新添加的整數(shù)對(duì)象官地。虛線的方框表示已經(jīng)分配但沒有使用的槽空間酿傍。
列表追加元素操作的平均復(fù)雜度為 O(1)。
繼續(xù)添加新的元素：l.append(2)驱入。調(diào)用 list_resize 函數(shù)赤炒，參數(shù)為 n+1 = 2， 但是因?yàn)橐呀?jīng)申請(qǐng)了 4 個(gè)槽空間亏较，所以不需要再申請(qǐng)內(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)分配但沒有使用的槽空間。現(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ù)對(duì)象图仓，但是最為關(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。
再?gòu)目s小來(lái)看劫窒，當(dāng)newsize小于allocated/2時(shí)本今，意味著需要縮小空間大小了（節(jié)約內(nèi)存）。
該縮小多少呢，同樣是基于上面那個(gè)函數(shù)冠息。由它計(jì)算出一個(gè)增量來(lái)挪凑，在什么基礎(chǔ)上增呢？
allocated/2逛艰，對(duì)就是在這個(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欠动，那么如果對(duì)于那么刪除后立即執(zhí)行插入操作效率就很不理想了丹诀。）
以上這個(gè)策略，可以實(shí)現(xiàn)不會(huì)過去頻繁地調(diào)用realloc這個(gè)低效率的函數(shù)翁垂。
Remove 操作
Python 的列表對(duì)象有個(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)方法比較有趣啼肩。我們?cè)趧h除列表位置 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中簡(jiǎn)單而重要的數(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列表中的元素可以是任意的對(duì)象芬沉。
在底層實(shí)現(xiàn)上躺同，由于對(duì)象大小未知，并不能像數(shù)組那樣連續(xù)排在內(nèi)存里丸逸。
python列表維護(hù)了一個(gè)指針數(shù)組蹋艺，每個(gè)指針指向不同的對(duì)象，
這也造成了一些弊端黄刚，例如列表中對(duì)象大小一樣的時(shí)候就很虧了捎谨，浪費(fèi)空間不說(shuō)，
跟C的數(shù)組相比，它離散的對(duì)象位置不能很好地利用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逆甜，
那么也就是說(shuō)tuple大小將不會(huì)改變，就不用像list那樣搞預(yù)分配了致板，更節(jié)省內(nèi)存交煞。
很多人說(shuō)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í)測(cè)看來(lái)，這個(gè)結(jié)論是不明顯的萝挤。
list和tuple在c實(shí)現(xiàn)上是很相似的御毅，對(duì)于元素?cái)?shù)量大的時(shí)候，
都是一個(gè)數(shù)組指針怜珍，指針指向相應(yīng)的對(duì)象端蛆，找不到tuple比list快的理由。
但對(duì)于小對(duì)象來(lái)說(shuō)酥泛，tuple會(huì)有一個(gè)對(duì)象池今豆，所以小的、重復(fù)的使用tuple還有益處的柔袁。
為什么要有tuple呆躲，還有很多的合理性。
實(shí)際情況中的確也有不少大小固定的列表結(jié)構(gòu)捶索，例如二維地理坐標(biāo)等插掂；
另外tuple也給元素天然地賦予了只讀屬性。
認(rèn)為tuple比list快的人大概是把python的tuple和list類比成C++中的數(shù)組和列表了腥例。
