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

本文正在参加「金石方案 . 瓜分6万现金大奖」

应用程序能够看做算法和数据结构的组合，从中不难看出数据结构对于应用程序开发是多么重要。并且数据结构和算法是超逸言语独立存在的，是相对比较抽象的东西。只要熟悉数据结构，了解每种数据结构所拿手表达的范畴，才能够将数据结构用的得心应手，恰当地挑选合适的数据结构来表明事物，才会让你的程序愈加流通，丝滑。

每种言语根据其拿手的范畴供给不同类型的数据结构，那么 python 活跃在多个范畴，支撑范式也多种多样，那么这样一个多面手，看一看 python 都供给那些比较中心的复合数据类型呢。接下来准备用几个篇幅来细细地聊一聊 python 这门言语对数据结构的支撑，期望经过共享，让咱们对 python 中数据结构必定了解，在今后开发中能够根据实际情况挑选合适的数据类型。

数组数据结构

大多数言语中都供给了数组这样数据结构，并且很多算法都是根据数组的，然后阐明数组在开发用中的重要性。接下来咱们就来看一看 Python 中是怎么完成数组的。关于数组的完成，咱们只会运用到 python 的中心特性或 Python 标准库中供给的功能。接下除了会给出数组的具体完成，还会聊一聊每种办法的优点和缺陷，便于你在项目中，挑选合适方法来完成数组。

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

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

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

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

从功能上来看，假如已知某一个元素的索引，在数组经过索引来进行查找是十分快，这时时刻复杂度为 $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\le x\le 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\le x\le 255$ 的整数的可变序列。bytearray 目标与 bytes 十分相似，主要区别在于 bytearray 能够自由地修改元素、删去现有元素或增加新元素。bytearray 长度也是可变的。

bytearray 能够转换为不行改动的 bytes 目标，完整地复制存储的数据所以耗时的操作，其时刻复杂度为 $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)