Python 提供了许多内置的数据集合类型如果选择明智的话可以高效解决许多问题。你可能已经学过下面这些集合类型它们都有专门的字面值如下所示。• 列表list。• 元组tuple。• 字典dictionary。• 集合setPython 的集合类型当然不止这 4 种它的标准库扩展了其可选列表。在许多情况下问题的答案可能正如选择正确的数据结构一样简单。本书的这一部分将深入介绍各种集合类型以帮你做出更好的选择。列表与元组Python 最基本的两个集合类型就是列表与元组它们都表示对象序列。只要是花几小时学过 Python 的人应该都很容易发现二者之间的根本区别列表是动态的其大小可以改变而元组是不可变的一旦创建就不能修改。虽然快速分配/释放小型对象的优化方法有很多但对于元素位置本身也是信息的数据结构来说推荐使用元组这一数据类型。举个例子想要保存(x, y)坐标对元组可能是一个很好的选择。反正关于元组的细节相当无趣。本章关于元组唯一重要的内容就是tuple是不可变的immutable因此也是可哈希的hashable。其具体含义将会在后面“字典”一节介绍。比元组更有趣的是另一种动态的数据结构 list以及它的工作原理和高效处理理方式。实现细节许多程序员容易将 Python 的 list 类型与其他语言如 C、C或 Java标准库中常见的链表的概念相混淆。事实上CPython 的列表根本不是列表。在 CPython 中列表被实现为长度可变的数组。对于其他 Python 实现如 Jython 和 IronPython而言这种说法应该也是正确的虽然这些项目的文档中没有记录其实现细节。造成这种混淆的原因很清楚。这种数据类型被命名为列表还和链表实现有相似的接口。为什么这一点很重要这又意味着什么呢列表是最常见的数据结构之一其使用方式会对所有应用的性能带来极大影响。此外CPython 又是最常见也最常用的 Python 实现所以了解其内部实现细节至关重要。从细节上来看Python 中的列表是由对其他对象的引用组成的的连续数组。指向这个数组的指针及其长度被保存在一个列表头结构中。这意味着每次添加或删除一个元素时由引用组成的数组需要改变大小重新分配。幸运的是Python 在创建这些数组时采用了指数过分配exponential over-allocation所以并不是每次操作都需要改变数组大小。这也是添加或取出元素的平摊复杂度较低的原因。不幸的是在普通链表中“代价很小”的其他一些操作在 Python 中的计算复杂度却相对较高• 利用 list.insert 方法在任意位置插入一个元素 — 复杂度为 O(n)。• 利用 list.delete 或 del 删除一个元素 — 复杂度为 O(n)。这里 n 是列表的长度。至少利用索引来查找或修改元素的时间开销与列表大小无关。表 2-1 是一张完整的表格列出了大多数列表操作的平均时间复杂度。表 2-1操作 复杂度复制 O(n)添加元素 O(1)插入元素 O(n)获取元素 O(1)修改元素 O(1)删除元素 O(n)遍历 O(n)获取长度为 k 的切片 O(k)删除切片 O(n)操作 复杂度修改长度为 k 的切片 O(kn)列表扩展Extend O(k)乘以 k O(nk)测试元素是否在列表中element in list O(n)min()/max() O(n)获取列表长度 O(1)对于需要真正的链表或者简单来说双端 append 和 pop 操作的复杂度都是 O(1)的数据结构的场景Python 在内置的 collections 模块中提供了 deque双端队列。它是栈和队列的一般化在需要用到双向链表的地方都可以使用这种数据结构。列表推导你可能知道编写这样的代码是很痛苦的evens []for i in range(10):… if i % 2 0:… evens.append(i)…evens[0, 2, 4, 6, 8]这种写法可能适用于 C 语言但在 Python 中的实际运行速度很慢原因如下。• 解释器在每次循环中都需要判断序列中的哪一部分需要修改。• 需要用一个计数器来跟踪需要处理的元素。• 由于 append()是一个列表方法所以每次遍历时还需要额外执行一个查询函数。列表推导正是解决这个问题的正确方法。它使用编排好的功能对上述语法的一部分做了自动化处理[i for i in range(10) if i % 2 0][0, 2, 4, 6, 8]这种写法除了更加高效之外也更加简短涉及的语法元素也更少。在大型程序中这意味着更少的错误代码也更容易阅读和理解。其他习语Python 习语的另一个典型例子是使用 enumerate枚举。在循环中使用序列时这个内置函数可以很方便地获取其索引。以下面这段代码为例i 0for element in [‘one’, ‘two’, ‘three’]:… print(i, element)… i 1…0 one1 two2 three它可以替换为下面这段更短的代码for i, element in enumerate([‘one’, ‘two’, ‘three’]):… print(i, element)…0 one1 two2 three如果需要一个一个合并多个列表或任意可迭代对象中的元素那么可以使用内置的 zip()函数。对两个大小相等的可迭代对象进行均匀遍历时这是一种非常常用的模式for item in zip([1, 2, 3], [4, 5, 6]):… print(item)…(1, 4)(2, 5)(3, 6)注意对 zip()函数返回的结果再次调用 zip()可以将其恢复原状for item in zip(*zip([1, 2, 3], [4, 5, 6])):… print(item)…(1, 2, 3)(4, 5, 6)另一个常用的语法元素是序列解包sequence unpacking。这种方法并不限于列表和元组而是适用于任意序列类型甚至包括字符串和字节序列。只要赋值运算符左边的变量数目与序列中的元素数目相等你都可以用这种方法将元素序列解包到另一组变量中first, second, third “foo”, “bar”, 100first‘foo’second‘bar’third100解包还可以利用带星号的表达式获取单个变量中的多个元素只要它的解释没有歧义即可。还可以对嵌套序列进行解包。特别是在遍历由序列构成的复杂数据结构时这种方法非常实用。下面是一些更复杂的解包示例带星号的表达式可以获取序列的剩余部分first, second, *rest 0, 1, 2, 3first0second1rest[2, 3]带星号的表达式可以获取序列的中间部分first, *inner, last 0, 1, 2, 3first0inner[1, 2]last3嵌套解包(a, b), (c, d) (1, 2), (3, 4)a, b, c, d(1, 2, 3, 4)
Python 高手编程系列十二：集合类型
Python 提供了许多内置的数据集合类型如果选择明智的话可以高效解决许多问题。你可能已经学过下面这些集合类型它们都有专门的字面值如下所示。• 列表list。• 元组tuple。• 字典dictionary。• 集合setPython 的集合类型当然不止这 4 种它的标准库扩展了其可选列表。在许多情况下问题的答案可能正如选择正确的数据结构一样简单。本书的这一部分将深入介绍各种集合类型以帮你做出更好的选择。列表与元组Python 最基本的两个集合类型就是列表与元组它们都表示对象序列。只要是花几小时学过 Python 的人应该都很容易发现二者之间的根本区别列表是动态的其大小可以改变而元组是不可变的一旦创建就不能修改。虽然快速分配/释放小型对象的优化方法有很多但对于元素位置本身也是信息的数据结构来说推荐使用元组这一数据类型。举个例子想要保存(x, y)坐标对元组可能是一个很好的选择。反正关于元组的细节相当无趣。本章关于元组唯一重要的内容就是tuple是不可变的immutable因此也是可哈希的hashable。其具体含义将会在后面“字典”一节介绍。比元组更有趣的是另一种动态的数据结构 list以及它的工作原理和高效处理理方式。实现细节许多程序员容易将 Python 的 list 类型与其他语言如 C、C或 Java标准库中常见的链表的概念相混淆。事实上CPython 的列表根本不是列表。在 CPython 中列表被实现为长度可变的数组。对于其他 Python 实现如 Jython 和 IronPython而言这种说法应该也是正确的虽然这些项目的文档中没有记录其实现细节。造成这种混淆的原因很清楚。这种数据类型被命名为列表还和链表实现有相似的接口。为什么这一点很重要这又意味着什么呢列表是最常见的数据结构之一其使用方式会对所有应用的性能带来极大影响。此外CPython 又是最常见也最常用的 Python 实现所以了解其内部实现细节至关重要。从细节上来看Python 中的列表是由对其他对象的引用组成的的连续数组。指向这个数组的指针及其长度被保存在一个列表头结构中。这意味着每次添加或删除一个元素时由引用组成的数组需要改变大小重新分配。幸运的是Python 在创建这些数组时采用了指数过分配exponential over-allocation所以并不是每次操作都需要改变数组大小。这也是添加或取出元素的平摊复杂度较低的原因。不幸的是在普通链表中“代价很小”的其他一些操作在 Python 中的计算复杂度却相对较高• 利用 list.insert 方法在任意位置插入一个元素 — 复杂度为 O(n)。• 利用 list.delete 或 del 删除一个元素 — 复杂度为 O(n)。这里 n 是列表的长度。至少利用索引来查找或修改元素的时间开销与列表大小无关。表 2-1 是一张完整的表格列出了大多数列表操作的平均时间复杂度。表 2-1操作 复杂度复制 O(n)添加元素 O(1)插入元素 O(n)获取元素 O(1)修改元素 O(1)删除元素 O(n)遍历 O(n)获取长度为 k 的切片 O(k)删除切片 O(n)操作 复杂度修改长度为 k 的切片 O(kn)列表扩展Extend O(k)乘以 k O(nk)测试元素是否在列表中element in list O(n)min()/max() O(n)获取列表长度 O(1)对于需要真正的链表或者简单来说双端 append 和 pop 操作的复杂度都是 O(1)的数据结构的场景Python 在内置的 collections 模块中提供了 deque双端队列。它是栈和队列的一般化在需要用到双向链表的地方都可以使用这种数据结构。列表推导你可能知道编写这样的代码是很痛苦的evens []for i in range(10):… if i % 2 0:… evens.append(i)…evens[0, 2, 4, 6, 8]这种写法可能适用于 C 语言但在 Python 中的实际运行速度很慢原因如下。• 解释器在每次循环中都需要判断序列中的哪一部分需要修改。• 需要用一个计数器来跟踪需要处理的元素。• 由于 append()是一个列表方法所以每次遍历时还需要额外执行一个查询函数。列表推导正是解决这个问题的正确方法。它使用编排好的功能对上述语法的一部分做了自动化处理[i for i in range(10) if i % 2 0][0, 2, 4, 6, 8]这种写法除了更加高效之外也更加简短涉及的语法元素也更少。在大型程序中这意味着更少的错误代码也更容易阅读和理解。其他习语Python 习语的另一个典型例子是使用 enumerate枚举。在循环中使用序列时这个内置函数可以很方便地获取其索引。以下面这段代码为例i 0for element in [‘one’, ‘two’, ‘three’]:… print(i, element)… i 1…0 one1 two2 three它可以替换为下面这段更短的代码for i, element in enumerate([‘one’, ‘two’, ‘three’]):… print(i, element)…0 one1 two2 three如果需要一个一个合并多个列表或任意可迭代对象中的元素那么可以使用内置的 zip()函数。对两个大小相等的可迭代对象进行均匀遍历时这是一种非常常用的模式for item in zip([1, 2, 3], [4, 5, 6]):… print(item)…(1, 4)(2, 5)(3, 6)注意对 zip()函数返回的结果再次调用 zip()可以将其恢复原状for item in zip(*zip([1, 2, 3], [4, 5, 6])):… print(item)…(1, 2, 3)(4, 5, 6)另一个常用的语法元素是序列解包sequence unpacking。这种方法并不限于列表和元组而是适用于任意序列类型甚至包括字符串和字节序列。只要赋值运算符左边的变量数目与序列中的元素数目相等你都可以用这种方法将元素序列解包到另一组变量中first, second, third “foo”, “bar”, 100first‘foo’second‘bar’third100解包还可以利用带星号的表达式获取单个变量中的多个元素只要它的解释没有歧义即可。还可以对嵌套序列进行解包。特别是在遍历由序列构成的复杂数据结构时这种方法非常实用。下面是一些更复杂的解包示例带星号的表达式可以获取序列的剩余部分first, second, *rest 0, 1, 2, 3first0second1rest[2, 3]带星号的表达式可以获取序列的中间部分first, *inner, last 0, 1, 2, 3first0inner[1, 2]last3嵌套解包(a, b), (c, d) (1, 2), (3, 4)a, b, c, d(1, 2, 3, 4)
