漫谈 Python 中的数据结构 (1) 数组

应用程序可以看做算法和数据结构的组合，从中不难看出数据结构对于应用程序开发是多么重要。而且数据结构和算法是超脱语言独立存在的，是相对比较抽象的东西。只有熟悉数据结构，了解每种数据结构所擅长表达的领域，才能够将数据结构用的得心应手，恰当地选择合适的数据结构来表示事物，才会让你的程序更加流畅，丝滑。

每种语言根据其擅长的领域提供不同类型的数据结构，那么 python 活跃在多个领域，支持范式也多种多样，那么这样一个多面手，看一看 python 都提供那些比较核心的复合数据类型呢。接下来准备用几个篇幅来细细地聊一聊 python 这门语言对数据结构的支持，希望通过分享，让大家对 python 中数据结构一定了解，在以后开发中可以根据实际情况选择合适的数据类型。

数组数据结构

大多数语言中都提供了数组这样数据结构，而且很多算法都是基于数组的，从而说明数组在开发用中的重要性。接下来我们就来看一看 Python 中是如何实现数组的。关于数组的实现，我们只会使用到 python 的核心特性或 Python 标准库中提供的功能。接下除了会给出数组的具体实现，还会聊一聊每种方法的优点和缺点，便于你在项目中，选择合适方式来实现数组。

为了便于更好理解数组这种数据结构，我们可以将数组想象为停车场，可以把停车场看成一个整体。每一个停车位都有一个索引(数值)来标识，每一个索引都是唯一的。

停车位是车辆的容器，每个停车位既可以是空的，也可以有汽车、摩托车或其他类型的车辆。但并不是所有的停车场都是一样的。有些停车场可能只限制一种类型的车辆。例如，摩托车停车场就不允许停放自行车。划分车位只适合放置同一类型的车辆。

arr = ["a","b","c"]

由于数组通常是存储在连续的内存中，这一点与链表有所不同,列表是在内存中可以是分散零散地存储。

从性能上来看，如果已知某一个元素的索引，在数组通过索引来进行查找是非常快，这时时间复杂度为 O(1)O(1)O(1) 。

在 Python 语言中，标准库中提供了几个类似数组的数据结构，这些数据结构之间都略有差异，让我们来看看

List: 可变的动态数组

list 是 Python 核心语言的一部分, 虽然 list 可以理解为列表，但在 Python 的 list 背后的实现就是一个动态数组。

那么作为动态列表，可以为其添加或删除元素，列表将通过分配或释放内存来自动地调整其所有占用内存的大小。

Python 中的 list 可以容纳任意多个的元素，所有的元素都是一个对象，包括函数。在 list 中可以不同类型的数据作为元素。

func = lambda x:x + 1
mixed_arr = [None,func,True,1,"hello world"]

为 list 添加元素

arr.append("hello")
arr.append("world")
print(arr) #['a', 'b', 'c', 'hello', 'world']

从 list 中删除元素

del arr[-1]
del arr[3]
print(arr)#['a', 'b', 'c']

从一个方面来看这可能是 list 的一个强大的功能，同时也是 list 缺点，因为需要支持对各种类型支持，势必需要额外做一些工作，而且通常这样存储设备不会那么紧密，而且会占用更多的空间。

tuple: 不可变的容器

和 list 一样，tuple 也是 Python 核心语言的一部分。然而与 list 不同支持， tuple 对象是不可变的。这意味着 tuple 一旦创建后，tuple 中的元素进行添加或删除。

tuple 也是可以容纳任意数据类型的元素的数据结构，在这点和 list 类似，灵活性的付出就是在内存中排列也没有那么紧密。

arr_tuple = ("a","b","c")

arr_tuple[0] = "hello"

就会抛出 TypeError: 'tuple' object does not support item assignment 这样异常

arr_tuple + (12,)

这样创建了一个新的 tuple 而不是在原理基础修改了 tuple

array.array: 基本类型的数组

Python 的数组模块为基本的 C 语言的数组，元素支持 C 语言的基本类型，如字节、32 位整数、浮点数等，提供了空间效率的存储。

用 array.array 类创建的数组是可变的，其行为类似于 list，不过还是存在一定的的区别：array.array 是类型化的数组，array.array 需要其中元素都是同一类型。因此 array.array 相对于 list 更有效地利用了内存空间。

另外，数组支持许多与 list 相同的方法，下面通过太多。

arr = array.array("f",(1.0,1.5,2.0))
print(arr[1])#1.5

print(arr) #array('f', [1.0, 1.5, 2.0])

del arr[1]
print(arr)#array('f', [1.0, 2.0])
arr.append(2.5)
print(arr)#array('f', [1.0, 2.0, 2.5])
arr[1] = "hello"#TypeError: must be real number, not str

