【数据结构和算法】详解列表和元组
总览
两者的主要区别总结如下：
- 列表是动态数组，它们可变且可以重设长度（改变其内部元素的个数）。
- 元组是静态数组，它们不可变，且其内部数据一旦创建便无法改变。
- 元组缓存于 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)$$
我们来看 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 "<stdin>", line 1, in <module>
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
