Data Structures and Algorithms Chapter 1 PDF

第1章 数据结构和算法 Python 内置了许多非常有用的数据结构，比如列表（list）、集合（set）以及字典 （dictionary）。就绝大部分情况而言，我们可以直接使用这些数据结构。但是，通常我 们还需要考虑比如搜索、...

第1章 数据结构和算法 Python 内置了许多非常有用的数据结构，比如列表（list）、集合（set）以及字典 （dictionary）。就绝大部分情况而言，我们可以直接使用这些数据结构。但是，通常我 们还需要考虑比如搜索、排序、排列以及筛选等这一类常见的问题。因此，本章的目 的就是来讨论常见的数据结构和同数据有关的算法。此外，在 collections 模块中也包含 了针对各种数据结构的解决方案。 1.1 将序列分解为单独的变量 1.1.1 问题 我们有一个包含 N 个元素的元组或序列，现在想将它分解为 N 个单独的变量。 1.1.2 解决方案 任何序列（或可迭代的对象）都可以通过一个简单的赋值操作来分解为单独的变量。 唯一的要求是变量的总数和结构要与序列相吻合。例如： >>> p = (4, 5) >>> x, y = p >>> x 4 >>> y 5 >>> >>> data = [ 'ACME', 50, 91.1, (2012, 12, 21) ] >>> name, shares, price, date = data >>> name 国国 1  'ACME' >>> date (2012, 12, 21) >>> name, shares, price, (year, mon, day) = data >>> name 'ACME' >>> year 2012 >>> mon 12 >>> day 21 >>> 如果元素的数量不匹配，将得到一个错误提示。例如： >>> p = (4, 5) >>> x, y, z = p Traceback (most recent call last): File "", line 1, in ValueError: need more than 2 values to unpack >>> 1.1.3 讨论 实际上不仅仅只是元组或列表，只要对象恰好是可迭代的，那么就可以执行分解操作。 这包括字符串、文件、迭代器以及生成器。比如： >>> s = 'Hello' >>> a, b, c, d, e = s >>> a 'H' >>> b 'e' >>> e 'o' >>> 当做分解操作时，有时候可能想丢弃某些特定的值。Python 并没有提供特殊的语法来 实现这一点，但是通常可以选一个用不到的变量名，以此来作为要丢弃的值的名称。 例如： >>> data = [ 'ACME', 50, 91.1, (2012, 12, 21) ] >>> _, shares, price, _ = data >>> shares 2 第1章  50 >>> price 91.1 >>> 但是请确保选择的变量名没有在其他地方用到过。 1.2 从任意长度的可迭代对象中分解元素 1.2.1 问题 需要从某个可迭代对象中分解出 N 个元素，但是这个可迭代对象的长度可能超过 N， 这会导致出现“分解的值过多（too many values to unpack）”的异常。 1.2.2 解决方案 Python 的“*表达式”可以用来解决这个问题。例如，假设开设了一门课程，并决定在 期末的作业成绩中去掉第一个和最后一个，只对中间剩下的成绩做平均分统计。如果 只有 4 个成绩，也许可以简单地将 4 个都分解出来，但是如果有 24 个呢？*表达式使 这一切都变得简单： def drop_first_last(grades): first, *middle, last = grades return avg(middle) 另一个用例是假设有一些用户记录，记录由姓名和电子邮件地址组成，后面跟着任意 数量的电话号码。则可以像这样分解记录： >>> record = ('Dave', '[email protected]', '773-555-1212', '847-555-1212') >>> name, email, *phone_numbers = user_record >>> name 'Dave' >>> email '[email protected]' >>> phone_numbers ['773-555-1212', '847-555-1212'] >>> 不管需要分解出多少个电话号码（甚至没有电话号码），变量 phone_numbers 都一直是 列表，而这是毫无意义的。如此一来，对于任何用到了变量 phone_numbers 的代码都不 必对它可能不是一个列表的情况负责，或者额外做任何形式的类型检查。 由*修饰的变量也可以位于列表的第一个位置。例如，比方说用一系列的值来代表公司 过去 8 个季度的销售额。如果想对最近一个季度的销售额同前 7 个季度的平均值做比 数据结构和算法 3 较，可以这么做： *trailing_qtrs, current_qtr = sales_record trailing_avg = sum(trailing_qtrs) / len(trailing_qtrs) return avg_comparison(trailing_avg, current_qtr) 从 Python 解释器的角度来看，这个操作是这样的： >>> *trailing, current = [10, 8, 7, 1, 9, 5, 10, 3] >>> trailing [10, 8, 7, 1, 9, 5, 10] >>> current 3 1.2.3 讨论 对于分解未知或任意长度的可迭代对象，这种扩展的分解操作可谓是量身定做的工具。 通常，这类可迭代对象中会有一些已知的组件或模式（例如，元素 1 之后的所有内容 都是电话号码），利用*表达式分解可迭代对象使得开发者能够轻松利用这些模式，而 不必在可迭代对象中做复杂花哨的操作才能得到相关的元素。 *式的语法在迭代一个变长的元组序列时尤其有用。例如，假设有一个带标记的元组序列： records = [ ('foo', 1, 2), ('bar', 'hello'), ('foo', 3, 4), ] def do_foo(x, y): print('foo', x, y) def do_bar(s): print('bar', s) for tag, *args in records: if tag == 'foo': do_foo(*args) elif tag == 'bar': do_bar(*args) 当和某些特定的字符串处理操作相结合，比如做拆分（splitting）操作时，这种*式的语 法所支持的分解操作也非常有用。例如： >>> line = 'nobody:*:-2:-2:Unprivileged User:/var/empty:/usr/bin/false' >>> uname, *fields, homedir, sh = line.split(':') >>> uname 'nobody' >>> homedir 4 第1章  '/var/empty' >>> sh '/usr/bin/false' >>> 有时候可能想分解出某些值然后丢弃它们。在分解的时候，不能只是指定一个单独的*， 但是可以使用几个常用来表示待丢弃值的变量名，比如_或者 ign（ignored） 。例如： >>> record = ('ACME', 50, 123.45, (12, 18, 2012)) >>> name, *_, (*_, year) = record >>> name 'ACME' >>> year 2012 >>> *分解操作和各种函数式语言中的列表处理功能有着一定的相似性。例如，如果有一个 列表，可以像下面这样轻松将其分解为头部和尾部： >>> items = [1, 10, 7, 4, 5, 9] >>> head, *tail = items >>> head 1 >>> tail [10, 7, 4, 5, 9] >>> 在编写执行这类拆分功能的函数时，人们可以假设这是为了实现某种精巧的递归算法。例如： >>> def sum(items):... head, *tail = items... return head + sum(tail) if tail else head... >>> sum(items) 36 >>> 但是请注意，递归真的不算是 Python 的强项，这是因为其内在的递归限制所致。因此， 最后一个例子在实践中没太大的意义，只不过是一点学术上的好奇罢了。 1.3 保存最后 N 个元素 1.3.1 问题 我们希望在迭代或是其他形式的处理过程中对最后几项记录做一个有限的历史记 数据结构和算法 5 录统计。 1.3.2 解决方案 保存有限的历史记录可算是 collections.deque 的完美应用场景了。例如，下面的代码对 一系列文本行做简单的文本匹配操作，当发现有匹配时就输出当前的匹配行以及最后 检查过的 N 行文本。 from collections import deque def search(lines, pattern, history=5): previous_lines = deque(maxlen=history) for line in lines: if pattern in line: yield line, previous_lines previous_lines.append(line) # Example use on a file if __name__ == '__main__': with open('somefile.txt') as f: for line, prevlines in search(f, 'python', 5): for pline in prevlines: print(pline, end='') print(line, end='') print('-'*20) 1.3.3 讨论 如同上面的代码片段中所做的一样，当编写搜索某项记录的代码时，通常会用到含有 yield 关键字的生成器函数。这将处理搜索过程的代码和使用搜索结果的代码成功解耦 开来。如果对生成器还不熟悉，请参见 4.3 节。 deque(maxlen=N)创建了一个固定长度的队列。当有新记录加入而队列已满时会自动移 除最老的那条记录。例如： >>> q = deque(maxlen=3) >>> q.append(1) >>> q.append(2) >>> q.append(3) >>> q deque([1, 2, 3], maxlen=3) >>> q.append(4) >>> q deque([2, 3, 4], maxlen=3) >>> q.append(5) >>> q deque([3, 4, 5], maxlen=3) 6 第1章 尽管可以在列表上手动完成这样的操作（append、del） ，但队列这种解决方案要优雅得 多，运行速度也快得多。 更普遍的是，当需要一个简单的队列结构时，deque 可祝你一臂之力。如果不指定队列 的大小，也就得到了一个无界限的队列，可以在两端执行添加和弹出操作，例如： >>> q = deque() >>> q.append(1) >>> q.append(2) >>> q.append(3) >>> q deque([1, 2, 3]) >>> q.appendleft(4) >>> q deque([4, 1, 2, 3]) >>> q.pop() 3 >>> q deque([4, 1, 2]) >>> q.popleft() 4 从队列两端添加或弹出元素的复杂度都是 O(1)。这和列表不同，当从列表的头部插入 或移除元素时，列表的复杂度为 O(N)。 1.4 找到最大或最小的 N 个元素 1.4.1 问题 我们想在某个集合中找出最大或最小的 N 个元素。 1.4.2 解决方案 heapq 模块中有两个函数—nlargest()和 nsmallest()—它们正是我们所需要的。例如： import heapq nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2] print(heapq.nlargest(3, nums)) # Prints [42, 37, 23] print(heapq.nsmallest(3, nums)) # Prints [-4, 1, 2] 这两个函数都可以接受一个参数 key，从而允许它们工作在更加复杂的数据结构之上。例如： portfolio = [ {'name': 'IBM', 'shares': 100, 'price': 91.1}, 数据结构和算法 7  {'name': 'AAPL', 'shares': 50, 'price': 543.22}, {'name': 'FB', 'shares': 200, 'price': 21.09}, {'name': 'HPQ', 'shares': 35, 'price': 31.75}, {'name': 'YHOO', 'shares': 45, 'price': 16.35}, {'name': 'ACME', 'shares': 75, 'price': 115.65} ] cheap = heapq.nsmallest(3, portfolio, key=lambda s: s['price']) expensive = heapq.nlargest(3, portfolio, key=lambda s: s['price']) 1.4.3 讨论 如果正在寻找最大或最小的 N 个元素，且同集合中元素的总数目相比，N 很小，那么 下面这些函数可以提供更好的性能。这些函数首先会在底层将数据转化成列表，且元 素会以堆的顺序排列。例如： >>> nums = [1, 8, 2, 23, 7, -4, 18, 23, 42, 37, 2] >>> import heapq >>> heap = list(nums) >>> heapq.heapify(heap) >>> heap [-4, 2, 1, 23, 7, 2, 18, 23, 42, 37, 8] >>> 堆最重要的特性就是 heap总是最小那个的元素。此外，接下来的元素可依次通过 heapq.heappop()方法轻松找到。该方法会将第一个元素（最小的）弹出，然后以第二小 的元素取而代之（这个操作的复杂度是 O(logN)，N 代表堆的大小） 。例如，要找到第 3 小的元素，可以这样做： >>> heapq.heappop(heap) -4 >>> heapq.heappop(heap) 1 >>> heapq.heappop(heap) 2 当所要找的元素数量相对较小时，函数 nlargest()和 nsmallest()才是最适用的。如果只是 简单地想找到最小或最大的元素（N=1 时），那么用 min()和 max()会更加快。同样，如 果 N 和集合本身的大小差不多大，通常更快的方法是先对集合排序，然后做切片操作 （例如，使用 sorted(items)[:N]或者 sorted(items)[-N:]）。应该要注意的是，nlargest()和 nsmallest()的实际实现会根据使用它们的方式而有所不同，可能会相应作出一些优化措 施（比如，当 N 的大小同输入大小很接近时，就会采用排序的方法）。 使用本节的代码片段并不需要知道如何实现堆数据结构，但这仍然是一个有趣也是值 8 第1章 得去学习的主题。通常在优秀的算法和数据结构相关的书籍里都能找到堆数据结构的 实现方法。在 heapq 模块的文档中也讨论了底层实现的细节。 1.5 实现优先级队列 1.5.1 问题 我们想要实现一个队列，它能够以给定的优先级来对元素排序，且每次 pop 操作时都 会返回优先级最高的那个元素。 1.5.2 解决方案 下面的类利用 heapq 模块实现了一个简单的优先级队列： import heapq class PriorityQueue: def __init__(self): self._queue = [] self._index = 0 def push(self, item, priority): heapq.heappush(self._queue, (-priority, self._index, item)) self._index += 1 def pop(self): return heapq.heappop(self._queue)[-1] 下面是如何使用这个类的例子： >>> class Item:... def __init__(self, name):... self.name = name... def __repr__(self):... return 'Item({!r})'.format(self.name)... >>> q = PriorityQueue() >>> q.push(Item('foo'), 1) >>> q.push(Item('bar'), 5) >>> q.push(Item('spam'), 4) >>> q.push(Item('grok'), 1) >>> q.pop() Item('bar') >>> q.pop() 数据结构和算法 9  Item('spam') >>> q.pop() Item('foo') >>> q.pop() Item('grok') >>> 请注意观察，第一次执行 pop()操作时返回的元素具有最高的优先级。我们也观察到拥 有相同优先级的两个元素（foo 和 grok）返回的顺序同它们插入到队列时的顺序相同。 1.5.3 讨论 上 面 的 代 码 片 段 的 核 心 在 于 heapq 模 块 的 使 用 。 函 数 heapq.heappush() 以 及 heapq.heappop()分别实现将元素从列表_queue 中插入和移除，且保证列表中第一个元素 的优先级最低（如 1.4 节所述）。heappop()方法总是返回“最小”的元素，因此这就是 让队列能弹出正确元素的关键。此外，由于 push 和 pop 操作的复杂度都是 O(logN)， 其中 N 代表堆中元素的数量，因此就算 N 的值很大，这些操作的效率也非常高。 在这段代码中，队列以元组(-priority, index, item)的形式组成。把 priority 取负值是为了 让队列能够按元素的优先级从高到低的顺序排列。这和正常的堆排列顺序相反，一般 情况下堆是按从小到大的顺序排序的。 变量 index 的作用是为了将具有相同优先级的元素以适当的顺序排列。通过维护一个不 断递增的索引，元素将以它们入队列时的顺序来排列。但是，index 在对具有相同优先 级的元素间做比较操作时同样扮演了重要的角色。 为了说明 Item 实例是没法进行次序比较的，我们来看下面这个例子： >>> a = Item('foo') >>> b = Item('bar') >>> a < b Traceback (most recent call last): File "", line 1, in TypeError: unorderable types: Item() < Item() >>> 如果以元组(priority, item)的形式来表示元素，那么只要优先级不同，它们就可以进 行比较。但是，如果两个元组的优先级值相同，做比较操作时还是会像之前那样失 败。例如： >>> a = (1, Item('foo')) >>> b = (5, Item('bar')) >>> a < b True >>> c = (1, Item('grok')) 10 第1章  >>> a < c Traceback (most recent call last): File "", line 1, in TypeError: unorderable types: Item() < Item() >>> 通过引入额外的索引值，以(prioroty, index, item)的方式建立元组，就可以完全避免这个 问题。因为没有哪两个元组会有相同的 index 值（一旦比较操作的结果可以确定，Python 就不会再去比较剩下的元组元素了）： >>> a = (1, 0, Item('foo')) >>> b = (5, 1, Item('bar')) >>> c = (1, 2, Item('grok')) >>> a < b True >>> a < c True >>> 如果想将这个队列用于线程间通信，还需要增加适当的锁和信号机制。请参见 12.3 节 的示例学习如何去做。 关于堆的理论和实现在 heapq 模块的文档中有着详细的示例和相关讨论。 1.6 在字典中将键映射到多个值上 1.6.1 问题 我们想要一个能将键（key）映射到多个值的字典（即所谓的一键多值字典[multidict]）。 1.6.2 解决方案 字典是一种关联容器，每个键都映射到一个单独的值上。如果想让键映射到多个值，需 要将这多个值保存到另一个容器如列表或集合中。例如，可能会像这样创建字典： d = { 'a' : [1, 2, 3], 'b' : [4, 5] } e = { 'a' : {1, 2, 3}, 'b' : {4, 5} } 要使用列表还是集合完全取决于应用的意图。如果希望保留元素插入的顺序，就用列 数据结构和算法 11 表。如果希望消除重复元素（且不在意它们的顺序），就用集合。 为了能方便地创建这样的字典，可以利用 collections 模块中的 defaultdict 类。defaultdict 的一个特点就是它会自动初始化第一个值，这样只需关注添加元素即可。例如： from collections import defaultdict d = defaultdict(list) d['a'].append(1) d['a'].append(2) d['b'].append(4)... d = defaultdict(set) d['a'].add(1) d['a'].add(2) d['b'].add(4)... 关于 defaultdict，需要注意的一个地方是，它会自动创建字典表项以待稍后的访问（即 使这些表项当前在字典中还没有找到）。如果不想要这个功能，可以在普通的字典上调 用 setdefault()方法来取代。例如： d = {} # A regular dictionary d.setdefault('a', []).append(1) d.setdefault('a', []).append(2) d.setdefault('b', []).append(4)... 然而，许多程序员觉得使用 setdefault()有点不自然—更别提每次调用它时都会创建一 个初始值的新实例了（例子中的空列表[]）。 1.6.3 讨论 原则上，构建一个一键多值字典是很容易的。但是如果试着自己对第一个值做初始化 操作，这就会变得很杂乱。例如，可能会写下这样的代码： d = {} for key, value in pairs: if key not in d: d[key] = [] d[key].append(value) 使用 defaultdict 后代码会清晰得多： d = defaultdict(list) for key, value in pairs: d[key].append(value) 12 第1章 这一节的内容同数据处理中的记录归组问题有很强的关联。请参见 1.15 节的示例。 1.7 让字典保持有序 1.7.1 问题 我们想创建一个字典，同时当对字典做迭代或序列化操作时，也能控制其中元素的顺序。 1.7.2 解决方案 要控制字典中元素的顺序，可以使用 collections 模块中的 OrderedDict 类。当对字典做 迭代时，它会严格按照元素初始添加的顺序进行。例如： from collections import OrderedDict d = OrderedDict() d['foo'] = 1 d['bar'] = 2 d['spam'] = 3 d['grok'] = 4 # Outputs "foo 1", "bar 2", "spam 3", "grok 4" for key in d: print(key, d[key]) 当想构建一个映射结构以便稍后对其做序列化或编码成另一种格式时，OrderedDict 就 显得特别有用。例如，如果想在进行 JSON 编码时精确控制各字段的顺序，那么只要首 先在 OrderedDict 中构建数据就可以了。 >>> import json >>> json.dumps(d) '{"foo": 1, "bar": 2, "spam": 3, "grok": 4}' >>> 1.7.3 讨论 OrderedDict 内部维护了一个双向链表，它会根据元素加入的顺序来排列键的位置。第 一个新加入的元素被放置在链表的末尾。接下来对已存在的键做重新赋值不会改变键 的顺序。 请注意 OrderedDict 的大小是普通字典的 2 倍多，这是由于它额外创建的链表所致。因 此，如果打算构建一个涉及大量 OrderedDict 实例的数据结构（例如从 CSV 文件中读 取 100000 行内容到 OrderedDict 列表中） ，那么需要认真对应用做需求分析，从而判断 数据结构和算法 13 使用 OrderedDict 所带来的好处是否能超越因额外的内存开销所带来的缺点。 1.8 与字典有关的计算问题 1.8.1 问题 我们想在字典上对数据执行各式各样的计算（比如求最小值、最大值、排序等）。 1.8.2 解决方案 假设有一个字典在股票名称和对应的价格间做了映射： prices = { 'ACME': 45.23, 'AAPL': 612.78, 'IBM': 205.55, 'HPQ': 37.20, 'FB': 10.75 } 为了能对字典内容做些有用的计算，通常会利用 zip()将字典的键和值反转过来。例如， 下面的代码会告诉我们如何找出价格最低和最高的股票。 min_price = min(zip(prices.values(), prices.keys())) # min_price is (10.75, 'FB') max_price = max(zip(prices.values(), prices.keys())) # max_price is (612.78, 'AAPL') 同样，要对数据排序只要使用 zip()再配合 sorted()就可以了，比如： prices_sorted = sorted(zip(prices.values(), prices.keys())) # prices_sorted is [(10.75, 'FB'), (37.2, 'HPQ'), # (45.23, 'ACME'), (205.55, 'IBM'), # (612.78, 'AAPL')] 当进行这些计算时，请注意 zip()创建了一个迭代器，它的内容只能被消费一次。例如 下面的代码就是错误的： prices_and_names = zip(prices.values(), prices.keys()) print(min(prices_and_names)) # OK print(max(prices_and_names)) # ValueError: max() arg is an empty sequence 1.8.3 讨论 如果尝试在字典上执行常见的数据操作，将会发现它们只会处理键，而不是值。例如： 14 第1章  min(prices) # Returns 'AAPL' max(prices) # Returns 'IBM' 这很可能不是我们所期望的，因为实际上我们是尝试对字典的值做计算。可以利用字 典的 values()方法来解决这个问题： min(prices.values()) # Returns 10.75 max(prices.values()) # Returns 612.78 不幸的是，通常这也不是我们所期望的。比如，我们可能想知道相应的键所关联的信 息是什么（例如哪支股票的价格最低？） 如果提供一个 key 参数传递给 min()和 max()，就能得到最大值和最小值所对应的键是 什么。例如： min(prices, key=lambda k: prices[k]) # Returns 'FB' max(prices, key=lambda k: prices[k]) # Returns 'AAPL' 但是，要得到最小值的话，还需要额外执行一次查找。例如： min_value = prices[min(prices, key=lambda k: prices[k])] 利用了 zip()的解决方案是通过将字典的键-值对“反转”为值-键对序列来解决这个问 题的。 当在这样的元组上执行比较操作时，值会先进行比较，然后才是键。这完全符合我们 的期望，允许我们用一条单独的语句轻松的对字典里的内容做整理和排序。 应该要注意的是，当涉及（value, key）对的比较时，如果碰巧有多个条目拥有相同的 value 值，那么此时 key 将用来作为判定结果的依据。例如，在计算 min()和 max()时， 如果碰巧 value 的值相同，则将返回拥有最小或最大 key 值的那个条目。示例如下： >>> prices = { 'AAA' : 45.23, 'ZZZ': 45.23 } >>> min(zip(prices.values(), prices.keys())) (45.23, 'AAA') >>> max(zip(prices.values(), prices.keys())) (45.23, 'ZZZ') >>> 1.9 在两个字典中寻找相同点 1.9.1 问题 有两个字典，我们想找出它们中间可能相同的地方（相同的键、相同的值等）。 数据结构和算法 15 1.9.2 解决方案 考虑如下两个字典： a = { 'x' : 1, 'y' : 2, 'z' : 3 } b = { 'w' : 10, 'x' : 11, 'y' : 2 } 要找出这两个字典中的相同之处，只需通过 keys()或者 items()方法执行常见的集合操作 即可。例如： # Find keys in common a.keys() & b.keys() # { 'x', 'y' } # Find keys in a that are not in b a.keys() - b.keys() # { 'z' } # Find (key,value) pairs in common a.items() & b.items() # { ('y', 2) } 这些类型的操作也可用来修改或过滤掉字典中的内容。例如，假设想创建一个新的字 典，其中会去掉某些键。下面是使用了字典推导式的代码示例： # Make a new dictionary with certain keys removed c = {key:a[key] for key in a.keys() - {'z', 'w'}} # c is {'x': 1, 'y': 2} 1.9.3 讨论 字典就是一系列键和值之间的映射集合。字典的 keys()方法会返回 keys-view 对象，其 中暴露了所有的键。关于字典的键有一个很少有人知道的特性，那就是它们也支持常 见的集合操作，比如求并集、交集和差集。因此，如果需要对字典的键做常见的集合 操作，那么就能直接使用 keys-view 对象而不必先将它们转化为集合。 字典的 items()方法返回由(key,value)对组成的 items-view 对象。这个对象支持类似的集 合操作，可用来完成找出两个字典间有哪些键值对有相同之处的操作。 尽管类似，但字典的 values()方法并不支持集合操作。部分原因是因为在字典中键和值 是不同的，从值的角度来看并不能保证所有的值都是唯一的。单这一条原因就使得某 16 第1章 些特定的集合操作是有问题的。但是，如果必须执行这样的操作，还是可以先将值转 化为集合来实现。 1.10 从序列中移除重复项且保持元素间顺序不变 1.10.1 问题 我们想去除序列中出现的重复元素，但仍然保持剩下的元素顺序不变。 1.10.2 解决方案 如果序列中的值是可哈希（hashable）的，那么这个问题可以通过使用集合和生成器轻 ① 松解决。示例如下 ： def dedupe(items): seen = set() for item in items: if item not in seen: yield item seen.add(item) 这里是如何使用这个函数的例子： >>> a = [1, 5, 2, 1, 9, 1, 5, 10] >>> list(dedupe(a)) [1, 5, 2, 9, 10] >>> 只有当序列中的元素是可哈希的时候才能这么做。如果想在不可哈希的对象（比如列 表）序列中去除重复项，需要对上述代码稍作修改： def dedupe(items, key=None): seen = set() for item in items: val = item if key is None else key(item) if val not in seen: yield item seen.add(val) 这里参数 key 的作用是指定一个函数用来将序列中的元素转换为可哈希的类型，这么 做的目的是为了检测重复项。它可以像这样工作： ① 如果一个对象是可哈希的，那么在它的生存期内必须是不可变的，它需要有一个__hash__()方法。 整数、浮点数、字符串、元组都是不可变的。——译者注 数据结构和算法 17  >>> a = [ {'x':1, 'y':2}, {'x':1, 'y':3}, {'x':1, 'y':2}, {'x':2, 'y':4}] >>> list(dedupe(a, key=lambda d: (d['x'],d['y']))) [{'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 2, 'y': 4}] >>> list(dedupe(a, key=lambda d: d['x'])) [{'x': 1, 'y': 2}, {'x': 2, 'y': 4}] >>> 如果希望在一个较复杂的数据结构中，只根据对象的某个字段或属性来去除重复项， 那么后一种解决方案同样能完美工作。 1.10.3 讨论 如果想要做的只是去除重复项，那么通常足够简单的办法就是构建一个集合。例如： >>> a [1, 5, 2, 1, 9, 1, 5, 10] >>> set(a) {1, 2, 10, 5, 9} >>> ① 但是这种方法不能保证元素间的顺序不变 ，因此得到的结果会被打乱。前面展示的解 决方案可避免出现这个问题。 本节中对生成器的使用反映出一个事实，那就是我们可能会希望这个函数尽可能的通 用—不必绑定在只能对列表进行处理。比如，如果想读一个文件，去除其中重复的 文本行，可以只需这样处理： with open(somefile,'r') as f: for line in dedupe(f):... 我们的 dedupe()函数也模仿了内置函数 sorted()、min()以及 max()对 key 函数的使用方 式。例子可参考 1.8 节和 1.13 节。 1.11 对切片命名 1.11.1 问题 我们的代码已经变得无法阅读，到处都是硬编码的切片索引，我们想将它们清理干净。 1.11.2 解决方案 假设有一些代码用来从字符串的固定位置中取出具体的数据（比如从一个平面文件或 ① 集合的特点就是集合中的元素都是唯一的，但不保证它们之间的顺序。—译者注 18 第1章  ① 类似的格式） ： ###### 0123456789012345678901234567890123456789012345678901234567890' record = '....................100.......513.25..........' cost = int(record[20:32]) * float(record[40:48]) 与其这样做，为什么不对切片命名呢？ SHARES = slice(20,32) PRICE = slice(40,48) cost = int(record[SHARES]) * float(record[PRICE]) 在后一种版本中，由于避免了使用许多神秘难懂的硬编码索引，我们的代码就变得清 晰了许多。 1.11.3 讨论 作为一条基本准则，代码中如果有很多硬编码的索引值，将导致可读性和可维护性都不 佳。例如，如果一年以后再回过头来看代码，你会发现自己很想知道当初编写这些代码 时自己在想些什么。前面展示的方法可以让我们对代码的功能有着更加清晰的认识。 一般来说，内置的 slice()函数会创建一个切片对象，可以用在任何允许进行切片操作的 地方。例如： >>> items = [0, 1, 2, 3, 4, 5, 6] >>> a = slice(2, 4) >>> items[2:4] [2, 3] >>> items[a] [2, 3] >>> items[a] = [10,11] >>> items [0, 1, 10, 11, 4, 5, 6] >>> del items[a] >>> items [0, 1, 4, 5, 6] 如果有一个 slice 对象的实例 s，可以分别通过 s.start、s.stop 以及 s.step 属性来得到关于 该对象的信息。例如： >>> a = slice( >>> a.start 10 >>> a.stop ① 平面文件（flat file）是一种包含没有相对关系结构的记录文件。—译者注 数据结构和算法 19  50 >>> a.step 2 >>> 此外，可以通过使用 indices(size)方法将切片映射到特定大小的序列上。这会返回一个 (start, stop, step)元组，所有的值都已经恰当地限制在边界以内（当做索引操作时可避免 出现 IndexError 异常）。例如： >>> s = 'HelloWorld' >>> a.indices(len(s)) (5, 10, 2) >>> for i in range(*a.indices(len(s))):... print(s[i])... w r d >>> 1.12 找出序列中出现次数最多的元素 1.12.1 问题 我们有一个元素序列，想知道在序列中出现次数最多的元素是什么。 1.12.2 解决方案 collections 模块中的 Counter 类正是为此类问题所设计的。它甚至有一个非常方便的 most_common()方法可以直接告诉我们答案。 为了说明用法，假设有一个列表，列表中是一系列的单词，我们想找出哪些单词出现 的最为频繁。下面是我们的做法： words = [ 'look', 'into', 'my', 'eyes', 'look', 'into', 'my', 'eyes', 'the', 'eyes', 'the', 'eyes', 'the', 'eyes', 'not', 'around', 'the', 'eyes', "don't", 'look', 'around', 'the', 'eyes', 'look', 'into', 'my', 'eyes', "you're", 'under' ] from collections import Counter word_counts = Counter(words) top_three = word_counts.most_common(3) print(top_three) # Outputs [('eyes', 8), ('the', 5), ('look', 4)] 20 第1章 1.12.3 讨论 可以给 Counter 对象提供任何可哈希的对象序列作为输入。在底层实现中，Counter 是 一个字典，在元素和它们出现的次数间做了映射。例如： >>> word_counts['not'] 1 >>> word_counts['eyes'] 8 >>> 如果想手动增加计数，只需简单地自增即可： >>> morewords = ['why','are','you','not','looking','in','my','eyes'] >>> for word in morewords:... word_counts[word] += 1... >>> word_counts['eyes'] 9 >>> 另一种方式是使用 update()方法。 >>> word_counts.update(morewords) >>> 关于 Counter 对象有一个不为人知的特性，那就是它们可以轻松地同各种数学运算操作 结合起来使用。例如： >>> a = Counter(words) >>> b = Counter(morewords) >>> a Counter({'eyes': 8, 'the': 5, 'look': 4, 'into': 3, 'my': 3, 'around': 2, "you're": 1, "don't": 1, 'under': 1, 'not': 1}) >>> b Counter({'eyes': 1, 'looking': 1, 'are': 1, 'in': 1, 'not': 1, 'you': 1, 'my': 1, 'why': 1}) >>> # Combine counts >>> c = a + b >>> c Counter({'eyes': 9, 'the': 5, 'look': 4, 'my': 4, 'into': 3, 'not': 2, 'around': 2, "you're": 1, "don't": 1, 'in': 1, 'why': 1, 'looking': 1, 'are': 1, 'under': 1, 'you': 1}) >>> # Subtract counts >>> d = a - b 数据结构和算法 21  >>> d Counter({'eyes': 7, 'the': 5, 'look': 4, 'into': 3, 'my': 2, 'around': 2, "you're": 1, "don't": 1, 'under': 1}) >>> 不用说，当面对任何需要对数据制表或计数的问题时，Counter 对象都是你手边的得力 工具。比起利用字典自己手写算法，更应该采用这种方式完成任务。 1.13 通过公共键对字典列表排序 1.13.1 问题 我们有一个字典列表，想根据一个或多个字典中的值来对列表排序。 1.13.2 解决方案 利用 operator 模块中的 itemgetter 函数对这类结构进行排序是非常简单的。假设通过查 询数据库表项获取网站上的成员列表，我们得到了如下的数据结构： rows = [ {'fname': 'Brian', 'lname': 'Jones', 'uid': 1003}, {'fname': 'David', 'lname': 'Beazley', 'uid': 1002}, {'fname': 'John', 'lname': 'Cleese', 'uid': 1001}, {'fname': 'Big', 'lname': 'Jones', 'uid': 1004} ] 根据所有的字典中共有的字段来对这些记录排序是非常简单的，示例如下： from operator import itemgetter rows_by_fname = sorted(rows, key=itemgetter('fname')) rows_by_uid = sorted(rows, key=itemgetter('uid')) print(rows_by_fname) print(rows_by_uid) 以上代码的输出为： [{'fname': 'Big', 'uid': 1004, 'lname': 'Jones'}, {'fname': 'Brian', 'uid': 1003, 'lname': 'Jones'}, {'fname': 'David', 'uid': 1002, 'lname': 'Beazley'}, {'fname': 'John', 'uid': 1001, 'lname': 'Cleese'}] [{'fname': 'John', 'uid': 1001, 'lname': 'Cleese'}, {'fname': 'David', 'uid': 1002, 'lname': 'Beazley'}, {'fname': 'Brian', 'uid': 1003, 'lname': 'Jones'}, {'fname': 'Big', 'uid': 1004, 'lname': 'Jones'}] 22 第1章 itemgetter()函数还可以接受多个键。例如下面这段代码： rows_by_lfname = sorted(rows, key=itemgetter('lname','fname')) print(rows_by_lfname) 这会产生如下的输出： [{'fname': 'David', 'uid': 1002, 'lname': 'Beazley'}, {'fname': 'John', 'uid': 1001, 'lname': 'Cleese'}, {'fname': 'Big', 'uid': 1004, 'lname': 'Jones'}, {'fname': 'Brian', 'uid': 1003, 'lname': 'Jones'}] 1.13.3 讨论 在这个例子中，rows 被传递给内建的 sorted()函数，该函数接受一个关键字参数 key。这 个参数应该代表一个可调用对象（callable） ，该对象从 rows 中接受一个单独的元素作为 输入并返回一个用来做排序依据的值。itemgetter()函数创建的就是这样一个可调用对象。 函数 operator.itemgetter()接受的参数可作为查询的标记，用来从 rows 的记录中提取出 所需要的值。它可以是字典的键名称、用数字表示的列表元素或是任何可以传给对象 的__getitem__()方法的值。如果传多个标记给 itemgetter()，那么它产生的可调用对象 将返回一个包含所有元素在内的元组，然后 sorted()将根据对元组的排序结果来排列 输出结果。如果想同时针对多个字段做排序（比如例子中的姓和名），那么这是非常 有用的。 有时候会用 lambda 表达式来取代 itemgetter()的功能。例如： rows_by_fname = sorted(rows, key=lambda r: r['fname']) rows_by_lfname = sorted(rows, key=lambda r: (r['lname'],r['fname'])) 这种解决方案通常也能正常工作。但是用 itemgetter()通常会运行得更快一些。因此如 果需要考虑性能问题的话，应该使用 itemgetter()。 最后不要忘了本节中所展示的技术同样适用于 min()和 max()这样的函数。例如： >>> min(rows, key=itemgetter('uid')) {'fname': 'John', 'lname': 'Cleese', 'uid': 1001} >>> max(rows, key=itemgetter('uid')) {'fname': 'Big', 'lname': 'Jones', 'uid': 1004} >>> 1.14 对不原生支持比较操作的对象排序 1.14.1 问题 我们想在同一个类的实例之间做排序，但是它们并不原生支持比较操作。 数据结构和算法 23 1.14.2 解决方案 内建的 sorted()函数可接受一个用来传递可调用对象（callable）的参数 key，而该 可调用对象会返回待排序对象中的某些值，sorted 则利用这些值来比较对象。例 如，如果应用中有一系列的 User 对象实例，而我们想通过 user_id 属性来对它们 排序，则可以提供一个可调用对象将 User 实例作为输入然后返回 user_id。示例 如下： >>> class User:... def __init__(self, user_id):... self.user_id = user_id... def __repr__(self):... return 'User({})'.format(self.user_id)... >>> users = [User(23), User(3), User(99)] >>> users [User(23), User(3), User(99)] >>> sorted(users, key=lambda u: u.user_id) [User(3), User(23), User(99)] >>> 除了可以用 lambda 表达式外，另一种方式是使用 operator.attrgetter()。 >>> from operator import attrgetter >>> sorted(users, key=attrgetter('user_id')) [User(3), User(23), User(99)] >>> 1.14.3 讨论 要使用 lambda 表达式还是 attrgetter()或许只是一种个人喜好。但是通常来说，attrgetter()要 更快一些，而且具有允许同时提取多个字段值的能力。这和针对字典的 operator.itemgetter() 的使用很类似（参见 1.13 节）。例如，如果 User 实例还有一个 first_name 和 last_name 属性的话，可以执行如下的排序操作： by_name = sorted(users, key=attrgetter('last_name', 'first_name')) 同样值得一提的是，本节所用到的技术也适用于像 min()和 max()这样的函数。例如： >>> min(users, key=attrgetter('user_id') User(3) >>> max(users, key=attrgetter('user_id') User(99) >>> 24 第1章 1.15 根据字段将记录分组 1.15.1 问题 有一系列的字典或对象实例，我们想根据某个特定的字段（比如说日期）来分组迭代数据。 1.15.2 解决方案 itertools.groupby()函数在对数据进行分组时特别有用。为了说明其用途，假设有如下的 字典列表： rows = [ {'address': '5412 N CLARK', 'date': '07/01/2012'}, {'address': '5148 N CLARK', 'date': '07/04/2012'}, {'address': '5800 E 58TH', 'date': '07/02/2012'}, {'address': '2122 N CLARK', 'date': '07/03/2012'}, {'address': '5645 N RAVENSWOOD', 'date': '07/02/2012'}, {'address': '1060 W ADDISON', 'date': '07/02/2012'}, {'address': '4801 N BROADWAY', 'date': '07/01/2012'}, {'address': '1039 W GRANVILLE', 'date': '07/04/2012'}, ] 现在假设想根据日期以分组的方式迭代数据。要做到这些，首先以目标字段（在这个 例子中是 date）来对序列排序，然后再使用 itertools.groupby()。 from operator import itemgetter from itertools import groupby # Sort by the desired field first rows.sort(key=itemgetter('date')) # Iterate in groups for date, items in groupby(rows, key=itemgetter('date')): print(date) for i in items: print(' ', i) 这会产生如下的输出： 07/01/2012 {'date': '07/01/2012', 'address': '5412 N CLARK'} {'date': '07/01/2012', 'address': '4801 N BROADWAY'} 07/02/2012 {'date': '07/02/2012', 'address': '5800 E 58TH'} 数据结构和算法 25  {'date': '07/02/2012', 'address': '5645 N RAVENSWOOD'} {'date': '07/02/2012', 'address': '1060 W ADDISON'} 07/03/2012 {'date': '07/03/2012', 'address': '2122 N CLARK'} 07/04/2012 {'date': '07/04/2012', 'address': '5148 N CLARK'} {'date': '07/04/2012', 'address': '1039 W GRANVILLE'} 1.15.3 讨论 函数 groupby()通过扫描序列找出拥有相同值（或是由参数 key 指定的函数所返回的值） 的序列项，并将它们分组。groupby()创建了一个迭代器，而在每次迭代时都会返回一 个值（value）和一个子迭代器（sub_iterator），这个子迭代器可以产生所有在该分组内 具有该值的项。 在这里重要的是首先要根据感兴趣的字段对数据进行排序。因为 groupby()只能检查连 续的项，不首先排序的话，将无法按所想的方式来对记录分组。 如果只是简单地根据日期将数据分组到一起，放进一个大的数据结构中以允许进行随 机访问，那么利用 defaultdict()构建一个一键多值字典（multidict，见 1.6 节）可能会更 好。例如： from collections import defaultdict rows_by_date = defaultdict(list) for row in rows: rows_by_date[row['date']].append(row) 这使得我们可以方便地访问每个日期的记录，如下所示： >>> for r in rows_by_date['07/01/2012']:... print(r)... {'date': '07/01/2012', 'address': '5412 N CLARK'} {'date': '07/01/2012', 'address': '4801 N BROADWAY'} >>> 对于后面这个例子，我们并不需要先对记录做排序。因此，如果不考虑内存方面的因 素，这种方式会比先排序再用 groupby()迭代要来的更快。 1.16 筛选序列中的元素 1.16.1 问题 序列中含有一些数据，我们需要提取出其中的值或根据某些标准对序列做删减。 26 第1章 1.16.2 解决方案 要筛选序列中的数据，通常最简单的方法是使用列表推导式（list comprehension） 。例 如： >>> mylist = [1, 4, -5, 10, -7, 2, 3, -1] >>> [n for n in mylist if n > 0] [1, 4, 10, 2, 3] >>> [n for n in mylist if n < 0] [-5, -7, -1] >>> 使用列表推导式的一个潜在缺点是如果原始输入非常大的话，这么做可能会产生一个 庞大的结果。如果这是你需要考虑的问题，那么可以使用生成器表达式通过迭代的方 式产生筛选的结果。例如： >>> pos = (n for n in mylist if n > 0) >>> pos >>> for x in pos:... print(x)... 1 4 10 2 3 >>> 有时候筛选的标准没法简单地表示在列表推导式或生成器表达式中。比如，假设筛选 过程涉及异常处理或者其他一些复杂的细节。基于此，可以将处理筛选逻辑的代码放 到单独的函数中，然后使用内建的 filter()函数处理。示例如下： values = ['1', '2', '-3', '-', '4', 'N/A', '5'] def is_int(val): try: x = int(val) return True except ValueError: return False ivals = list(filter(is_int, values)) print(ivals) # Outputs ['1', '2', '-3', '4', '5'] 数据结构和算法 27 filter()创建了一个迭代器，因此如果我们想要的是列表形式的结果，请确保加上了 list()， 就像示例中那样。 1.16.3 讨论 列表推导式和生成器表达式通常是用来筛选数据的最简单和最直接的方式。此外，它 们也具有同时对数据做转换的能力。例如： >>> mylist = [1, 4, -5, 10, -7, 2, 3, -1] >>> import math >>> [math.sqrt(n) for n in mylist if n > 0] [1.0, 2.0, 3.1622776601683795, 1.4142135623730951, 1.7320508075688772] >>> 关于筛选数据，有一种情况是用新值替换掉不满足标准的值，而不是丢弃它们。例如， 除了要找到正整数之外，我们也许还希望在指定的范围内将不满足要求的值替换掉。 通常，这可以通过将筛选条件移到一个条件表达式中来轻松实现。就像下面这样： >>> clip_neg = [n if n > 0 else 0 for n in mylist] >>> clip_neg [1, 4, 0, 10, 0, 2, 3, 0] >>> clip_pos = [n if n < 0 else 0 for n in mylist] >>> clip_pos [0, 0, -5, 0, -7, 0, 0, -1] >>> 另一个值得一提的筛选工具是 itertools.compress()，它接受一个可迭代对象以及一个布 尔选择器序列作为输入。输出时，它会给出所有在相应的布尔选择器中为 True 的可迭 代对象元素。如果想把对一个序列的筛选结果施加到另一个相关的序列上时，这就会 非常有用。例如，假设有以下两列数据： addresses = [ '5412 N CLARK', '5148 N CLARK', '5800 E 58TH', '2122 N CLARK' '5645 N RAVENSWOOD', '1060 W ADDISON', '4801 N BROADWAY', '1039 W GRANVILLE', ] counts = [ 0, 3, 10, 4, 1, 7, 6, 1] 现在我们想构建一个地址列表，其中相应的 count 值要大于 5。下面是我们可以尝试的 28 第1章 方法： >>> from itertools import compress >>> more5 = [n > 5 for n in counts] >>> more5 [False, False, True, False, False, True, True, False] >>> list(compress(addresses, more5)) ['5800 E 58TH', '4801 N BROADWAY', '1039 W GRANVILLE'] >>> 这里的关键在于首先创建一个布尔序列，用来表示哪个元素可满足我们的条件。然后 compress()函数挑选出满足布尔值为 True 的相应元素。 同 filter()函数一样，正常情况下 compress()会返回一个迭代器。因此，如果需要的话， 得使用 list()将结果转为列表。 1.17 从字典中提取子集 1.17.1 问题 我们想创建一个字典，其本身是另一个字典的子集。 1.17.2 解决方案 利用字典推导式（dictionary comprehension）可轻松解决。例如： prices = { 'ACME': 45.23, 'AAPL': 612.78, 'IBM': 205.55, 'HPQ': 37.20, 'FB': 10.75 } # Make a dictionary of all prices over 200 p1 = { key:value for key, value in prices.items() if value > 200 } # Make a dictionary of tech stocks tech_names = { 'AAPL', 'IBM', 'HPQ', 'MSFT' } p2 = { key:value for key,value in prices.items() if key in tech_names } 1.17.3 讨论 大部分可以用字典推导式解决的问题也可以通过创建元组序列然后将它们传给 dict()函 数据结构和算法 29 数来完成。例如： p1 = dict((key, value) for key, value in prices.items() if value > 200) 但是字典推导式的方案更加清晰，而且实际运行起来也要快很多（以本例中的字典 prices 来测试，效率要高 2 倍多）。 有时候会有多种方法来完成同一件事情。例如，第二个例子还可以重写成： # Make a dictionary of tech stocks tech_names = { 'AAPL', 'IBM', 'HPQ', 'MSFT' } p2 = { key:prices[key] for key in prices.keys() & tech_names } 但是，计时测试表明这种解决方案几乎要比第一种慢上 1.6 倍。如果需要考虑性能因 素，那么通常都需要花一点时间来研究它。有关计时和性能分析方面的信息，请参见 14.13 节。 1.18 将名称映射到序列的元素中 1.18.1 问题 我们的代码是通过位置（即索引，或下标）来访问列表或元组的，但有时候这会使代 码变得有些难以阅读。我们希望可以通过名称来访问元素，以此减少结构中对位置的 依赖性。 1.18.2 解决方案 相比普通的元组，collections.namedtuple()（命名元组）只增加了极小的开销就提供了这 些便利。实际上 collections.namedtuple()是一个工厂方法，它返回的是 Python 中标准元 组类型的子类。我们提供给它一个类型名称以及相应的字段，它就返回一个可实例化 的类、为你已经定义好的字段传入值等。例如： >>> from collections import namedtuple >>> Subscriber = namedtuple('Subscriber', ['addr', 'joined']) >>> sub = Subscriber('[email protected]', '2012-10-19') >>> sub Subscriber(addr='[email protected]', joined='2012-10-19') >>> sub.addr '[email protected]' >>> sub.joined '2012-10-19' >>> 尽管 namedtuple 的实例看起来就像一个普通的类实例，但它的实例与普通的元组是可互换 30 第1章 的，而且支持所有普通元组所支持的操作，例如索引（indexing）和分解（unpacking） 。 比如： >>> len(sub) 2 >>> addr, joined = sub >>> addr '[email protected]' >>> joined '2012-10-19' >>> 命名元组的主要作用在于将代码同它所控制的元素位置间解耦。所以，如果从数据库 调用中得到一个大型的元组列表，而且通过元素的位置来访问数据，那么假如在表单 中新增了一列数据，那么代码就会崩溃。但如果首先将返回的元组转型为命名元组， 就不会出现问题。 为了说明这个问题，下面有一些使用普通元组的代码： def compute_cost(records): total = 0.0 for rec in records: total += rec * rec return total 通过位置来引用元素常常使得代码的表达力不够强，而且也很依赖于记录的具体结构。 下面是使用命名元组的版本： from collections import namedtuple Stock = namedtuple('Stock', ['name', 'shares', 'price']) def compute_cost(records): total = 0.0 for rec in records: s = Stock(*rec) total += s.shares * s.price return total 当然，如果示例中的 records 序列已经包含了这样的实例，那么可以避免显式地将记录 ① 转换为 Stock 命名元组 。 1.18.3 讨论 namedtuple 的一种可能用法是作为字典的替代，后者需要更多的空间来存储。因此，如 ① 作者的意思是如果 records 中的元素是某个类的实例，且已经有了 shares 和 price 这样的属性，那就可以 直接通过属性名来访问，不需要通过位置来引用，也就没有必要再转换成命名元组了。——译者注 数据结构和算法 31 果要构建涉及字典的大型数据结构，使用 namedtuple 会更加高效。但是请注意，与字 典不同的是，namedtuple 是不可变的（immutable）。例如： >>> s = Stock('ACME', 100, 123.45) >>> s Stock(name='ACME', shares=100, price=123.45) >>> s.shares = 75 Traceback (most recent call last): File "", line 1, in AttributeError: can't set attribute >>> 如果需要修改任何属性，可以通过使用 namedtuple 实例的_replace()方法来实现。该方 法会创建一个全新的命名元组，并对相应的值做替换。示例如下： >>> s = s._replace(shares=75) >>> s Stock(name='ACME', shares=75, price=123.45) >>> _replace()方法有一个微妙的用途，那就是它可以作为一种简便的方法填充具有可选或 缺失字段的命名元组。要做到这点，首先创建一个包含默认值的“原型”元组，然后 使用_replace()方法创建一个新的实例，把相应的值替换掉。示例如下： from collections import namedtuple Stock = namedtuple('Stock', ['name', 'shares', 'price', 'date', 'time']) # Create a prototype instance stock_prototype = Stock('', 0, 0.0, None, None) # Function to convert a dictionary to a Stock def dict_to_stock(s): return stock_prototype._replace(**s) 让我们演示一下上面的代码是如何工作的： >>> a = {'name': 'ACME', 'shares': 100, 'price': 123.45} >>> dict_to_stock(a) Stock(name='ACME', shares=100, price=123.45, date=None, time=None) >>> b = {'name': 'ACME', 'shares': 100, 'price': 123.45, 'date': '12/17/2012'} >>> dict_to_stock(b) Stock(name='ACME', shares=100, price=123.45, date='12/17/2012', time=None) >>> 最后，也是相当重要的是，应该要注意如果我们的目标是定义一个高效的数据结构， 32 第1章 而且将来会修改各种实例属性，那么使用 namedtuple 并不是最佳选择。相反，可以考 虑定义一个使用__slots__属性的类（参见 8.4 节）。 1.19 同时对数据做转换和换算 1.19.1 问题 我们需要调用一个换算（reduction）函数（例如 sum()、min()、max()），但首先得对数 据做转换或筛选。 1.19.2 解决方案 有一种非常优雅的方式能将数据换算和转换结合在一起—在函数参数中使用生成器 表达式。例如，如果想计算平方和，可以像下面这样做： nums = [1, 2, 3, 4, 5] s = sum(x * x for x in nums) 这里还有一些其他的例子： # Determine if any.py files exist in a directory import os files = os.listdir('dirname') if any(name.endswith('.py') for name in files): print('There be python!') else: print('Sorry, no python.') # Output a tuple as CSV s = ('ACME', 50, 123.45) print(','.join(str(x) for x in s)) # Data reduction across fields of a data structure portfolio = [ {'name':'GOOG', 'shares': 50}, {'name':'YHOO', 'shares': 75}, {'name':'AOL', 'shares': 20}, {'name':'SCOX', 'shares': 65} ] min_shares = min(s['shares'] for s in portfolio) 1.19.3 讨论 这种解决方案展示了当把生成器表达式作为函数的单独参数时在语法上的一些微妙之 数据结构和算法 33 处（即，不必重复使用括号）。比如，下面这两行代码表示的是同一个意思： s = sum((x * x for x in nums)) # Pass generator-expr as argument s = sum(x * x for x in nums) # More elegant syntax 比起首先创建一个临时的列表，使用生成器做参数通常是更为高效和优雅的方式。例 如，如果不使用生成器表达式，可能会考虑下面这种实现： nums = [1, 2, 3, 4, 5] s = sum([x * x for x in nums]) 这也能工作，但这引入了一个额外的步骤而且创建了额外的列表。对于这么小的一个 列表，这根本就无关紧要，但是如果 nums 非常巨大，那么就会创建一个庞大的临时数 据结构，而且只用一次就要丢弃。基于生成器的解决方案可以以迭代的方式转换数据， 因此在内存使用上要高效得多。 某些特定的换算函数比如 min()和 max()都可接受一个 key 参数，当可能倾向于使用生 成器时会很有帮助。例如在 portfolio 的例子中，也许会考虑下面这种替代方案： # Original: Returns 20 min_shares = min(s['shares'] for s in portfolio) # Alternative: Returns {'name': 'AOL', 'shares': 20} min_shares = min(portfolio, key=lambda s: s['shares']) 1.20 将多个映射合并为单个映射 1.20.1 问题 我们有多个字典或映射，想在逻辑上将它们合并为一个单独的映射结构，以此执行某 些特定的操作，比如查找值或检查键是否存在。 1.20.2 解决方案 假设有两个字典： a = {'x': 1, 'z': 3 } b = {'y': 2, 'z': 4 } 现在假设想执行查找操作，我们必须得检查这两个字典（例如，先在 a 中查找，如果 没找到再去 b 中查找）。一种简单的方法是利用 collections 模块中的 ChainMap 类来解 决这个问题。例如： from collections import ChainMap c = ChainMap(a,b) 34 第1章  print(c['x']) # Outputs 1 (from a) print(c['y']) # Outputs 2 (from b) print(c['z']) # Outputs 3 (from a) 1.20.3 讨论 ChainMap 可接受多个映射然后在逻辑上使它们表现为一个单独的映射结构。但是，这 些映射在字面上并不会合并在一起。相反，ChainMap 只是简单地维护一个记录底层映 射关系的列表，然后重定义常见的字典操作来扫描这个列表。大部分的操作都能正常 工作。例如： >>> len(c) 3 >>> list(c.keys()) ['x', 'y', 'z'] >>> list(c.values()) [1, 2, 3] >>> 如果有重复的键，那么这里会采用第一个映射中所对应的值。因此，例子中的 c[‘z’]总 是引用字典 a 中的值，而不是字典 b 中的值。 修改映射的操作总是会作用在列出的第一个映射结构上。例如： >>> c['z'] = 10 >>> c['w'] = 40 >>> del c['x'] >>> a {'w': 40, 'z': 10} >>> del c['y'] Traceback (most recent call last):... KeyError: "Key not found in the first mapping: 'y'" >>> ChainMap 与带有作用域的值，比如编程语言中的变量（即全局变量、局部变量等）一 起工作时特别有用。实际上这里有一些方法使这个过程变得简单： >>> values = ChainMap() >>> values['x'] = 1 >>> # Add a new mapping >>> values = values.new_child() >>> values['x'] = 2 >>> # Add a new mapping >>> values = values.new_child() >>> values['x'] = 3 数据结构和算法 35  >>> values ChainMap({'x': 3}, {'x': 2}, {'x': 1}) >>> values['x'] 3 >>> # Discard last mapping >>> values = values.parents >>> values['x'] 2 >>> # Discard last mapping >>> values = values.parents >>> values['x'] 1 >>> values ChainMap({'x': 1}) >>> 作为 ChainMap 的替代方案，我们可能会考虑利用字典的 update()方法将多个字典合并 在一起。例如： >>> a = {'x': 1, 'z': 3 } >>> b = {'y': 2, 'z': 4 } >>> merged = dict(b) >>> merged.update(a) >>> merged['x'] 1 >>> merged['y'] 2 >>> merged['z'] 3 >>> 这么做行得通，但这需要单独构建一个完整的字典对象（或者修改其中现有的一个字 典，这就破坏了原始数据） 。此外，如果其中任何一个原始字典做了修改，这个改变都 不会反应到合并后的字典中。例如： >>> a['x'] = 13 >>> merged['x'] 1 而 ChainMap 使用的就是原始的字典，因此它不会产生这种令人不悦的行为。示例如下： >>> a = {'x': 1, 'z': 3 } >>> b = {'y': 2, 'z': 4 } >>> merged = ChainMap(a, b) >>> merged['x'] 1 >>> a['x'] = 42 >>> merged['x'] # Notice change to merged dicts 42 >>> 36 第1章