数据结构
数据结构的概念很好理解，就是用来将数据组织在一起的结构。换句话说，数据结构是用来存储一系列关联数据的东西。在Python中有四种内建的数据结构，分别是List、Tuple、Dictionary以及Set。大部分的应用程序不需要其他类型的数据结构，但若是真需要也有很多高级数据结构可供选择，例如Collection、Array、Heapq、Bisect、Weakref、Copy以及Pprint。本文将介绍这些数据结构的用法，看看它们是如何帮助我们的应用程序的。
关于四种内建数据结构的使用方法很简单，并且网上有很多参考资料，因此本文将不会讨论它们。
1. Collections
collections模块包含了内建类型之外的一些有用的工具，例如Counter、defaultdict、OrderedDict、deque以及nametuple。其中Counter、deque以及defaultdict是最常用的类。
1.1 Counter()
如果你想统计一个单词在给定的序列中一共出现了多少次，诸如此类的操作就可以用到Counter。来看看如何统计一个list中出现的item次数：
from collections import Counter
li = ["Dog", "Cat", "Mouse", 42, "Dog", 42, "Cat", "Dog"]
a = Counter(li)
print a # Counter({'Dog': 3, 42: 2, 'Cat': 2, 'Mouse': 1})
若要统计一个list中不同单词的数目，可以这么用：
from collections import Counter
li = ["Dog", "Cat", "Mouse", 42, "Dog", 42, "Cat", "Dog"]
a = Counter(li)
print a # Counter({'Dog': 3, 42: 2, 'Cat': 2, 'Mouse': 1})
print len(set(li)) # 4
如果需要对结果进行分组，可以这么做：
from collections import Counter
li = ["Dog", "Cat", "Mouse","Dog","Cat", "Dog"]
a = Counter(li)
print a # Counter({'Dog': 3, 'Cat': 2, 'Mouse': 1})
print "{0} : {1}".format(a.values(),a.keys()) # [1, 3, 2] : ['Mouse', 'Dog', 'Cat']
print(a.most_common(3)) # [('Dog', 3), ('Cat', 2), ('Mouse', 1)]
以下的代码片段找出一个字符串中出现频率最高的单词，并打印其出现次数。
import re
from collections import Counter
string = """ Lorem ipsum dolor sit amet, consectetur
adipiscing elit. Nunc ut elit id mi ultricies
adipiscing. Nulla facilisi. Praesent pulvinar,
sapien vel feugiat vestibulum, nulla dui pretium orci,
non ultricies elit lacus quis ante. Lorem ipsum dolor
sit amet, consectetur adipiscing elit. Aliquam
pretium ullamcorper urna quis iaculis. Etiam ac massa
sed turpis tempor luctus. Curabitur sed nibh eu elit
mollis congue. Praesent ipsum diam, consectetur vitae
ornare a, aliquam a nunc. In id magna pellentesque
tellus posuere adipiscing. Sed non mi metus, at lacinia
augue. Sed magna nisi, ornare in mollis in, mollis
sed nunc. Etiam at justo in leo congue mollis.
Nullam in neque eget metus hendrerit scelerisque
eu non enim. Ut malesuada lacus eu nulla bibendum
id euismod urna sodales. """
words = re.findall(r'\w+', string) #This finds words in the document
lower_words = [word.lower() for word in words] #lower all the words
word_counts = Counter(lower_words) #counts the number each time a word appears
print word_counts
# Counter({'elit': 5, 'sed': 5, 'in': 5, 'adipiscing': 4, 'mollis': 4, 'eu': 3,
# 'id': 3, 'nunc': 3, 'consectetur': 3, 'non': 3, 'ipsum': 3, 'nulla': 3, 'pretium':
# 2, 'lacus': 2, 'ornare': 2, 'at': 2, 'praesent': 2, 'quis': 2, 'sit': 2, 'congue': 2, 'amet': 2,
# 'etiam': 2, 'urna': 2, 'a': 2, 'magna': 2, 'lorem': 2, 'aliquam': 2, 'ut': 2, 'ultricies': 2, 'mi': 2,
# 'dolor': 2, 'metus': 2, 'ac': 1, 'bibendum': 1, 'posuere': 1, 'enim': 1, 'ante': 1, 'sodales': 1, 'tellus': 1,
# 'vitae': 1, 'dui': 1, 'diam': 1, 'pellentesque': 1, 'massa': 1, 'vel': 1, 'nullam': 1, 'feugiat': 1, 'luctus': 1,
# 'pulvinar': 1, 'iaculis': 1, 'hendrerit': 1, 'orci': 1, 'turpis': 1, 'nibh': 1, 'scelerisque': 1, 'ullamcorper': 1,
# 'eget': 1, 'neque': 1, 'euismod': 1, 'curabitur': 1, 'leo': 1, 'sapien': 1, 'facilisi': 1, 'vestibulum': 1, 'nisi': 1,
# 'justo': 1, 'augue': 1, 'tempor': 1, 'lacinia': 1, 'malesuada': 1})
1.2 Deque
Deque是一种由队列结构扩展而来的双端队列(double-ended queue)，队列元素能够在队列两端添加或删除。因此它还被称为头尾连接列表(head-tail linked list)，尽管叫这个名字的还有另一个特殊的数据结构实现。
Deque支持线程安全的，经过优化的append和pop操作，在队列两端的相关操作都能够达到近乎O(1)的时间复杂度。虽然list也支持类似的操作，但是它是对定长列表的操作表现很不错，而当遇到pop(0)和insert(0, v)这样既改变了列表的长度又改变其元素位置的操作时，其复杂度就变为O(n)了。
来看看相关的比较结果：
import time
from collections import deque
num = 100000
def append(c):
for i in range(num):
c.append(i)
def appendleft(c):
if isinstance(c, deque):
for i in range(num):
c.appendleft(i)
else:
for i in range(num):
c.insert(0, i)
def pop(c):
for i in range(num):
c.pop()
def popleft(c):
if isinstance(c, deque):
for i in range(num):
c.popleft()
else:
for i in range(num):
c.pop(0)
for container in [deque, list]:
for operation in [append, appendleft, pop, popleft]:
c = container(range(num))
start = time.time()
operation(c)
elapsed = time.time() - start
print "Completed {0}/{1} in {2} seconds: {3} ops/sec".format(
container.__name__, operation.__name__, elapsed, num / elapsed)
# Completed deque/append in 0.0250000953674 seconds: 3999984.74127 ops/sec
# Completed deque/appendleft in 0.0199999809265 seconds: 5000004.76838 ops/sec
# Completed deque/pop in 0.0209999084473 seconds: 4761925.52225 ops/sec
# Completed deque/popleft in 0.0199999809265 seconds: 5000004.76838 ops/sec
# Completed list/append in 0.0220000743866 seconds: 4545439.17637 ops/sec
# Completed list/appendleft in 21.3209998608 seconds: 4690.21155917 ops/sec
# Completed list/pop in 0.0240001678467 seconds: 4166637.52682 ops/sec
# Completed list/popleft in 4.01799988747 seconds: 24888.0046791 ops/sec
另一个例子是执行基本的队列操作：
from collections import deque
q = deque(range(5))
q.append(5)
q.appendleft(6)
print q
print q.pop()
print q.popleft()
print q.rotate(3)
print q
print q.rotate(-1)
print q
# deque([6, 0, 1, 2, 3, 4, 5])
# 5
# 6
# None
# deque([2, 3, 4, 0, 1])
# None
# deque([3, 4, 0, 1, 2])
译者注:rotate是队列的旋转操作，Right rotate(正参数)是将右端的元素移动到左端，而Left rotate(负参数)则相反。
1.3 Defaultdict
这个类型除了在处理不存在的键的操作之外与普通的字典完全相同。当查找一个不存在的键操作发生时，它的default_factory会被调用，提供一个默认的值，并且将这对键值存储下来。其他的参数同普通的字典方法dict()一致，一个defaultdict的实例同内建dict一样拥有同样地操作。
defaultdict对象在当你希望使用它存放追踪数据的时候很有用。举个例子，假定你希望追踪一个单词在字符串中的位置，那么你可以这么做：
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(<type 'list'>, {'brown': [2], 'lazy': [7], 'over': [5], 'fox': [3],
# 'dog': [8], 'quick': [1], 'the': [0, 6], 'jumps': [4]})
是选择lists或sets与defaultdict搭配取决于你的目的，使用list能够保存你插入元素的顺序，而使用set则不关心元素插入顺序，它会帮助消除重复元素。
from collections import defaultdict
s = "the quick brown fox jumps over the lazy dog"
words = s.split()
location = defaultdict(set)
for m, n in enumerate(words):
location[n].add(m)
print location
# defaultdict(<type 'set'>, {'brown': set([2]), 'lazy': set([7]),
# 'over': set([5]), 'fox': set([3]), 'dog': set([8]), 'quick': set([1]),
# 'the': set([0, 6]), 'jumps': set([4])})
另一种创建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
# {0: ['the'], 1: ['quick'], 2: ['brown'], 3: ['fox'], 4: ['jumps'], 5: ['over'], 6: ['the'], 7: ['lazy'], 8: ['dog']}
一个更复杂的例子：
class Example(dict):
def __getitem__(self, item):
try:
return dict.__getitem__(self, item)
except KeyError:
value = self[item] = type(self)()
return value
a = Example()
a[1][2][3] = 4
a[1][3][3] = 5
a[1][2]['test'] = 6
print a # {1: {2: {'test': 6, 3: 4}, 3: {3: 5}}}
2. Array
array模块定义了一个很像list的新对象类型，不同之处在于它限定了这个类型只能装一种类型的元素。array元素的类型是在创建并使用的时候确定的。
如果你的程序需要优化内存的使用，并且你确定你希望在list中存储的数据都是同样类型的，那么使用array模块很合适。举个例子，如果需要存储一千万个整数，如果用list，那么你至少需要160MB的存储空间，然而如果使用array，你只需要40MB。但虽然说能够节省空间，array上几乎没有什么基本操作能够比在list上更快。
在使用array进行计算的时候，需要特别注意那些创建list的操作。例如，使用列表推导式(list comprehension)的时候，会将array整个转换为list，使得存储空间膨胀。一个可行的替代方案是使用生成器表达式创建新的array。看代码：
import array
a = array.array("i", [1,2,3,4,5])
b = array.array(a.typecode, (2*x for x in a))
因为使用array是为了节省空间，所以更倾向于使用in-place操作。一种更高效的方法是使用enumerate：
import array
a = array.array("i", [1,2,3,4,5])
for i, x in enumerate(a):
a[i] = 2*x
对于较大的array，这种in-place修改能够比用生成器创建一个新的array至少提升15%的速度。
那么什么时候使用array呢？是当你在考虑计算的因素之外，还需要得到一个像C语言里一样统一元素类型的数组时。
import array
from timeit import Timer
def arraytest():
a = array.array("i", [1, 2, 3, 4, 5])
b = array.array(a.typecode, (2 * x for x in a))
def enumeratetest():
a = array.array("i", [1, 2, 3, 4, 5])
for i, x in enumerate(a):
a[i] = 2 * x
if __name__=='__main__':
m = Timer("arraytest()", "from __main__ import arraytest")
n = Timer("enumeratetest()", "from __main__ import enumeratetest")
print m.timeit() # 5.22479210582
print n.timeit() # 4.34367196717
