對數學家來說，Python這門語言有著很多吸引他們的地方。舉幾個例子：對于tuple、lists以及sets等容器的支持，使用與傳統數學類似的符號標記方式，還有列表推導式這樣與數學中集合推導式和集的結構式(set-builder notation)很相似的語法結構。
另外一些很吸引數學愛好者的特性是Python中的iterator(迭代器)、generator(生成器)以及相關的itertools包。這些工具幫助人們能夠很輕松的寫出處理諸如無窮序列(infinite sequence)、隨機過程(stochastic processes)、遞推關系(recurrence relations)以及組合結構(combinatorial structures)等數學對象的優雅代碼。本文將涵蓋我關于迭代器和生成器的一些筆記，并且有一些我在學習過程中積累的相關經驗。
Iterators
迭代器(Iterator)是一個可以對集合進行迭代訪問的對象。通過這種方式不需要將集合全部載入內存中，也正因如此，這種集合元素幾乎可以是無限的。你可以在Python官方文檔的“迭代器類型(Iterator Type)”部分找到相關文檔。
讓我們對定義的描述再準確些，如果一個對象定義了__iter__方法，并且此方法需要返回一個迭代器，那么這個對象就是可迭代的(iterable)。而迭代器是指實現了__iter__以及next(在Python 3中為__next__)兩個方法的對象，前者返回一個迭代器對象，而后者返回迭代過程的下一個集合元素。據我所知，迭代器總是在__iter__方法中簡單的返回自己(self)，因為它們正是自己的迭代器。
一般來說，你應該避免直接調用__iter__以及next方法。而應該使用for或是列表推導式(list comprehension)，這樣的話Python能夠自動為你調用這兩個方法。如果你需要手動調用它們，請使用Python的內建函數iter以及next，并且把目標迭代器對象或是集合對象當做參數傳遞給它們。舉個例子，如果c是一個可迭代對象，那么你可以使用iter(c)來訪問，而不是c.__iter__()，類似的，如果a是一個迭代器對象，那么請使用next(a)而不是a.next()來訪問下一個元素。與之相類似的還有len的用法。
說到len，值得注意的是對迭代器而言沒必要去糾結length的定義。所以它們通常不會去實現__len__方法。如果你需要計算容器的長度，那么必須得手動計算，或者使用sum。本文末，在itertools模塊之后會給出一個例子。
有一些可迭代對象并不是迭代器，而是使用其他對象作為迭代器。舉個例子，list對象是一個可迭代對象，但并不是一個迭代器(它實現了__iter__但并未實現next)。通過下面的例子你可以看到list是如何使用迭代器listiterator的。同時值得注意的是list很好地定義了length屬性，而listiterator卻沒有。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
>>> a = [1, 2]>>> type(a)<type 'list'>>>> type(iter(a))<type 'listiterator'>>>> it = iter(a)>>> next(it)1>>> next(it)2>>> next(it)Traceback (most recent call last): File "<stdin>", line 1, in <module>StopIteration>>> len(a)2>>> len(it)Traceback (most recent call last): File "<stdin>", line 1, in <module>TypeError: object of type 'listiterator' has no len() |
當迭代結束卻仍然被繼續迭代訪問時，Python解釋器會拋出StopIteration異常。然而，前述中提到迭代器可以迭代一個無窮集合，所以對于這種迭代器就必須由用戶負責確保不會造成無限循環的情況，請看下面的例子：
|
1
2
3
4
5
6
7
8
9
10
|
class count_iterator(object): n = 0 def __iter__(self): return self def next(self): y = self.n self.n += 1 return y |
下面是例子，注意最后一行試圖將一個迭代器對象轉為list，這將導致一個無限循環，因為這種迭代器對象將不會停止。
|
1
2
3
4
5
6
7
8
9
10
|
>>> counter = count_iterator()>>> next(counter)0>>> next(counter)1>>> next(counter)2>>> next(counter)3>>> list(counter) # This will result in an infinite loop! |
最后，我們將修改以上的程序：如果一個對象沒有__iter__方法但定義了__getitem__方法，那么這個對象仍然是可迭代的。在這種情況下，當Python的內建函數iter將會返回一個對應此對象的迭代器類型，并使用__getitem__方法遍歷list的所有元素。如果StopIteration或IndexError異常被拋出，則迭代停止。讓我們看看以下的例子：
|
1
2
3
4
5
6
|
class SimpleList(object): def __init__(self, *items): self.items = items def __getitem__(self, i): return self.items[i] |
用法在此：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
>>> a = SimpleList(1, 2, 3)>>> it = iter(a)>>> next(it)1>>> next(it)2>>> next(it)3>>> next(it)Traceback (most recent call last): File "<stdin>", line 1, in <module>StopIteration |
現在來看一個更有趣的例子：根據初始條件使用迭代器生成Hofstadter Q序列。Hofstadter在他的著作《G?del, Escher, Bach: An Eternal Golden Braid》中首次提到了這個嵌套的序列，并且自那時候開始關于證明這個序列對所有n都成立的問題就開始了。以下的代碼使用一個迭代器來生成給定n的Hofstadter序列，定義如下：
|
1
|
Q(n)=Q(n-Q(n-1))+Q(n?Q(n?2)) |
給定一個初始條件，舉個例子，qsequence([1, 1])將會生成H序列。我們使用StopIteration異常來指示序列不能夠繼續生成了，因為需要一個合法的下標索引來生成下一個元素。例如如果初始條件是[1,2]，那么序列生成將立即停止。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class qsequence(object): def __init__(self, s): self.s = s[:] def next(self): try: q = self.s[-self.s[-1]] + self.s[-self.s[-2]] self.s.append(q) return q except IndexError: raise StopIteration() def __iter__(self): return self def current_state(self): return self.s |
用法在此：
|
1
2
3
4
5
6
7
|
>>> Q = qsequence([1, 1])>>> next(Q)2>>> next(Q)3>>> [next(Q) for __ in xrange(10)][3, 4, 5, 5, 6, 6, 6, 8, 8, 8] |
生成器(Generator)是一種用更簡單的函數表達式定義的生成器。說的更具體一些，在生成器內部會用到yield表達式。生成器不會使用return返回值，而當需要時使用yield表達式返回結果。Python的內在機制能夠幫助記住當前生成器的上下文，也就是當前的控制流和局部變量的值等。每次生成器被調用都適用yield返回迭代過程中的下一個值。__iter__方法是默認實現的，意味著任何能夠使用迭代器的地方都能夠使用生成器。下面這個例子實現的功能同上面迭代器的例子一樣，不過代碼更緊湊，可讀性更強。
|
1
2
3
4
5
|
def count_generator(): n = 0 while True: yield n n += 1 |
來看看用法：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
>>> counter = count_generator()>>> counter<generator object count_generator at 0x106bf1aa0>>>> next(counter)0>>> next(counter)1>>> iter(counter)<generator object count_generator at 0x106bf1aa0>>>> iter(counter) is counterTrue>>> type(counter)<type 'generator'> |
現在讓我們嘗試用生成器來實現Hofstadter's Q隊列。這個實現很簡單，不過我們卻不能實現前的類似于current_state那樣的函數了。因為據我所知，不可能在外部直接訪問生成器內部的變量狀態，因此如current_state這樣的函數就不可能實現了(雖然有諸如gi_frame.f_locals這樣的數據結構可以做到，但是這畢竟是CPython的特殊實現，并不是這門語言的標準部分，所以并不推薦使用)。如果需要訪問內部變量，一個可能的方法是通過yield返回所有的結果，我會把這個問題留作練習。
|
1
2
3
4
5
6
7
8
9
|
def hofstadter_generator(s): a = s[:] while True: try: q = a[-a[-1]] + a[-a[-2]] a.append(q) yield q except IndexError: return |
請注意，在生成器迭代過程的結尾有一個簡單的return語句，但并沒有返回任何數據。從內部來說，這將拋出一個StopIteration異常。
下一個例子來自Groupon的面試題。在這里我們首先使用兩個生成器來實現Bernoulli過程，這個過程是一個隨機布爾值的無限序列，True的概率是p而False的概率為q=1-p。隨后實現一個von Neumann extractor，它從Bernoulli process獲取輸入(0<p<1)，并且返回另一個Bernoulli process(p=0.5)。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
import random def bernoulli_process(p): if p > 1.0 or p < 0.0: raise ValueError("p should be between 0.0 and 1.0.") while True: yield random.random() < p def von_neumann_extractor(process): while True: x, y = process.next(), process.next() if x != y: yield x |
最后，生成器是一種生成隨機動態系統的很有利的工具。下面這個例子將演示著名的帳篷映射(tent map)動態系統是如何通過生成器實現的。(插句題外話，看看數值的不準確性是如何開始關聯變化并呈指數式增長的，這是一個如帳篷映射這樣的動態系統的關鍵特征)。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
>>> def tent_map(mu, x0):... x = x0... while True:... yield x... x = mu * min(x, 1.0 - x)...>>>>>> t = tent_map(2.0, 0.1)>>> for __ in xrange(30):... print t.next()...0.10.20.40.80.40.80.40.80.40.80.40.80.40.80.40.80.40.7999999999990.4000000000010.8000000000030.3999999999940.7999999999880.4000000000230.8000000000470.3999999999070.7999999998140.4000000003730.8000000007450.399999998510.79999999702 |
另一個相似的例子是Collatz序列。
|
1
2
3
4
5
|
def collatz(n): yield n while n != 1: n = n / 2 if n % 2 == 0 else 3 * n + 1 yield n |
請注意在這個例子中，我們仍舊沒有手動拋出StopIteration異常，因為它會在控制流到達函數結尾的時候自動拋出。
請看用法：
|
1
2
3
4
5
6
7
8
9
10
|
>>> # If the Collatz conjecture is true then list(collatz(n)) for any n will... # always terminate (though your machine might run out of memory first!)>>> list(collatz(7))[7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]>>> list(collatz(13))[13, 40, 20, 10, 5, 16, 8, 4, 2, 1]>>> list(collatz(17))[17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1]>>> list(collatz(19))[19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1] |
生成器可以像其它函數那樣遞歸。讓我們來看一個自實現的簡單版本的itertools.permutations，這個生成器通過給定一個item列表生成其全排列(在實際中請使用itertools.permutations，那個實現更快)。基本思想很簡單：對列表中的每一個元素，我們通過將它與列表第一個元素交換將其放置到第一的位置上去，而后重新遞歸排列列表的剩余部分。
|
1
2
3
4
5
6
7
8
9
|
def permutations(items): if len(items) == 0: yield [] else: pi = items[:] for i in xrange(len(pi)): pi[0], pi[i] = pi[i], pi[0] for p in permutations(pi[1:]): yield [pi[0]] + p |
|
1
2
3
4
5
6
7
8
9
|
>>> for p in permutations([1, 2, 3]):... print p...[1, 2, 3][1, 3, 2][2, 1, 3][2, 3, 1][3, 1, 2][3, 2, 1] |
生成器表達式可以讓你通過一個簡單的，單行聲明定義生成器。這跟Python中的列表推導式非常類似，舉個例子，下面的代碼將定義一個生成器迭代所有的完全平方。注意生成器表達式的返回結果是一個生成器類型對象，它實現了next和__iter__兩個方法。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
>>> g = (x ** 2 for x in itertools.count(1))>>> g<generator object <genexpr> at 0x1029a5fa0>>>> next(g)1>>> next(g)4>>> iter(g)<generator object <genexpr> at 0x1029a5fa0>>>> iter(g) is gTrue>>> [g.next() for __ in xrange(10)][9, 16, 25, 36, 49, 64, 81, 100, 121, 144] |
同樣可以使用生成器表達式實現Bernoulli過程，在這個例子中p=0.4。如果一個生成器表達式需要另一個迭代器作為循環指示器，并且這個生辰器表達式使用在無限序列上的，那么itertools.count將是一個很好的選擇。若非如此，xrange將是一個不錯的選擇。
|
1
2
3
|
>>> g = (random.random() < 0.4 for __ in itertools.count())>>> [g.next() for __ in xrange(10)][False, False, False, True, True, False, True, False, False, True] |
正如前面提到的，生成器表達式能夠用在任何需要迭代器作為參數的地方。舉個例子，我們可以通過如下代碼計算前十個全平方數的累加和：
|
1
2
|
>>> sum(x ** 2 for x in xrange(10))285 |
更多生成器表達式的例子將在下一節給出。
itertools模塊
itertools模塊提供了一系列迭代器能夠幫助用戶輕松地使用排列、組合、笛卡爾積或其他組合結構。
在開始下面的部分之前，注意到上面給出的所有代碼都是未經優化的，在這里只是充當一個示例的作用。在實際使用中，你應該避免自己去實現排列組合除非你能夠有更好的想法，因為枚舉的數量可是按照指數級增加的。
讓我們先從一些有趣的用例開始。第一個例子來看如何寫一個常用的模式：循環遍歷一個三維數組的所有下標元素，并且循環遍歷滿足0≤i<j<k≤n條件的所有下標。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
from itertools import combinations, product n = 4d = 3 def visit(*indices): print indices # Loop through all possible indices of a 3-D arrayfor i in xrange(n): for j in xrange(n): for k in xrange(n): visit(i, j, k) # Equivalent using itertools.productfor indices in product(*([xrange(n)] * d)): visit(*indices) # Now loop through all indices 0 <= i < j < k <= nfor i in xrange(n): for j in xrange(i + 1, n): for k in xrange(j + 1, n): visit(i, j, k) # And equivalent using itertools.combinationsfor indices in combinations(xrange(n), d): visit(*indices) |
使用itertools模塊提供的枚舉器有兩個好處：代碼能夠在單行內完成，并且很容易擴展到更高維度。我并未比較for方法和itertools兩種方法的性能，也許跟n有很大關系。如果你想的話請自行測試評判。
第二個例子，來做一些有趣的數學題：使用生成器表達式、itertools.combinations以及itertools.permutations來計算排列的逆序數，并且計算一個列表全排列逆序數之和。如OEIS A001809所示，求和的結果趨近于n!n(n-1)/4。在實際使用中直接通過這公式計算要比上面的代碼更高效，不過我寫這個例子是為了練習itertools枚舉器的使用。
|
1
2
3
4
5
6
7
8
9
10
|
import itertoolsimport math def inversion_number(A): """Return the number of inversions in list A.""" return sum(1 for x, y in itertools.combinations(xrange(len(A)), 2) if A[x] > A[y]) def total_inversions(n): """Return total number of inversions in permutations of n.""" return sum(inversion_number(A) for A in itertools.permutations(xrange(n))) |
用法如下：
|
1
2
3
4
5
|
>>> [total_inversions(n) for n in xrange(10)][0, 0, 1, 9, 72, 600, 5400, 52920, 564480, 6531840] >>> [math.factorial(n) * n * (n - 1) / 4 for n in xrange(10)][0, 0, 1, 9, 72, 600, 5400, 52920, 564480, 6531840] |
第三個例子，通過brute-force counting方法計算recontres number。recontres number的定義在此。首先，我們寫了一個函數在一個求和過程中使用生成器表達式去計算排列中fixed points出現的個數。然后在求和中使用itertools.permutations和其他生成器表達式計算包含n個數并且有k個fixed points的排列的總數。然后得到結果。當然了，這個實現方法是效率低下的，不提倡在實際應用中使用。再次重申，這只是為了掩飾生成器表達式以及itertools相關函數使用方法的示例。
|
1
2
3
4
5
6
7
|
def count_fixed_points(p): """Return the number of fixed points of p as a permutation.""" return sum(1 for x in p if p[x] == x) def count_partial_derangements(n, k): """Returns the number of permutations of n with k fixed points.""" return sum(1 for p in itertools.permutations(xrange(n)) if count_fixed_points(p) == k) |
用法：
|
1
2
3
|
# Usage:>>> [count_partial_derangements(6, i) for i in xrange(7)][265, 264, 135, 40, 15, 0, 1] |
