Python 中常见的数据结构：数组数据结构

大多数编程语言中都有数组这种基本数据结构，它在许多算法中都有广泛的运用。

本文将介绍 Python 中的一些数组实现，这些数组只用到了语言的核心特性或 Python 标准库包含的功能。同时，还会介绍每种实现的优缺点，这样就能根据实际情况选择合适的实现。不过在介绍之前，先来了解一些基础知识。

首先要知道数组的原理及用途。

数组由大小固定的数据记录组成，根据索引能快速找到其中的每个元素。

因为数组将信息存储在依次连接的内存块中，所以它是连续的数据结构（与链式列表等链式数据结构不同）。

现实世界中能用来类比数组数据结构的是停车场。

停车场可被视为一个整体，即单个对象，但停车场内的每个停车位都有唯一的编号索引。停车位是车辆的容器，每个停车位既可以为空，也可以停有汽车、摩托车或其他车辆。

各个停车场之间也会有区别。

有些停车场可能只能停一种类型的车辆。例如，汽车停车场不允许停放自行车。这种“有限制”的停车场相当于“类型数组”数据结构，只允许存储相同数据类型的元素。

在性能方面，根据元素的索引能快速查找数组中对应的元素。合理的数组实现能够确保索引访问的耗时为常量时间 O(1)。

Python 标准库包含几个与数组相似的数据结构，每个数据结构的特征略有不同。下面来逐一介绍。

列表——可变动态数组

列表是 Python 语言核心的一部分。10 虽然名字叫列表，但它实际上是以动态数组实现的。这意味着列表能够添加或删除元素，还能分配或释放内存来自动调整存储空间。

Python 列表可以包含任意元素，因为 Python 中一切皆为对象，连函数也是对象。因此，不同的数据类型可以混合存储在一个列表中。

这个功能很强大，但缺点是同时支持多种数据类型会导致数据存储得不是很紧凑。因此整个结构占据了更多的空间。

本质上是因为列表中存储的是 PyObject 指针，指向不同的对象。然而数组是直接存放数据本身。后面类似内容不再提醒，还请读者注意。——译者注

>>> arr = ['one', 'two', 'three']>>> arr[0]'one'
# 列表拥有不错的__repr__方法：>>> arr['one', 'two', 'three']
# 列表是可变的：>>> arr[1] = 'hello'>>> arr['one', 'hello', 'three']
>>> del arr[1]>>> arr['one', 'three']
# 列表可以含有任意类型的数据：>>> arr.append(23)>>> arr['one', 'three', 23]

元组——不可变容器

与列表一样，元组也是 Python 语言核心的一部分。与 s 列表不同的是，Python 的元组对象是不可变的。这意味着不能动态添加或删除元素，元组中的所有元素都必须在创建时定义。

就像列表一样，元组可以包含任意数据类型的元素。这具有很强的灵活性，但也意味着数据的打包密度要比固定类型的数组小。

>>> arr = 'one', 'two', 'three'>>> arr[0]'one'
# 元组拥有不错的__repr__方法：>>> arr('one', 'two', 'three')
# 元组是可变的>>> arr[1] = 'hello'TypeError:"'tuple' object does not support item assignment"
>>> del arr[1]TypeError:"'tuple' object doesn't support item deletion"
# 元组可以持有任意类型的数据：#（添加元素会创建新元组）>>> arr + (23,)('one', 'two', 'three', 23)

array.array——基本类型数组

Python 的 array 模块占用的空间较少，用于存储 C 语言风格的基本数据类型（如字节、32 位整数，以及浮点数等）。

使用 array.array 类创建的数组是可变的，行为与列表类似。但有一个重要的区别：这种数组是单一数据类型的“类型数组”。

由于这个限制，含有多个元素的 array.array 对象比列表和元组节省空间。存储在其中的元素紧密排列，因此适合存储许多相同类型的元素。

此外，数组中有许多普通列表中也含有的方法，使用方式也相同，无须对应用程序代码进行其他更改。

>>> import array>>> arr = array.array('f', (1.0, 1.5, 2.0, 2.5))>>> arr[1]1.5
# 数组拥有不错的__repr__方法：>>> arrarray('f', [1.0, 1.5, 2.0, 2.5])
# 数组是可变的：>>> arr[1] = 23.0>>> arrarray('f', [1.0, 23.0, 2.0, 2.5])
>>> del arr[1]>>> arrarray('f', [1.0, 2.0, 2.5])
>>> arr.append(42.0)>>> arrarray('f', [1.0, 2.0, 2.5, 42.0])
# 数组中元素类型是固定的：>>> arr[1] = 'hello'TypeError: "must be real number, not str"

str——含有 Unicode 字符的不可变数组