str: 不可变的 Unicode 字符数组

Python 3.x 使用 str 对象来存储文本数据，其实 str 可以看作一个不可变的 Unicode 字符的序列。字符串中的每个字符本身就是一个长度为 1 的 str 对象。

字符串对象的空间效率很高，因为保存类型都是字符，所以在内存中 str 也是紧密排列的，如果你要存储 Unicode 字符，那么就应该选择 str 作为容器。

str 在 Python 中是不可变的，修改一个 str 需要创建一个修改过的副本。与可变 str 最相似的是在一个列表中存储单个字符。

arr = "abc"
print(arr[1]) #b

arr[1] = 'd'#TypeError: 'str' object does not support item assignment

del arr[1] #TypeError: 'str' object doesn't support item deletion

print(list("abc")) #['a', 'b', 'c']

print("".join(list("abc"))) "abc"

print(type("abc"))#<class 'str'>
print(type("abc"[0]))#<class 'str'>

bytes: 单个字节的不可改变的数组

bytes 对象是不可改变的单字节序列，表示范围为 0≤x≤2550 \le x \le 2550≤x≤255 的整数。从概念上讲，字节对象类似于str 对象，也可以把看成是不可变的字节数组。

和字符串一样，字节也有可以通过字面语法来创建对象，因此存储节省空间。字节对象是不可变的，但是和字符串不同的是，提供了有一个专门的可变的字节数组数据类型 bytearray

b = bytes(b'ABCD')
print(b)#b'ABCD'

bytes(src,enc,error)

• src 表示要转换为字节的源对象
• enc 字符串编码方式
• error 指定处理任意错误方式

b + u'EFGH' #TypeError: can't concat str to bytes

a = bytes('hello world','utf8')
print(a)

ValueError: bytes must be in range(0, 256)

arr_1 = bytes((0,1,2,3))
print(arr_1)

print(arr_1[1])


# arr_1 = bytes((1,300))
arr_1[1] = 2
del arr_1[1]

bytearray: 可变的单字节数组

bytearray 类型表示能力也是 0≤x≤2550 \le x \le 2550≤x≤255 的整数的可变序列。bytearray 对象与 bytes 非常相似，主要区别在于 bytearray 可以自由地修改元素、删除现有元素或添加新元素。bytearray 长度也是可变的。

bytearray 可以转换为不可改变的 bytes 对象，完整地复制存储的数据所以耗时的操作，其时间复杂度为 O(n)O(n)O(n) 。

arr = bytearray((0,1,2,3,5,7,8))
print(arr[1])#1

arr[1] = 12
print(arr)#bytearray(b'\x00\x0c\x02\x03\x05\x07\x08')

del arr[1]
print(arr)#bytearray(b'\x00\x02\x03\x05\x07\x08')

arr.append(3)
print(arr)#bytearray(b'\x00\x02\x03\x05\x07\x08\x03'

在开始之前，让我们先补习一些基础知识。看一看数组是如何工作的，以及数组用途是什么？那么我们希望数组和列表是有所区别，区别在于我们希望数组中元素大小是固定，也就是数组具有相同类型，然后可以通过索引来访问特定的元素。

• 如果需要存储的对象是不确定的，可能是包含多种数据类型的数据，那么这样就可以选择 list 或 tuple，到底选择是 list 还是 tuple，取决于希望是不可变的数据结构还是不可变的数据结构，则可以选择 tuple 否则可以考虑 list

• 如果更多关心是性能，而且元素类型为整数或浮点数据，那么可以试一试array.array

• 如果数据为 Unicode 字符表示的文本数据，那么就可以使用 Python 内置的 str 做数组来保存数据，不过 str 是不可变的类型，需要一个类似字符串的可变数据结构，那么就可以考虑字符的 list 来作为数组使用

• 如果想存储一个连续的字节，那么使用不可变的 bytes 类型，如果你需要一个可变的数据结构，则使用bytearray

在大多数情况下，我喜欢从一个简单的 list 来开始介绍数组。只有当性能或存储空间成为一个问题时，才会在以后进一步考虑。大多数时候，使用像 list 这样的常见数据结构来模拟数组数据结构，因为 list 是大家比较熟悉的数据结构，便于大家上手实现一个简单数组，然后再去一步一步深入考虑如何将提升代码的性能。

后续我们会引入 Numpy 看一看这个 python 中，如果要接触数据处理或者数学方面，不可不学的库。其实 python 在学术领域，这么受欢迎，是因为 python 有像 numpy 这样的库。

参考

Common Python Data Structures (Guide)