内置标准库之数据结构

数据结构的概念很好理解，就是用来将数据组织在一起的结构。换句话说，数据结构是用来存储一系列关联数据的东西。在 Python 中有四种内建的数据结构，分别是 List、Tuple、Dictionary 以及 Set。大部分的应用程序不需要其他类型的数据结构，但若是真需要也有很多高级数据结构可供选择，例如 Collection、Array、Heapq、Bisect、Weakref、Copy 以及 Pprint。下面将介绍这些数据结构的用法，看看它们是如何帮助我们的应用程序的。

---

1. collections

1.1 deque

• Deque 是一种由队列结构扩展而来的双端队列(double-ended queue)，队列元素能够在队列两端添加或删除。因此它还被称为头尾连接列表(head-tail linked list)，尽管叫这个名字的还有另一个特殊的数据结构实现。

• Deque 支持线程安全的，经过优化的 append 和 pop 操作，在队列两端的相关操作都能够达到近乎 O(1) 的时间复杂度。虽然 list 也支持类似的操作，但是它是对定长列表的操作表现很不错，而当遇到 pop(0) 和 insert(0, v) 这样既改变了列表的长度又改变其元素位置的操作时，其复杂度就变为 O(n) 了。

In [1]: import collections

In [2]: lst = collections.deque()

In [3]: lst.append('B')

In [4]: lst.append('C')

In [5]: lst.appendleft('A')

In [6]: lst
Out[6]: deque(['A', 'B', 'C'])

In [7]: lst.insert(2, 'D')

In [8]: lstOut: deque(['A', 'B', 'D', 'C'])

In [9]: lst.pop()
Out[9]: 'C'

In [10]: lst.popleft()Out: 'A'

In [11]: lst
Out[11]: deque(['B', 'D'])

In [12]: lst.remove('B')

In [13]: lst.index('D')
Out[13]: 0

In [14]: lst
Out[14]: deque(['D'])

• rotate 是队列的旋转操作，Right rotate(正参数) 是将右端的元素移动到左端，而 Left rotate(负参数) 则相反。

In [1]: import collections

In [2]: lst = collections.deque(range(5))

In [3]: lst
Out[3]: deque([0, 1, 2, 3, 4])

In [4]: lst.rotate(3)

In [5]: lst
Out[5]: deque([2, 3, 4, 0, 1])

In [6]: lst.rotate(-3)

In [7]: lst
Out[7]: deque([0, 1, 2, 3, 4])

---

1.2 nametuple

• 顾名思义，nametuple 就是一个命名元组，可以使用名子的方式访问元素内容的 tuple 子类。以前，使用命名元组会创建一个类，需要我们事先定义好名称和属性。如下例所示，名称为 People 且存在三个属性，分别为 name、age、sex。

# 传统元组写法
In [1]: Bob = ('bob', 30, 'male')

In [2]: f'{Bob[0]} is {Bob[1]} years old {Bob[2]}'
Out[2]: 'bobis30 years old male'

# 使用命名元组的写法
In [1]: from collections import namedtuple

In [2]: People = namedtuple('People', 'name age sex')

In [3]: Bob = People('bob', 30, 'male')

In [4]: f'{Bob.name} is {Bob.age} years old {Bob.sex}'
Out[4]: 'bobis30 years old male'

---

1.3 Counter

• 如果你想统计一个单词在给定的序列中一共出现了多少次，诸如此类的操作就可以用到 Counter 这个 Python 自带的计数器实现。它不仅支持字符串、列表、字典等的计数统计，而且还是对计数进行叠加。

In [1]: from collections import Counter

In [2]: c = Counter('hello world')

In [3]: c.most_common(2)
Out[3]: [('l', 3), ('o', 2)]

In [4]: c = Counter(['a', 'b', 'c', 'a', 'b', 'a'])

In [5]: c
Out[5]: Counter({'a': 3, 'b': 2, 'c': 1})

In [6]: c.update(['a', 'b', 'a', 'c'])

In [7]: c
Out[7]: Counter({'a': 5, 'b': 3, 'c': 2})

In [8]: c = Counter({'a': 2, 'b': 5})

In [9]: c.update(['a', 'b'], a=3, c=1)

In [10]: c
Out[10]: Counter({'a': 6, 'b': 6, 'c': 1})

---

1.4 OrderedDict

• 未完，待续…

---

1.5 defaultdict

