列表和元组
# 列表和元组
列表和元组的区别
- 列表：长度大小不固定，可以随意地增加、删除或者改变元素（mutable）。
- 元组：长度大小固定，无法增加删减或者改名（immutable）。
# 列表底层实现
列表的底层是由动态数组+指针实现的。
这意味着列表允许添加或删除元素，并且列表将通过分配或释放内存来自动调整保存这些元素的后备存储。列表同时支持多种数据类型，意味着数据通常不那么紧密，整个结构占用更多的空间。
l = [1, 2, 3]
l.__sizeof__() # 104
tup = (1, 2, 3)
tup.__sizeof__() # 48
2
3
4
5
list 列表实现的源码文件 listobject.h (opens new window) 和 listobject.c (opens new window)。
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;
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
list本质上是一个长度可变的连续数组。其中ob_item是一个指针列表，里边的每一个指针都指向列表中的元素，而allocated则用于存储该列表目前已被分配的空间大小。
# 元组底层实现
tuple元组实现的源码文件 tupleobject.h (opens new window) 和 tupleobject.c (opens new window)
typedef struct {
PyObject_VAR_HEAD
/* 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. */
PyObject *ob_item[1];
} PyTupleObject;
2
3
4
5
6
7
tuple和list相似，本质也是一个数组，但是空间大小固定。
# 性能
元组要比列表更加轻量级一些，总体上来说，元组的性能速度要略优于列表。
# tuple
Python 会在后台，对静态数据做一些资源缓存（resource caching）。通常来说，因为垃圾回收机制的存在，如果一些变量不被使用了，Python 就会回收它们所占用的内存，返还给操作系统，以便其他变量或其他应用使用。
但是对于一些静态变量，比如元组，如果它不被使用并且占用空间不大时，Python 会暂时缓存这部分内存。这样，下次我们再创建同样大小的元组时，Python 就可以不用再向操作系统发出请求，去寻找内存，而是可以直接分配之前缓存的内存空间，这样就能大大加快程序的运行速度。
在元组的底层定义了一个free_list，拥有提高效率，避免频繁的调用系统函数 free和 malloc向操作系统申请和释放空间，申请过的且小于一定大小的元组，在释放的时候会被放进这个free_list中以供下次使用。
static PyTupleObject *free_list[PyTuple_MAXSAVESIZE];
下面的例子，是计算初始化一个相同元素的列表和元组分别所需的时间。我们可以看到，元组的初始化速度，要比列表快 5 倍。
python -m timeit 'l=(1,2,3,4,5,6,7,8,9)'
# 20000000 loops, best of 5: 12.9 nsec per loop
python -m timeit 'l=[1,2,3,4,5,6,7,8,9]'
# 5000000 loops, best of 5: 56.3 nsec per loop
2
3
4
# list
在内部，列表表示为数组；最大的成本来自超出当前分配大小的增长（因为所有内容都必须移动），或者来自在开头附近的某个位置插入或删除（因为之后的所有内容都必须移动）。如果您需要在两端添加/删除，请考虑改用collections.deque。
| Operation | Average Case | Amortized Worst Case |
|---|---|---|
| Copy | O(n) | O(n) |
| Append[1] | O(1) | O(1) |
| Pop last | O(1) | O(1) |
| Pop intermediate[2] | O(n) | O(n) |
| Insert | O(n) | O(n) |
| Get Item | O(1) | O(1) |
| Set Item | O(1) | O(1) |
| Delete Item | O(n) | O(n) |
| Iteration | O(n) | O(n) |
| Get Slice | O(k) | O(k) |
| Del Slice | O(n) | O(n) |
| Set Slice | O(k+n) | O(k+n) |
| Extend[1] | O(k) | O(k) |
| Sort (opens new window) | O(n log n) | O(n log n) |
| Multiply | O(nk) | O(nk) |
| x in s | O(n) | |
| min(s), max(s) | O(n) | |
| Get Length | O(1) | O(1) |
# collections.deque
deque（双端队列）在内部表示为双向链表。（好吧，为了提高效率，使用数组列表而不是对象列表。）两端都可以访问，但是即使查看中间也很慢，并且从中间添加或删除仍然更慢。
| Operation | Average Case | Amortized Worst Case |
|---|---|---|
| Copy | O(n) | O(n) |
| append | O(1) | O(1) |
| appendleft | O(1) | O(1) |
| pop | O(1) | O(1) |
| popleft | O(1) | O(1) |
| extend | O(k) | O(k) |
| extendleft | O(k) | O(k) |
| rotate | O(k) | O(k) |
| remove | O(n) | O(n) |
# 其他
使用list()创建列表和[]创建列表的区别。
l1 = list()
l2 = []
2
区别主要在于list()是一个function call，Python的function call会创建stack，并且进行一系列参数检查的操作，比较expensive，反观[]是一个内置的C函数，可以直接被调用，因此效率高。
使用dis (opens new window)字节码反汇编器分析。
>>> def empty_list1():
... return list()
...
>>> def empty_list2():
... return []
...
>>> dis.dis(empty_list1)
2 0 LOAD_GLOBAL 0 (list)
2 CALL_FUNCTION 0
4 RETURN_VALUE
>>> dis.dis(empty_list2)
2 0 BUILD_LIST 0
2 RETURN_VALUE
2
3
4
5
6
7
8
9
10
11
12
13
14