Python编程中3个常用的数据结构和算法
Python内置了许多非常有用的数据结构，比如列表(list)、集合(set)以及字典(dictionary)。就绝大部分情况而言，我们可以直接使用这些数据结构。但是，通常我们还需要考虑比如搜索、排序、排列以及筛选等这一类常见的问题。
本篇文章将介绍3种常见的数据结构和同数据有关的算法。此外，在collections模块中也包含了针对各种数据结构的解决方案。
1. 将序列分解为单独的变量
(1) 问题
我们有一个包含 N 个元素的元组或序列，现在想将它分解为N个单独的变量。
(2) 解决方案
任何序列(或可迭代的对象)都可以通过一个简单的赋值操作来分解为单独的变量。唯一的要求是变量的总数和结构要与序列相吻合。例如：
1. >>> p = (4, 5)
2. >>> x, y = p
3. >>> x
4. 4
5. >>> y
6. 5
7. >>>
8. >>> data = [ 'ACME', 50, 91.1, (2012, 12, 21) ]
9. >>> name, shares, price, date = data
10. >>> name
11. 'ACME'
12. >>> date
13. (2012, 12, 21)
14. >>> name, shares, price, (year, mon, day) = data
15. >>> name
16. 'ACME'
17. >>> year
18. 2012
19. >>> mon
20. 12
21. >>> day
22. 21
23. >>>
如果元素的数量不匹配，将得到一个错误提示。例如：
1. >>> p = (4, 5)
2. >>> x, y, z = p
3. Traceback (most recent call last):
4. File "<stdin>", line 1, in <module>
5. ValueError: need more than 2 values to unpack
6. >>>
(3) 讨论
实际上不仅仅只是元组或列表，只要对象恰好是可迭代的，那么就可以执行分解操作。这包括字符串、文件、迭代器以及生成器。比如：
1. >>> s = 'Hello'
2. >>> a, b, c, d, e = s
3. >>> a
4. 'H'
5. >>> b
6. 'e'
7. >>> e
8. 'o'
9. >>>
当做分解操作时，有时候可能想丢弃某些特定的值。Python并没有提供特殊的语法来实现这一点，但是通常可以选一个用不到的变量名，以此来作为要丢弃的值的名称。例如：
1. >>> data = [ 'ACME', 50, 91.1, (2012, 12, 21) ]
2. >>> _, shares, price, _ = data
3. >>> shares
4. 50
5. >>> price
6. 91.1
7. >>>
但是请确保选择的变量名没有在其他地方用到过。
2. 从任意长度的可迭代对象中分解元素
(1) 问题
需要从某个可迭代对象中分解出N个元素，但是这个可迭代对象的长度可能超过N，这会导致出现“分解的值过多(too many values to unpack)”的异常。
(2) 解决方案
Python的“表达式”可以用来解决这个问题。例如，假设开设了一门课程，并决定在期末的作业成绩中去掉第一个和最后一个，只对中间剩下的成绩做平均分统计。如果只有4个成绩，也许可以简单地将4个都分解出来，但是如果有24个呢?表达式使这一切都变得简单：
1. def drop_first_last(grades):
2. first, *middle, last = grades
3. return avg(middle)
另一个用例是假设有一些用户记录，记录由姓名和电子邮件地址组成，后面跟着任意数量的电话号码。则可以像这样分解记录：
1. >>> record = ('Dave', 'dave@example.com', '773-555-1212', '847-555-1212')
2. >>> name, email, *phone_numbers = user_record
3. >>> name
4. 'Dave'
5. >>> email
6. 'dave@example.com'
7. >>> phone_numbers
8. ['773-555-1212', '847-555-1212']
9. >>>
不管需要分解出多少个电话号码(甚至没有电话号码)，变量phone_numbers都一直是列表，而这是毫无意义的。如此一来，对于任何用到了变量phone_numbers的代码都不必对它可能不是一个列表的情况负责，或者额外做任何形式的类型检查。
由*修饰的变量也可以位于列表的第一个位置。例如，比方说用一系列的值来代表公司过去8个季度的销售额。如果想对最近一个季度的销售额同前7个季度的平均值做比较，可以这么做：
1. *trailing_qtrs, current_qtr = sales_record
2. trailing_avg = sum(trailing_qtrs) / len(trailing_qtrs)
3. return avg_comparison(trailing_avg, current_qtr)
从Python解释器的角度来看，这个操作是这样的：
1. >>> *trailing, current = [10, 8, 7, 1, 9, 5, 10, 3]
2. >>> trailing
3. [10, 8, 7, 1, 9, 5, 10]
4. >>> current
5. 3
(3) 讨论
对于分解未知或任意长度的可迭代对象，这种扩展的分解操作可谓是量身定做的工具。通常，这类可迭代对象中会有一些已知的组件或模式(例如，元素1之后的所有内容都是电话号码)，利用*表达式分解可迭代对象使得开发者能够轻松利用这些模式，而不必在可迭代对象中做复杂花哨的操作才能得到相关的元素。
*式的语法在迭代一个变长的元组序列时尤其有用。例如，假设有一个带标记的元组序列：
1. records = [
2. ('foo', 1, 2),
3. ('bar', 'hello'),
4. ('foo', 3, 4),
5. ]
6. def do_foo(x, y):
7. print('foo', x, y)
8. def do_bar(s):
9. print('bar', s)
10. for tag, *args in records:
11. if tag == 'foo':
12. do_foo(*args)
13. elif tag == 'bar':
14. do_bar(*args)
当和某些特定的字符串处理操作相结合，比如做拆分(splitting)操作时，这种*式的语法所支持的分解操作也非常有用。例如：
1. >>> line = 'nobody:*:-2:-2:Unprivileged User:/var/empty:/usr/bin/false'
2. >>> uname, *fields, homedir, sh = line.split(':')
3. >>> uname
4. 'nobody'
5. >>> homedir
6. '/var/empty'
7. >>> sh
8. '/usr/bin/false'
9. >>>
有时候可能想分解出某些值然后丢弃它们。在分解的时候，不能只是指定一个单独的*，但是可以使用几个常用来表示待丢弃值的变量名，比如_或者ign(ignored)。例如：
1. >>> record = ('ACME', 50, 123.45, (12, 18, 2012))
2. >>> name, *_, (*_, year) = record
3. >>> name
4. 'ACME'
5. >>> year
6. 2012
7. >>>
*分解操作和各种函数式语言中的列表处理功能有着一定的相似性。例如，如果有一个列表，可以像下面这样轻松将其分解为头部和尾部：
1. >>> items = [1, 10, 7, 4, 5, 9]
2. >>> head, *tail = items
3. >>> head
4. 1
5. >>> tail
6. [10, 7, 4, 5, 9]
7. >>>
在编写执行这类拆分功能的函数时，人们可以假设这是为了实现某种精巧的递归算法。例如：
1. >>> def sum(items):
2. ... head, *tail = items
3. ... return head + sum(tail) if tail else head
4. ...
5. >>> sum(items)
6. 36
7. >>>
但是请注意，递归真的不算是Python的强项，这是因为其内在的递归限制所致。因此，最后一个例子在实践中没太大的意义，只不过是一点学术上的好奇罢了。
3. 保存最后N个元素
(1) 问题
我们希望在迭代或是其他形式的处理过程中对最后几项记录做一个有限的历史记录统计。
(2) 解决方案
保存有限的历史记录可算是collections.deque的完美应用场景了。例如，下面的代码对一系列文本行做简单的文本匹配操作，当发现有匹配时就输出当前的匹配行以及最后检查过的N行文本。
1. from collections import deque
2. def search(lines, pattern, history=5):
3. previous_lines = deque(maxlen=history)
4. for line in lines:
5. if pattern in line:
6. yield line, previous_lines
7. previous_lines.append(line)
8. # Example use on a file
9. if __name__ == '__main__':
10. with open('somefile.txt') as f:
11. for line, prevlines in search(f, 'python', 5):
12. for pline in prevlines:
13. print(pline, end='')
14. print(line, end='')
15. print('-'*20)
(3) 讨论
如同上面的代码片段中所做的一样，当编写搜索某项记录的代码时，通常会用到含有yield关键字的生成器函数。这将处理搜索过程的代码和使用搜索结果的代码成功解耦开来。如果对生成器还不熟悉，请参见4.3节。
deque(maxlen=N)创建了一个固定长度的队列。当有新记录加入而队列已满时会自动移除最老的那条记录。例如：
1. >>> q = deque(maxlen=3)
2. >>> q.append(1)
3. >>> q.append(2)
4. >>> q.append(3)
5. >>> q
6. deque([1, 2, 3], maxlen=3)
7. >>> q.append(4)
8. >>> q
9. deque([2, 3, 4], maxlen=3)
10. >>> q.append(5)
11. >>> q
12. deque([3, 4, 5], maxlen=3)
尽管可以在列表上手动完成这样的操作(append、del)，但队列这种解决方案要优雅得多，运行速度也快得多。
更普遍的是，当需要一个简单的队列结构时，deque可祝你一臂之力。如果不指定队列的大小，也就得到了一个无界限的队列，可以在两端执行添加和弹出操作，例如：
1. >>> q = deque()
2. >>> q.append(1)
3. >>> q.append(2)
4. >>> q.append(3)
5. >>> q
6. deque([1, 2, 3])
7. >>> q.appendleft(4)
8. >>> q
9. deque([4, 1, 2, 3])
10. >>> q.pop()
11. 3
12. >>> q
13. deque([4, 1, 2])
14. >>> q.popleft()
15. 4
从队列两端添加或弹出元素的复杂度都是O(1)。这和列表不同，当从列表的头部插入或移除元素时，列表的复杂度为O(N)。