{\rm Python}~3.x 使用 str 对象将文本数据存储为不可变的 Unicode 字符序列。实际上，这意味着 str 是不可变的字符数组。说来也怪，str 也是一种递归的数据结构，字符串中的每个字符都是长度为 1 的 str 对象。

由于字符串对象专注于单一数据类型，元组排列紧密，因此很节省空间，适合用来存储 Unicode 文本。因为字符串在 Python 中是不可变的，所以修改字符串需要创建一个改动副本。最接近“可变字符串”概念的是存储单个字符的列表。

>>> arr = 'abcd'>>> arr[1]'b'
>>> arr'abcd'
# 字符串是可变的：>>> arr[1] = 'e'TypeError: "'str' object does not support item assignment"
>>> del arr[1]TypeError:"'str' object doesn't support item deletion"
# 字符串可以解包到列表中，从而得到可变版本：>>> list('abcd')['a', 'b', 'c', 'd']>>> ''.join(list('abcd'))'abcd'
# 字符串是递归型数据类型：>>> type('abc')"<class 'str'>">>> type('abc'[0])"<class 'str'>"

bytes——含有单字节的不可变数组

bytes 对象是单字节的不可变序列，单字节为 0～255（含）范围内的整数。从概念上讲，bytes 与 str 对象类似，可认为是不可变的字节数组。

与字符串一样，也有专门用于创建 bytes 对象的字面语法，bytes 也很节省空间。bytes 对象是不可变的，但与字符串不同，还有一个名为 bytearray 的专用“可变字节数组”数据类型，bytes 可以解包到 bytearray 中。下一节将介绍更多关于 bytearray 的内容。

>>> arr = bytes((0, 1, 2, 3))>>> arr[1]1
# bytes 有自己的语法：>>> arrb'\x00\x01\x02\x03'>>> arr = b'\x00\x01\x02\x03'
# bytes 必须位于0～255：>>> bytes((0, 300))ValueError: "bytes must be in range(0, 256)"
# bytes 是不可变的：>>> arr[1] = 23TypeError:"'bytes' object does not support item assignment"
>>> del arr[1]TypeError:"'bytes' object doesn't support item deletion"

bytearray——含有单字节的可变数组

bytearray 类型是可变整数序列 16，包含的整数范围在 0～255（含）。bytearray 与 bytes 对象关系密切，主要区别在于 bytearray 可以自由修改，如覆盖、删除现有元素和添加新元素，此时 bytearray 对象将相应地增长和缩小。

bytearray 数可以转换回不可变的 bytes 对象，但是这需要复制所存储的数据，是耗时为 O(n)的慢操作。

>>> arr = bytearray((0, 1, 2, 3))>>> arr[1]1
# bytearray 的repr：>>> arrbytearray(b'\x00\x01\x02\x03')
# bytearray 是可变的：>>> arr[1] = 23>>> arrbytearray(b'\x00\x17\x02\x03')
>>> arr[1]23
# bytearray 可以增长或缩小：>>> del arr[1]>>> arrbytearray(b'\x00\x02\x03')
>>> arr.append(42)>>> arrbytearray(b'\x00\x02\x03*')
# bytearray 只能持有byte，即位于0～255 范围内的整数>>> arr[1] = 'hello'TypeError: "an integer is required"
>>> arr[1] = 300ValueError: "byte must be in range(0, 256)"
# bytearray 可以转换回byte 对象，此过程会复制数据：>>> bytes(arr)b'\x00\x02\x03*'

小结

Python 中有多种内置数据结构可用来实现数组，本节只专注位于标准库中和核心语言特性中的数据结构。

如果不想局限于 Python 标准库，那么从 NumPy 这样的第三方软件包中可找到为科学计算和数据科学提供的许多快速数组实现。

对于 Python 中包含的数组数据结构，选择顺序可归结如下。

如果需要存储任意对象，且其中可能含有混合数据类型，那么可以选择使用列表或元组，前者可变后者不可变。

如果存储数值（整数或浮点数）数据并要求排列紧密且注重性能，那么先尝试 array.array，看能否满足要求。另外可尝试准库之外的软件包，如 NumPy 或 Pandas。

如果有需要用 Unicode 字符表示的文本数据，那么可以使用 Python 内置的 str。如果需要用到“可变字符串”，则请使用字符列表。

如果想存储一个连续的字节块，不可变的请使用 bytes，可变的请使用 bytearray。

总之，在大多数情况下首先应尝试列表。如果在性能或存储空间上有问题，再选择其他专门的数据类型。一般像列表这样通用的数组型数据结构已经能同时兼顾开发速度和编程便利性的要求了。

强烈建议在初期使用通用数据格式，不要试图在一开始就榨干所有性能。

本文内容来自作者图书作品《深入理解 Python 特性》，点击购买。