• 这个类型，除了在处理不存在的键的操作之外与普通的字典完全相同。当查找一个不存在的键操作发生时，它的 default_factory 会被调用，提供一个默认的值，并且将这对键值存储下来。其他的参数同普通的字典方法 dict() 一致，一个 defaultdict 的实例同内建 dict 一样拥有同样地操作。

• defaultdict 对象在当你希望使用它存放追踪数据的时候很有用。举个例子，假定你希望追踪一个单词在字符串中的位置，那么你可以这么做。

• 这里是选择 lists 或 sets 与 defaultdict 搭配取决于你的目的。使用 list 能够保存你插入元素的顺序，而使用 set 则不关心元素插入顺序，它会帮助消除重复元素。

from collections import defaultdict

s = "the quick brown fox jumps over the lazy dog"

words = s.split()
location = defaultdict(list)
for m, n in enumerate(words):
    location[n].append(m)
print(location)

defaultdict(<class 'list'>,
            {'brown': [2],
             'dog': [8],
             'fox': [3],
             'jumps': [4],
             'lazy': [7],
             'over': [5],
             'quick': [1],
             'the': [0, 6]})

• 另一种，创建 multidict 的方法。

s = "the quick brown fox jumps over the lazy dog"

d = {}
words = s.split()
for key, value in enumerate(words):
    d.setdefault(key, []).append(value)
print(d)

---

2. enum

• enum用于表示枚举类型，在 Python2 中需要使用第三方模块，而在 Python3.3 的时候将其加入了标准库中。

• 那它有什么意义呢？当我们定义一个常量，其中一个办法就是使用大写的变量通过整数来定义，如下所示这个 StatusesMixin 表示了四种状态。

class StatusesMixin:
    STATUSES = (
        STATUS_PENDING,
        STATUS_SUCCESS,
        STATUS_FAILURE,
        STATUS_FREEZING,
    ) = range(4)

• 而用 enum 的话，可以这样来写。使 StatusesMixin 这个类继承自 Enum，虽然看起来确实没有什么区别，但是它附带了很多非常有用的属性和功能。同时，还支持多种方法的访问，如下例所示。

In [1]: from enum import Enum

In [2]: class StatusesMixin(Enum):
   ...:     STATUSES = (
   ...:         STATUS_PENDING,
   ...:         STATUS_SUCCESS,
   ...:         STATUS_FAILURE,
   ...:         STATUS_FREEZING,
   ...:     ) = range(4)
   ...:

In [3]: st = StatusesMixin.STATUS_PENDING

In [4]: st
Out[4]: <StatusesMixin.STATUS_PENDING: 0>

In [5]: st.name, st.value
Out[5]: ('STATUS_PENDING', 0)

In [6]: StatusesMixin['STATUS_PENDING']
Out[6]: <StatusesMixin.STATUS_PENDING: 0>

In [7]: StatusesMixin(0)
Out[7]: <StatusesMixin.STATUS_PENDING: 0>

• 另外，这个 enum 还有一个非常有用的功能，那就是自动检测重复的值。

In [1]: from enum import Enum, unique

In [2]: @unique
   ...: class StatusType(Enum):
   ...:     PENDING = 1
   ...:     SUCCESS = 2
   ...:     FAILURE = 1
   ...:
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
<ipython-input-15-a0ddd2e335c7> in <module>()
      1 @unique
----> 2classStatusType(Enum):
      3     PENDING = 1
      4     SUCCESS = 2
      5     FAILURE = 1

~/envs/sansa-Qv8b9W1J/lib/python3.6/enum.pyinunique(enumeration)
    832                 ["%s -> %s" % (alias, name) for (alias, name) in duplicates])
    833         raise ValueError('duplicate values found in %r: %s' %
--> 834                 (enumeration, alias_details))
    835return enumeration
    836

ValueError: duplicate values found in <enum 'StatusType'>: FAILURE -> PENDING

---

3. bisect

• bisect模块能够提供保持 list 元素序列的支持，在向一个 list 插入元素的同时维持list是有序的。它使用了二分法完成大部分的工作。在某些情况下，这比重复的对一个 list 进行排序更为高效，并且对于一个较大的 list 来说，对每步操作维持其有序也比对其排序要高效。

• 这里面的 insort 其实是 insort_right 的别名，表示把值插入到已存在列表的右边。当然，也有 insort_left 方法，但是结果都是一样的。

In [1]: import random

In [2]: values = random.sample(range(100), 10)

In [3]: values
Out[3]: [98, 35, 9, 16, 41, 33, 10, 61, 0, 75]

