Python 数组数据结构

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

本节将介绍Python中的一些数组实现，这些数组只用到了语言的核心特性或Python标准库包含的功能。

不过在介绍之前，先来了解一些基础知识。

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

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

因为数组将信息存储在依次连接的内存块中，所以它是连续的数据结构（与链式列表等链式数据结构不同）。
现实世界中能用来类比数组数据结构的是停车场。

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

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

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

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

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

Python 数组数据结构 列表——可变动态数组

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

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

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

>>> 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 数组数据结构 元组——不可变容器

与列表一样，元组也是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)

Python 数组数据结构 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__方法：
>>> arr
array('f', [1.0, 1.5, 2.0, 2.5])

# 数组是可变的：
>>> arr[1] = 23.0
>>> arr
array('f', [1.0, 23.0, 2.0, 2.5])

>>> del arr[1]
>>> arr
array('f', [1.0, 2.0, 2.5])

>>> arr.append(42.0)
>>> arr
array('f', [1.0, 2.0, 2.5, 42.0])

# 数组中元素类型是固定的：
>>> arr[1] = 'hello'
TypeError: "must be real number, not str"

Python 数组数据结构 str——含有Unicode字符的不可变数组

使用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'>"

Python 数组数据结构 bytes——含有单字节的不可变数组

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

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

>>> arr = bytes((0, 1, 2, 3))
>>> arr[1]
1

# bytes 有自己的语法：
>>> arr
b'\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] = 23
TypeError:
"'bytes' object does not support item assignment"

>>> del arr[1]
TypeError:
"'bytes' object doesn't support item deletion"

Python 数组数据结构 bytearray——含有单字节的可变数组

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

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

>>> arr = bytearray((0, 1, 2, 3))
>>> arr[1]
1

# bytearray 的repr：
>>> arr
bytearray(b'\x00\x01\x02\x03')

# bytearray 是可变的：
>>> arr[1] = 23
>>> arr
bytearray(b'\x00\x17\x02\x03')

>>> arr[1]
23

# bytearray 可以增长或缩小：
>>> del arr[1]
>>> arr
bytearray(b'\x00\x02\x03')

>>> arr.append(42)
>>> arr
bytearray(b'\x00\x02\x03*')

# bytearray 只能持有byte，即位于0～255 范围内的整数
>>> arr[1] = 'hello'
TypeError: "an integer is required"

>>> arr[1] = 300
ValueError: "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。
总之，在大多数情况下首先应尝试列表。如果在性能或存储空间上有问题，再选择其他专门的数据类型。一般像列表这样通用的数组型数据结构已经能同时兼顾开发速度和编程便利性的要求了。
强烈建议在初期使用通用数据格式，不要试图在一开始就榨干所有性能。