數據結構
數據結構的概念很好理解，就是用來將數據組織在一起的結構。換句話說，數據結構是用來存儲一系列關聯數據的東西。在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