In [4]: print('New  Pos  Contents')
   ...: print('---  ---  --------')
   ...: lst = []
   ...: for i in values:
   ...:     position = bisect.bisect(lst, i)
   ...:     bisect.insort(lst, i)
   ...:     print(f'{i:3}  {position:3}  {lst}')
   ...:
New  Pos  Contents
---  ---  --------
 98    0  [98]
 35    0  [35, 98]
  9    0  [9, 35, 98]
 16    1  [9, 16, 35, 98]
 41    3  [9, 16, 35, 41, 98]
 33    2  [9, 16, 33, 35, 41, 98]
 10    1  [9, 10, 16, 33, 35, 41, 98]
 61    6  [9, 10, 16, 33, 35, 41, 61, 98]
  0    0  [0, 9, 10, 16, 33, 35, 41, 61, 98]
 75    8  [0, 9, 10, 16, 33, 35, 41, 61, 75, 98]

In [5]: bisect.insort(lst, 31)

In [6]: lst
Out[6]: [0, 9, 10, 16, 31, 33, 35, 41, 61, 75, 98]

---

4. copy

在 Python 里面，赋值语句是对对象的引入。这里，我们开始介绍copy这个模块。

In [1]: a = [1, 2, 3]

In [2]: a[1] = a

In [3]: a
Out[3]: [1, [...], 3]

In [4]: a[1]
Out[4]: [1, [...], 3]

In [5]: a[1][1]
Out[5]: [1, [...], 3]

• 浅拷贝

对于 shallow copy 而言，它创建一个新的混合对象，并且将原对象中其他对象的引用插入新对象。

从下例中可以看出，改变 a 的时候，c 的值也发生了改变，这是因为赋值只是一个对象的引入而并没有创建新的对象。

In [1]: a = [1, 2]

In [2]: c = a

In [3]: id(a), id(c)
Out[3]: (4495167432, 4495167432)

In [4]: a.append(3)

In [5]: c
Out[5]: [1, 2, 3]

如果不希望c的值发生改变，可以使用copy.copy来实现浅拷贝。浅拷贝就是创建一个新的对象，赋值原有对象的一个引用。但是浅拷贝只会拷贝父对象，而不会拷贝对象内部的子对象。

In [6]: d = copy.copy(a)

In [7]: d
Out[7]: [1, 2, 3]

In [8]: id(a), id(d)
Out[8]: (4495167432, 4495159368)

In [9]: a.append(4)

In [10]: d
Out[10]: [1, 2, 3]

In [11]: a
Out[11]: [1, 2, 3, 4]

• 深拷贝

对于 deep copy 而言，它创建一个新的对象，并且递归地复制源对象中的其他对象并插入新的对象中。

想要全部都拷贝的话，就需要使用 copy.deepcopy 来实现深拷贝。需要注意的是，在 dict 中自带有浅拷贝的方法 copy，效果和 copy.copy 一样。

In [1]: a = {1: [1, 2, 3]}

In [2]: b = a.copy()

In [3]: id(a), id(b)
Out: (4496796408, 4496853320)

In [4]: a[1].append(4)

In [5]: a, b
Out[5]: ({1: [1, 2, 3, 4]}, {1: [1, 2, 3, 4]})

In [6]: e = copy.deepcopy(a)

In [7]: a, e
Out[7]: ({1: [1, 2, 3, 4]}, {1: [1, 2, 3, 4]})

In [8]: a[1].append(5)

In [9]: a, e
Out[9]: ({1: [1, 2, 3, 4, 5]}, {1: [1, 2, 3, 4]})

假定我有两个类，名为Manager和Graph，每个Graph包含了一个指向其manager的引用，而每个Manager有一个指向其管理的Graph的集合，现在我们有两个任务需要完成。

第一个任务，就是复制一个graph实例，使用deepcopy，但其manager指向为原graph的 manager。第二个任务，就是复制一个manager，完全创建新manager，但拷贝原有的所有graph。

import weakref, copy

class Graph(object):
    def __init__(self, manager=None):
        self.manager = None if manager is None else weakref.ref(manager)
    def __deepcopy__(self, memodict):
        manager = self.manager()
        return Graph(memodict.get(id(manager), manager))

class Manager(object):
    def __init__(self, graphs=[]):
        self.graphs = graphs
        for g in self.graphs:
            g.manager = weakref.ref(self)

a = Manager([Graph(), Graph()])
b = copy.deepcopy(a)

if [g.manager() is b for g in b.graphs]:
    print(True)  # True

if copy.deepcopy(a.graphs[0]).manager() is a:
    print(True)  # True

