據說Python中tuple的速度比list快，如果tuple中包含有list元素，tuple是如何保持比list快的？

01-02

很簡單，Tuple是immutable的，從資源的角度來說沒有沒事有事malloc的需求，也沒有定址的要求，當然比List快，簡單的類比就是C裡面的定長數組和自己實現的鏈表。

那麼Tuple裡面有List如何保持比List還快，那是因為Tuple裡面List元素只是一個引用，簡單的類比就是C的定長數組裡面一個元素是一個指向某個鏈表的指針。

可以走Python簡單測一發

&>&>&> b= ["a",]

&>&>&> a = (b, 1)

&>&>&> a

(["a"], 1)

&>&>&> b.append("c")

&>&>&> a

(["a", "c"], 1)

Background：所陳述觀點，均以CPython2.7為測試平台

----------------

題主說 "據說Python中tuple的速度比list快"

這句話沒說清楚，究竟怎麼快，快也得有個比法。劉翔快不快? 拉劉翔去跑馬拉松何如？

這裡的「比誰快」究竟怎麼比。

1. 對象的創建時性能的比較

沒有實測的時間性能數據木有說服力~ 看圖

用相同的內容去構造對象，兩者的速度差距大於十倍之上

2.對象的的訪問

tuple和list本質上都是array，而且也儲存的都是實際對象的引用reference。(真的不要無腦黑reference，這傢伙是節約內存的大功臣)

Include/tupleobject.h typedef struct { PyObject_VAR_HEAD PyObject *ob_item[1];


    /* ob_item contains space for "ob_size" elements.

     * Items must normally not be NULL, except during construction when

     * the tuple is not yet visible outside the function that builds it.

     */

} PyTupleObject;
Include/listobject.h

typedef struct {

    PyObject_VAR_HEAD

    /* Vector of pointers to list elements.  list[0] is ob_item[0], etc. */

    PyObject **ob_item;

/* ob_item contains space for "allocated" elements. The number * currently in use is ob_size. * Invariants: * 0 &<= ob_size &<= allocated * len(list) == ob_size * ob_item == NULL implies ob_size == allocated == 0 * list.sort() temporarily sets allocated to -1 to detect mutations. * * Items must normally not be NULL, except during construction when * the list is not yet visible outside the function that builds it. */ Py_ssize_t allocated; } PyListObject;

在兩者的結構體定義也能看出，其實兩者在定義的時候是極為相似的。

而所謂的前者是immutable，而後者是mutable，都是後來限定的操作。

創建對象之後，tuple對象就不支持插入操作了。tuple的大小在創建時就固定了，而list支持插入等改變對象內存大小的操作。

對於數據的訪問，兩者理論上都是一樣快的，都支持index操作，理論時間是O(1). array的特性就是爽啊~

3.從CPython源碼實現的角度來分析

Tuple 實現的時為小尺寸的對象，採用了緩存策略

Object/tupleobject.c /* Speed optimization to avoid frequent malloc/free of small tuples */ #ifndef PyTuple_MAXSAVESIZE #define PyTuple_MAXSAVESIZE 20 /* Largest tuple to save on free list */ #endif #ifndef PyTuple_MAXFREELIST #define PyTuple_MAXFREELIST 2000 /* Maximum number of tuples of each size to save */ #endif

#if PyTuple_MAXSAVESIZE &> 0 /* Entries 1 up to PyTuple_MAXSAVESIZE are free lists, entry 0 is the empty tuple () of which at most one instance will be allocated. */ static PyTupleObject *free_list[PyTuple_MAXSAVESIZE]; static int numfree[PyTuple_MAXSAVESIZE]; #endif #ifdef COUNT_ALLOCS Py_ssize_t fast_tuple_allocs; //利用緩存的內存創建新的tuple多少次 Py_ssize_t tuple_zero_allocs; //記錄空tuple創建了多少次 #endif

CPython 在實現tuple的時候，考慮到了為了避免頻繁的為小尺寸（20個對象容量，PyTuple_MAXFREELIST）的tuple對象。每一次通過虛擬機申請來的內存，並不會釋放，而是通過單鏈表的形式維護起來(這裡一丟丟小技巧，看源碼的時候可能注意一下就行了)。然後numfree數組記錄了當前小tuple空閑被釋放掉緩存的數目，以tuple長度為依據來記錄，numfree[4]得到的就是當前len(tuple)為4的緩存內存數目。

可能會問，緩存是好，但是如果緩存的太多了呢？豈不是也是內存浪費？ yes

在實現的時候，PyTuple_MAXFREELIST就限定了各種長度的小tuple最多能夠緩存多少個。默認的參數上限時2000個。

list支持創建對象後改變對象的大小，而tuple不支持

有所長，有所短。list支持改變大小是要付出性能代價的

圖怎麼來的

from matplotlib import pyplot import pylab


size = 200

axis_x = [i for i in xrange(size)]

axis_y = []

for i in xrange(size):

    axis_y.append(axis_y.__sizeof__())

pyplot.title("The size of list.") pyplot.xlabel("Number of objects in the list.") pyplot.ylabel("List size") pyplot.plot(axis_x, axis_y, color = "red") pylab.show()

可以看到每當尺寸增長觸碰到一定的閾值的時候，就會觸發系統為這個list對象申請到更多的內存，這都是可能觸發系統本身的page fault exception來實現的。我機器上網路有點問題，不能安裝perf，有興趣的話可以嘗試用perf去測一測當你嘗試去改變list的大小的時候，會觸發那些系統異常或者IO，性能怎麼樣。

從插入數據的角度來分析

tuple壓根就不支持插入，而list是支持的，且插入數據不會太多的話不用過多的申請甚至不用申請額外的內存。而tuple想要做到類似 list.append(object)的功能只能創建新的tuple對象，(1,2) + (3,4)得到的是一個全新的對象。

Reference:

《High Performance Python》Micha Gorelick / lan Ozsvald

《Python源碼剖析》陳儒

----------------------------------------------------------

歡迎交流討論 : )

tuple裡面就算有list也只是list的引用啊，最後tuple還是一個不可變的類型。你修改裡面元素的list，tuple還是原來的樣子。

所以tuple裡面有list對tuple的性能沒影響。

tuple固定大小其實類似於c語言的數組，因為空間分配固定且連續，所以可以快速定位。list對應鏈表分配離散，所以查找必須遍歷。你可以去看看數據結構方面的書，看看就知道2者的區別。