RPA手把手——【資料結構和算法】詳解清單和元組

藝賽旗 RPA9.0全新首發免費下載下傳 點選下載下傳

http://www.i-search.com.cn/index.html?from=line1

總覽

兩者的主要差別總結如下：

清單是動态數組，它們可變且可以重設長度（改變其内部元素的個數）。

元組是靜态數組，它們不可變，且其内部資料一旦建立便無法改變。

元組緩存于 Python 運作時環境，這意味着我們每次使用元組時無須通路核心去配置設定記憶體。

這些差別揭示了兩者在設計哲學上的不同：元組用于描述一個不會改變的事物的多個屬性，而清單可被用于儲存多個互相獨立對象的資料集合。比如，儲存一個電話号碼适合用元組：它們不會改變，如果改變則意味着他們代表了一個新的對象，也就是另一個電話号碼。同樣，儲存一個多項式的系數适合用元組，因為不用的系數代表了不同的多項式。另一方面，儲存藝賽旗論壇所有使用者的名字更适合用清單：雖然資料的内容和大小時刻在發生變化，但始終表示同一個概念。

值得注意的是，清單和元組都可以接受混合類型。這會帶來一些額外的開銷并減少一些可能的優化。如果我們強制要求所有的資料都是同一個類型，那麼就可以避免這些開銷，可以通過使用 numpy 降低記憶體和計算的開銷。另外，對于非數字的資料，還有一些其他子產品，如 blist 和 array 也能夠減少這些開銷。這暗示了一個觀點：通用代碼會比為某個特定問題設計的代碼慢很多。

動态數組：清單

一旦我們建立了清單，我們就可以根據需要随意改變其内容：

numbers = [5, 8, 1, 3, 2, 6]

numbers[2] = 2 * numbers[0]

numbers

[5, 8, 10, 3, 2, 6]

如上，這個操作的複雜度是 O(1)，因為我們可以立即找到第 0 個和第 2 個資料儲存的位置。

另外，我們可以給清單添加新的資料來增加其大小：

len(numbers)

6

numbers.append(42)

numbers

[5, 8, 1, 3, 2, 6, 42]

len(numbers)

7

這是因為動态數組支援 resize 操作，可以增加數組的容量。當建立 N 個元素的清單時，Python 的動态記憶體配置設定長 N＋1 個元素的記憶體，第一個元素存儲清單長度和清單的元資訊。當一個大小為 N 的清單第一次需要添加資料時，Python 會建立一個新的清單，足夠存放原來的 N 個元素以及額外需要添加的元素。不過，實際配置設定的并不是 N+1 個元素，而是 M 個，M > N + 1，這是為了給未來的添加預留白間。然後舊清單的資料被複制到新清單中，舊清單則被銷毀。從設計理念上來說，一個 Append 操作很可能是很多 Append 操作的開始，通過額外配置設定記憶體來減少可能的記憶體配置設定和記憶體複制的次數。這一點非常重要，因為記憶體複制可能非常昂貴，特别是當清單大小開始增長以後。

對于一個具有 N 個元素的清單，當一次 Append 操作發生時，新清單要配置設定多少記憶體（額外 M 個元素，需多配置設定一個元素存儲長度）呢？答案是：

M=(N>>3)+(N<9?3:6)M=(N>>3)+(N<9?3:6)

我們來看 Python3.6.1 的清單 resize 過程，源代碼位于 Objects/listobject.c 中的 list_resize 函數：

static int

list_resize(PyListObject *self, Py_ssize_t newsize)

{

PyObject **items;

size_t new_allocated;

Py_ssize_t allocated = self->allocated;

/* Bypass realloc() when a previous overallocation is large enough
   to accommodate the newsize.  If the newsize falls lower than half
   the allocated size, then proceed with the realloc() to shrink the list.
*/
if (allocated >= newsize && newsize >= (allocated >> 1)) {
    assert(self->ob_item != NULL || newsize == 0);
    Py_SIZE(self) = newsize;
    return 0;
}

/* 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 > SIZE_MAX - newsize) {
    PyErr_NoMemory();
    return -1;
} else {
    new_allocated += newsize;
}

if (newsize == 0)
    new_allocated = 0;
items = self->ob_item;
if (new_allocated <= (SIZE_MAX / sizeof(PyObject *)))
    PyMem_RESIZE(items, PyObject *, new_allocated);
else
    items = NULL;
if (items == NULL) {
    PyErr_NoMemory();
    return -1;
}
self->ob_item = items;
Py_SIZE(self) = newsize;
self->allocated = new_allocated;
return 0;
           

}

結合 C 源碼我們來舉個例子，當一個 list 長度為 8 時，發生 append 操作後：

new_size = 原有的 size ＋ append 一個對象 = 8 + 1 = 9

newsize 為 9，二進制是 1001，9 >> 3 = 1

new_allocated = 9 >> 3 + 6 = 7

new_allocated += new_size，為 9 + 7 ＝ 16

清單的最終占用記憶體大小為 16

額外配置設定的空間一般來說非常小，但累加起來就不可忽視。當你在維護很多小清單或一個非常大的清單時，這一效果會變得十分顯著。

靜态數組：元組

元組固定且不可變。這意味着一旦元組被建立，和清單不同，它的内容無法被修改。

t = (1, 2, 3, 4)

t[0] = 5

Traceback (most recent call last):

File “”, line 1, in

TypeError: ‘tuple’ object does not support item assignment

雖然它們不支援改變大小，但是我們可以将兩個元組合并成一個新元組。這個操作類似于清單的 append，但是又不會額外的配置設定記憶體。但我們不能把它當成 append，因為每次都會進行一個配置設定記憶體和記憶體 copy 操作。

另一個元組的靜态本質帶來的好處是，資源緩存。Python 是一門垃圾收集語言，當一個變量不用了，記憶體會被回收并交回給作業系統。但是，對于一個長度為 1~20 個元素的元組，當它不再被用時，記憶體不會立即返還給作業系統，而是為了以後應用而暫緩保留，當一個新的元組被建立時，我們不會向作業系統重新申請配置設定記憶體，因為我們已經有了預留的記憶體。

這看上去可能隻是一個細微的好處，但實際上是元組一個很神奇的地方：它們可以被輕松迅速地建立，因為它們可以避免跟作業系統打交道，而後者很花時間。下面的例子顯示了初始化一個清單比初始化一個元組慢了 5 倍左右——如果是在一個循環内部，這點差别會很快累加起來！

指令行中

C:\Users\young ray>python -m timeit “l = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]”

10000000 loops, best of 3: 0.0751 usec per loop

C:\Users\young ray>python -m timeit “t = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)”

100000000 loops, best of 3: 0.0159 usec per loop