---

5. array

• array模块定义了一个很像list的新对象类型，不同之处在于它限定了这个类型只能装一种类型的元素。array元素的类型是在创建并使用的时候确定的。

• 如果你的程序需要优化内存的使用，并且你确定你希望在list中存储的数据都是同样类型的，那么使用array模块很合适。举个例子，如果需要存储一千万个整数，如果用list，那么你至少需要160MB的存储空间，然而如果使用array，你只需要40MB。但虽然说能够节省空间，array上几乎没有什么基本操作能够比在list上更快。

• 在使用array进行计算的时候，需要特别注意那些创建list的操作。例如，使用列表推导式的时候，会将array整个转换为list，使得存储空间膨胀。一个可行的替代方案是使用生成器表达式创建新的array。

Type code	C Type	Python Type	Minimum size in bytes
b	signed char	Int	1
B	unsigned char	Int	1
u	Py_UNICODE	Character	2
h	signed short	Int	2
H	unsigned short	Int	2
i	signed int	Int	2
I	unsigned int	Int	2
l	signed long	Int	4
L	unsigned long	Int	4
q	signed long	Int	8
Q	unsigned long	Int	8
f	Float	Float	4
d	Double	Float	8

import array

a = array.array("i", [1,2,3,4,5])
b = array.array(a.typecode, (2*x for x in a))

In [1]: a
Out[1]: array('i', [1, 2, 3, 4, 5])

In [2]: b
Out[2]: array('i', [2, 4, 6, 8, 10])

那么什么时候使用array呢？是当你在考虑计算的因素之外，还需要得到一个像C语言里一样统一元素类型的数组时。

---

8. heapq

• heapq模块使用一个用堆实现的优先级队列。堆是一种简单的有序列表，并且置入了堆的相关规则。

• 堆是一种树形的数据结构，树上的子节点与父节点之间存在顺序关系。二叉堆(binary heap)能够用一个经过组织的列表或数组结构来标识，在这种结构中，元素N的子节点的序号为2*N+1和2*N+2(下标始于0)。简单来说，这个模块中的所有函数都假设序列是有序的，所以序列中的第一个元素(seq[0])是最小的，序列的其他部分构成一个二叉树，并且seq[i]节点的子节点分别为seq[2*i+1]以及seq[2*i+2]。当对序列进行修改时，相关函数总是确保子节点大于等于父节点。

import heapq

heap = []

for value in [20, 10, 30, 50, 40]:
    heapq.heappush(heap, value)

while heap:
    print heapq.heappop(heap)

• 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]

• 两个函数也能够通过一个键参数使用更为复杂的数据结构，如下所示。

import heapq

portfolio = [
{'name': 'IBM', 'shares': 100, 'price': 91.1},
{'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'])

print(cheap)
# [{'price': 16.35, 'name': 'YHOO', 'shares': 45},
# {'price': 21.09, 'name': 'FB', 'shares': 200}, {'price': 31.75, 'name': 'HPQ', 'shares': 35}]

print(expensive)
# [{'price': 543.22, 'name': 'AAPL', 'shares': 50}, {'price': 115.65, 'name': 'ACME',
# 'shares': 75}, {'price': 91.1, 'name': 'IBM', 'shares': 100}]

• 来看看如何实现一个根据给定优先级进行排序，并且每次pop操作都返回优先级最高的元素的队列例子。

import heapq

class Item:
    def __init__(self, name):
        self.name = name

    def __repr__(self):
        return 'Item({!r})'.format(self.name)

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]

q = PriorityQueue()
q.push(Item('foo'), 1)
q.push(Item('bar'), 5)
q.push(Item('spam'), 4)
q.push(Item('grok'), 1)

print q.pop()  # Item('bar')
print q.pop()  # Item('spam')
print q.pop()  # Item('foo')
print q.pop()  # Item('grok')

---

9. pprint

• pprint模块能够提供比较优雅的数据结构打印方式，如果你需要打印一个结构较为复杂，层次较深的字典或是JSON对象时，使用pprint能够提供较好的打印结果。

• 假定你需要打印一个矩阵，当使用普通的print时，你只能打印出普通的列表，不过如果使用pprint，你就能打出漂亮的矩阵结构。

import pprint

matrix = [ [1,2,3], [4,5,6], [7,8,9] ]
a = pprint.PrettyPrinter(width=20)
a.pprint(matrix)

[[1, 2, 3],
 [4, 5, 6],
 [7, 8, 9]]