Python 与数据结构 —— 基于数组的序列类型

Python 中的序列类型包含内置的 list、tuple、str 等，它们有很多明显的共同点。比如都支持通过索引语法（seq[k]）获取序列中的某个特定元素；底层的结构都是用数组来实现的。

Low-Level Array

计算机系统一般都包含有数量庞大的内存空间，为了跟踪具体某段数据实际的存储位置，计算机加入了称为内存地址（memory address）的抽象形式。每个字节的存储空间都会关联一个独特的数字作为其地址。

memory address

计算机的内存为 random access memory (RAM)，即任意一个 byte 内存的读取与写入耗费的时间都是 O(1)。

通常来说，编程语言会跟踪每一个标识符及其对应的值的位置（内存地址）。为了方便起见，一组相关联的变量则可以保存在一段连续的内存中，即数组（array）。
比如字符串实际上是由独立的字符组成的有序的序列：

string

数组中的每一个元素都占据同样大小的存储空间，使得任意一个元素的访问和更新都可以通过索引以常量的时间完成。

存储引用的数组

假如需要用数组保存如下的一个姓名列表：
[Rene, Joseph, Janet, Jonas, Helen, Virginia, ...]

使用数组的话，则需要确保数组中的每一个元素都占据同样的内存大小。但字符串本身具有差异很大的长度。
当然可以尝试为数组中的每一个元素都分配足够大的内存空间，保证即使最长的字符串也不会超出，但这样必然会导致内存的浪费。

Python 的方案是在 list 或 tuple 中不保存字符串对象本身而是保存其引用。即列表中只是包含一系列内存地址，每一个地址都指向对应元素实际的存储位置。

reference

即便每一个字符串的大小并不相同，列表中保存的字符串的内存地址却都是固定的（64bit）。

由于 list 和 tuple 中保存的是引用，导致同一个对象有可能成为多个 list 中某个元素的实体。比如对某个 list 执行分片操作后，分片中的元素实际上和母列表中对应的元素指向同样的对象。如 temp = primes[3:6]：

slice

若对分片中的某个元素重新赋值，则直接将该元素替换为新的内存地址（指向新对象）即可，如执行 temp[2] = 15：

slice

一个更显著的例子如 counters = [0] * 8，生成的 counters 列表中的 8 个数字 0 实际上都指向了同一个数字对象。

numbers
这种方式初看上去很容易出现混乱，但是得益于数字本身是不可变对象，即使为数组中的某个元素重新赋值（比如 counters[2] = 1），也只是将当前位置保存的对数字 0 的引用替换为指向新的数字 1 的引用。而原数字 0 本身不发生任何变化，即数组中指向数字 0 的其他元素不受任何影响。
numbers

存储数值的数组

前面提到过字符串是一种存储一系列字符（而不是这些字符的地址）的序列，这种更直接的形式称为 compact array。它相对于前面的存储引用的数组有着性能上的优势，且需要更少的内存。

比如存储一个包含一百万个 64-bit 整数的序列，理论上只需要 64 MB 的内存。实际上 Python 里的 list 需要 4 到 5 倍的容量去储存这些值。
此外对于计算而言，compact array 将有关联的数据直接保存在一段连续的内存中，容易获得更高的性能。

动态数组

在创建 low-level 数组时，其大小必须精确地、显式地声明，从而使系统可以为其分配适当的内存空间。但是这些内存附近的空间有可能提供给其他数据用于储存，因此数组在初始化后其容量一般是固定的，其中保存的元素的数量不能超越这个限制。

Python 的 list 类采用了一种称为 dynamic array 的机制，使其看上去没有长度的限制，其容量可以随着元素的添加不断地增长。
list 实例会在底层维护着一个容量比当前 list 更大的数组，这个容量更大的数组使得为 list 添加元素变得方便很多。当元素数量持续增长直到数组中预留的空间也要被用尽时，list 会申请一个容量更大的数组替代之前容量较小的数组，旧的数组则被系统回收。

测试代码：

import sys

data = []

for count in range(20):
    data.append(None)
    length = len(data)
    size = sys.getsizeof(data)
    print('Length: {0:3d}; Size in bytes: {1:4d}'.format(length, size))

输出结果：

Length:   1; Size in bytes:   88
Length:   2; Size in bytes:   88
Length:   3; Size in bytes:   88
Length:   4; Size in bytes:   88
Length:   5; Size in bytes:  120
Length:   6; Size in bytes:  120
Length:   7; Size in bytes:  120
Length:   8; Size in bytes:  120
Length:   9; Size in bytes:  184
Length:  10; Size in bytes:  184
Length:  11; Size in bytes:  184
Length:  12; Size in bytes:  184
Length:  13; Size in bytes:  184
Length:  14; Size in bytes:  184
Length:  15; Size in bytes:  184
Length:  16; Size in bytes:  184
Length:  17; Size in bytes:  256
Length:  18; Size in bytes:  256
Length:  19; Size in bytes:  256
Length:  20; Size in bytes:  256

可以看出随着数组长度的增加，其占据的内存空间不是成比例而是分段地进行扩展的。

动态数组的 Python 实现

import ctypes


class DynamicArray:
    def __init__(self):
        self._n = 0
        self._capacity = 1
        self._A = self._make_array(self._capacity)

    def __len__(self):
        return self._n

    def __getitem__(self, k):
        if not 0 <= k < self._n:
            raise IndexError('invalid index')
        return self._A[k]

    def append(self, obj):
        if self._n == self._capacity:
            self._resize(2 * self._capacity)
        self._A[self._n] = obj
        self._n += 1

    def _resize(self, c):
        B = self._make_array(c)
        for k in range(self._n):
            B[k] = self._A[k]
        self._A = B
        self._capacity = c

    def _make_array(self, c):
        return (c * ctypes.py_object)()

    def insert(self, k, value):
        if self._n == self._capacity:
            self._resize(2 * self._capacity)
        for j in range(self._n, k, -1):
            self._A[j] = self._A[j - 1]
        self._A[k] = value
        self._n += 1

    def remove(self, value):
        for k in range(self._n):
            if self._A[k] == value:
                for j in range(k, self._n - 1):
                    self._A[j] = self._A[j + 1]
                self._A[self._n - 1] = None
                self._n -= 1
                return
        raise ValueError('value not found')

Python 中 List 的性能

操作	时间
len(data)	O(1)
data[j]	O(1)
data.count(value)	O(n)
data.index(value)	O(k + 1)，k 指从左起 value 第一次出现的位置
value in data	O(k + 1)，k 指从左起 value 第一次出现的位置
data1 == data2	O(k + 1)，此处 k 指从左起第一次出现不同元素的位置
data[j:k]	O(k - j + 1)，j 和 k 指分片的起止位置
data1 + data2	O(n1 + n2)
c * data	O(cn)
data[j] = val	O(1)
data.append(value)	O(1)
data.insert(k, value)	O(n - k + 1)
data.pop()	O(1)
data.pop(k)	O(n - k)
data1 += data2	O(n2)
data.reverse()	O(n)
data.sort()	O(nlogn)

参考资料

Data Structures and Algorithms in Python