11.7. 用于操作列表的工具

许多对于数据结构的需求可以通过内置列表类型来满足。 但是，有时也会需要具有不同效费比的替代实现。

array 模块提供了一种 array() 对象，它类似于列表，但只能存储类型一致的数据且存储密集更高。 下面的例子演示了一个以两个字节为存储单元的无符号二进制数值的数组 (类型码为 "H")，而对于普通列表来说，每个条目存储为标准 Python 的 int 对象通常要占用16 个字节:

  1. >>> from array import array
  2. >>> a = array('H', [4000, 10, 700, 22222])
  3. >>> sum(a)
  4. 26932
  5. >>> a[1:3]
  6. array('H', [10, 700])

collections 模块提供了一种 deque() 对象，它类似于列表，但从左端添加和弹出的速度较快，而在中间查找的速度较慢。 此种对象适用于实现队列和广度优先树搜索:

  1. >>> from collections import deque
  2. >>> d = deque(["task1", "task2", "task3"])
  3. >>> d.append("task4")
  4. >>> print("Handling", d.popleft())
  5. Handling task1
  1. unsearched = deque([starting_node])
  2. def breadth_first_search(unsearched):
  3.     node = unsearched.popleft()
  4.     for m in gen_moves(node):
  5.         if is_goal(m):
  6.             return m
  7.         unsearched.append(m)

在替代的列表实现以外，标准库也提供了其他工具，例如 bisect 模块具有用于操作有序列表的函数:

  1. >>> import bisect
  2. >>> scores = [(100, 'perl'), (200, 'tcl'), (400, 'lua'), (500, 'python')]
  3. >>> bisect.insort(scores, (300, 'ruby'))
  4. >>> scores
  5. [(100, 'perl'), (200, 'tcl'), (300, 'ruby'), (400, 'lua'), (500, 'python')]

heapq 模块提供了基于常规列表来实现堆的函数。 最小值的条目总是保持在位置零。 这对于需要重复访问最小元素而不希望运行完整列表排序的应用来说非常有用:

  1. >>> from heapq import heapify, heappop, heappush
  2. >>> data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
  3. >>> heapify(data)                      # rearrange the list into heap order
  4. >>> heappush(data, -5)                 # add a new entry
  5. >>> [heappop(data) for i in range(3)]  # fetch the three smallest entries
  6. [-5, 0, 1]