python复杂类型详解

复杂类型详解

list列表实现栈和队列

二者的区别在于对数据的存取顺序：

队列是，先存入的数据最先取出，即“先进先出”。
栈是，最后存入的数据最先取出，即“后进先出”。

list实现队列

存入数据时使用 insert() 方法，设置其第一个参数为 0，即表示每次都从最前面插入数据；

读取数据时，使用 pop() 方法，即将队列的最后一个元素弹出。

#定义一个空列表，当做队列
queue = []
#向列表中插入元素
queue.insert(0,1)
queue.insert(0,2)
queue.insert(0,"hello")
print(queue)
print("取一个元素：",queue.pop())
print("取一个元素：",queue.pop())
print("取一个元素：",queue.pop())

list实现栈

append() 方法存入数据；使用 pop() 方法读取数据。

#定义一个空 list 当做栈
stack = []
stack.append(1)
stack.append(2)
stack.append("hello")
print(stack)
print("取一个元素：",stack.pop())
print("取一个元素：",stack.pop())
print("取一个元素：",stack.pop())

collections模块实现栈和队列

标准库的 collections 模块中的 deque 结构体，它被设计成在两端存入和读取都很快的特殊 list，可以用来实现栈和队列的功能。

import collections
queueAndStack = collections.deque()
queueAndStack.append(1)
queueAndStack.append(2)
queueAndStack.append("hello")
print(list(queueAndStack))
#实现队列功能，从队列中取一个元素，根据先进先出原则，这里应输出 1
print(queueAndStack.popleft())
#实现栈功能，从栈里取一个元素，根据后进先出原则，这里应输出 hello
print(queueAndStack.pop())
#再次打印列表
print(list(queueAndStack))

列表和元组的底层实现

list 列表

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;

本质上是一个长度可变的连续数组。其中 ob_item 是一个指针列表，里边的每一个指针都指向列表中的元素，而 allocated 则用于存储该列表目前已被分配的空间大小。

当前列表分配的空间已满（即 allocated == len(list)），则会向系统请求更大的内存空间，并把原来的元素全部拷贝过去。

tuple元组

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;

本质也是一个数组，但是空间大小固定。

字典和集合的底层实现

字典和集合是进行过性能高度优化的数据结构，特别是对于查找、添加和删除操作。

原理

字典和集合的内部结构都是一张哈希表：

对于字典而言，这张表存储了哈希值（hash）、键和值这 3 个元素。
而对集合来说，哈希表内只存储单一的元素。

为了提高存储空间的利用率，现在的哈希表除了字典本身的结构，会把索引和哈希值、键、值单独分开。

平均情况下，仍能保证插入、查找和删除的时间复杂度为 O(1)。

哈希表插入数据

当向字典中插入数据时，Python 会首先根据键（key）计算出对应的哈希值（通过 hash(key) 函数），而向集合中插入数据时，Python会根据该元素本身计算对应的哈希值（通过 hash(valuse) 函数）。

得到哈希值（例如为 hash）之后，再结合字典或集合要存储数据的个数（例如 n），就可以得到该元素应该插入到哈希表中的位置（比如，可以用 hash%n 的方式）。

哈希表查找数据

根据哈希值，找到该元素应该存储到哈希表中的位置，然后和该位置的元素比较其哈希值和键（集合直接比较元素值）：

如果相等，则证明找到；
反之，则证明当初存储该元素时，遇到了哈希冲突，需要继续使用当初解决哈希冲突的方法进行查找，直到找到该元素或者找到空位为止。

哈希表删除元素

对这个位置的元素赋于一个特殊的值，等到重新调整哈希表的大小时，再将其删除。

哈希冲突的发生往往会降低字典和集合操作的速度。因此，为了保证其高效性，字典和集合内的哈希表，通常会保证其至少留有 1/3 的剩余空间。随着元素的不停插入，当剩余空间小于 1/3 时，Python 会重新获取更大的内存空间，扩充哈希表，与此同时，表内所有的元素位置都会被重新排放。

深拷贝和浅拷贝

浅拷贝

指的是重新分配一块内存，创建一个新的对象，但里面的元素是原对象中各个子对象的引用。

常见的浅拷贝的方法，是使用数据类型本身的构造器。

1
2
3

list1 = [1, 2, 3]
list2 = list(list1)
print(list2)

对于可变的序列，还可以通过切片操作符“：”来完成浅拷贝

1
2
3

list1 = [1, 2, 3]
list2 = list1[:]
print(list2)

函数 copy.copy() 函数，适用于任何数据类型。

import copy
list1 = [1, 2, 3]
list2 = copy.copy(list1)
print(list2)

深拷贝

是指重新分配一块内存，创建一个新的对象，并且将原对象中的元素，以递归的方式，通过创建新的子对象拷贝到新对象中。因此，新对象和原对象没有任何关联。

copy.deepcopy() 来实现对象的深度拷贝。

1
2
3

import copy
list1 = [[1, 2], (30, 40)]
list2 = copy.deepcopy(list1)

拷贝对象中存在指向自身的引用，那么程序很容易陷入无限循环。