對數(shù)學(xué)家來說，Python這門語言有著很多吸引他們的地方。舉幾個例子：對于tuple、lists以及sets等容器的支持，使用與傳統(tǒng)數(shù)學(xué)類似的符號標(biāo)記方式，還有列表推導(dǎo)式這樣與數(shù)學(xué)中集合推導(dǎo)式和集的結(jié)構(gòu)式(set-builder notation)很相似的語法結(jié)構(gòu)。
另外一些很吸引數(shù)學(xué)愛好者的特性是Python中的iterator(迭代器)、generator(生成器)以及相關(guān)的itertools包。這些工具幫助人們能夠很輕松的寫出處理諸如無窮序列(infinite sequence)、隨機(jī)過程(stochastic processes)、遞推關(guān)系(recurrence relations)以及組合結(jié)構(gòu)(combinatorial structures)等數(shù)學(xué)對象的優(yōu)雅代碼。本文將涵蓋我關(guān)于迭代器和生成器的一些筆記，并且有一些我在學(xué)習(xí)過程中積累的相關(guān)經(jīng)驗。
Iterators
迭代器(Iterator)是一個可以對集合進(jìn)行迭代訪問的對象。通過這種方式不需要將集合全部載入內(nèi)存中，也正因如此，這種集合元素幾乎可以是無限的。你可以在Python官方文檔的“迭代器類型(Iterator Type)”部分找到相關(guān)文檔。
讓我們對定義的描述再準(zhǔn)確些，如果一個對象定義了__iter__方法，并且此方法需要返回一個迭代器，那么這個對象就是可迭代的(iterable)。而迭代器是指實(shí)現(xiàn)了__iter__以及next(在Python 3中為__next__)兩個方法的對象，前者返回一個迭代器對象，而后者返回迭代過程的下一個集合元素。據(jù)我所知，迭代器總是在__iter__方法中簡單的返回自己(self)，因為它們正是自己的迭代器。
一般來說，你應(yīng)該避免直接調(diào)用__iter__以及next方法。而應(yīng)該使用for或是列表推導(dǎo)式(list comprehension)，這樣的話Python能夠自動為你調(diào)用這兩個方法。如果你需要手動調(diào)用它們，請使用Python的內(nèi)建函數(shù)iter以及next，并且把目標(biāo)迭代器對象或是集合對象當(dāng)做參數(shù)傳遞給它們。舉個例子，如果c是一個可迭代對象，那么你可以使用iter(c)來訪問，而不是c.__iter__()，類似的，如果a是一個迭代器對象，那么請使用next(a)而不是a.next()來訪問下一個元素。與之相類似的還有l(wèi)en的用法。
說到len，值得注意的是對迭代器而言沒必要去糾結(jié)length的定義。所以它們通常不會去實(shí)現(xiàn)__len__方法。如果你需要計算容器的長度，那么必須得手動計算，或者使用sum。本文末，在itertools模塊之后會給出一個例子。
有一些可迭代對象并不是迭代器，而是使用其他對象作為迭代器。舉個例子，list對象是一個可迭代對象，但并不是一個迭代器(它實(shí)現(xiàn)了__iter__但并未實(shí)現(xiàn)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() |
當(dāng)?shù)Y(jié)束卻仍然被繼續(xù)迭代訪問時，Python解釋器會拋出StopIteration異常。然而，前述中提到迭代器可以迭代一個無窮集合，所以對于這種迭代器就必須由用戶負(fù)責(zé)確保不會造成無限循環(huán)的情況，請看下面的例子：
|
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 |
下面是例子，注意最后一行試圖將一個迭代器對象轉(zhuǎn)為list，這將導(dǎo)致一個無限循環(huán)，因為這種迭代器對象將不會停止。
|
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__方法，那么這個對象仍然是可迭代的。在這種情況下，當(dāng)Python的內(nèi)建函數(shù)iter將會返回一個對應(yīng)此對象的迭代器類型，并使用__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 |
現(xiàn)在來看一個更有趣的例子：根據(jù)初始條件使用迭代器生成Hofstadter Q序列。Hofstadter在他的著作《G?del, Escher, Bach: An Eternal Golden Braid》中首次提到了這個嵌套的序列，并且自那時候開始關(guān)于證明這個序列對所有n都成立的問題就開始了。以下的代碼使用一個迭代器來生成給定n的Hofstadter序列，定義如下：
|
1
|
Q(n)=Q(n-Q(n-1))+Q(n?Q(n?2)) |
給定一個初始條件，舉個例子，qsequence([1, 1])將會生成H序列。我們使用StopIteration異常來指示序列不能夠繼續(xù)生成了，因為需要一個合法的下標(biāo)索引來生成下一個元素。例如如果初始條件是[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)是一種用更簡單的函數(shù)表達(dá)式定義的生成器。說的更具體一些，在生成器內(nèi)部會用到y(tǒng)ield表達(dá)式。生成器不會使用return返回值，而當(dāng)需要時使用yield表達(dá)式返回結(jié)果。Python的內(nèi)在機(jī)制能夠幫助記住當(dāng)前生成器的上下文，也就是當(dāng)前的控制流和局部變量的值等。每次生成器被調(diào)用都適用yield返回迭代過程中的下一個值。__iter__方法是默認(rèn)實(shí)現(xiàn)的，意味著任何能夠使用迭代器的地方都能夠使用生成器。下面這個例子實(shí)現(xiàn)的功能同上面迭代器的例子一樣，不過代碼更緊湊，可讀性更強(qiáng)。
|
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'> |
現(xiàn)在讓我們嘗試用生成器來實(shí)現(xiàn)Hofstadter's Q隊列。這個實(shí)現(xiàn)很簡單，不過我們卻不能實(shí)現(xiàn)前的類似于current_state那樣的函數(shù)了。因為據(jù)我所知，不可能在外部直接訪問生成器內(nèi)部的變量狀態(tài)，因此如current_state這樣的函數(shù)就不可能實(shí)現(xiàn)了(雖然有諸如gi_frame.f_locals這樣的數(shù)據(jù)結(jié)構(gòu)可以做到，但是這畢竟是CPython的特殊實(shí)現(xiàn)，并不是這門語言的標(biāo)準(zhǔn)部分，所以并不推薦使用)。如果需要訪問內(nèi)部變量，一個可能的方法是通過yield返回所有的結(jié)果，我會把這個問題留作練習(xí)。
|
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 |
請注意，在生成器迭代過程的結(jié)尾有一個簡單的return語句，但并沒有返回任何數(shù)據(jù)。從內(nèi)部來說，這將拋出一個StopIteration異常。
下一個例子來自Groupon的面試題。在這里我們首先使用兩個生成器來實(shí)現(xiàn)Bernoulli過程，這個過程是一個隨機(jī)布爾值的無限序列，True的概率是p而False的概率為q=1-p。隨后實(shí)現(xiàn)一個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 |
最后，生成器是一種生成隨機(jī)動態(tài)系統(tǒng)的很有利的工具。下面這個例子將演示著名的帳篷映射(tent map)動態(tài)系統(tǒng)是如何通過生成器實(shí)現(xiàn)的。(插句題外話，看看數(shù)值的不準(zhǔn)確性是如何開始關(guān)聯(lián)變化并呈指數(shù)式增長的，這是一個如帳篷映射這樣的動態(tài)系統(tǒng)的關(guā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
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 |
請注意在這個例子中，我們?nèi)耘f沒有手動拋出StopIteration異常，因為它會在控制流到達(dá)函數(shù)結(jié)尾的時候自動拋出。
請看用法：
|
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] |
生成器可以像其它函數(shù)那樣遞歸。讓我們來看一個自實(shí)現(xiàn)的簡單版本的itertools.permutations，這個生成器通過給定一個item列表生成其全排列(在實(shí)際中請使用itertools.permutations，那個實(shí)現(xiàn)更快)。基本思想很簡單：對列表中的每一個元素，我們通過將它與列表第一個元素交換將其放置到第一的位置上去，而后重新遞歸排列列表的剩余部分。
|
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] |
生成器表達(dá)式可以讓你通過一個簡單的，單行聲明定義生成器。這跟Python中的列表推導(dǎo)式非常類似，舉個例子，下面的代碼將定義一個生成器迭代所有的完全平方。注意生成器表達(dá)式的返回結(jié)果是一個生成器類型對象，它實(shí)現(xiàn)了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] |
同樣可以使用生成器表達(dá)式實(shí)現(xiàn)Bernoulli過程，在這個例子中p=0.4。如果一個生成器表達(dá)式需要另一個迭代器作為循環(huán)指示器，并且這個生辰器表達(dá)式使用在無限序列上的，那么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] |
正如前面提到的，生成器表達(dá)式能夠用在任何需要迭代器作為參數(shù)的地方。舉個例子，我們可以通過如下代碼計算前十個全平方數(shù)的累加和：
|
1
2
|
>>> sum(x ** 2 for x in xrange(10))285 |
更多生成器表達(dá)式的例子將在下一節(jié)給出。
itertools模塊
itertools模塊提供了一系列迭代器能夠幫助用戶輕松地使用排列、組合、笛卡爾積或其他組合結(jié)構(gòu)。
在開始下面的部分之前，注意到上面給出的所有代碼都是未經(jīng)優(yōu)化的，在這里只是充當(dāng)一個示例的作用。在實(shí)際使用中，你應(yīng)該避免自己去實(shí)現(xiàn)排列組合除非你能夠有更好的想法，因為枚舉的數(shù)量可是按照指數(shù)級增加的。
讓我們先從一些有趣的用例開始。第一個例子來看如何寫一個常用的模式：循環(huán)遍歷一個三維數(shù)組的所有下標(biāo)元素，并且循環(huán)遍歷滿足0≤i<j<k≤n條件的所有下標(biāo)。
|
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模塊提供的枚舉器有兩個好處：代碼能夠在單行內(nèi)完成，并且很容易擴(kuò)展到更高維度。我并未比較for方法和itertools兩種方法的性能，也許跟n有很大關(guān)系。如果你想的話請自行測試評判。
第二個例子，來做一些有趣的數(shù)學(xué)題：使用生成器表達(dá)式、itertools.combinations以及itertools.permutations來計算排列的逆序數(shù)，并且計算一個列表全排列逆序數(shù)之和。如OEIS A001809所示，求和的結(jié)果趨近于n!n(n-1)/4。在實(shí)際使用中直接通過這公式計算要比上面的代碼更高效，不過我寫這個例子是為了練習(xí)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的定義在此。首先，我們寫了一個函數(shù)在一個求和過程中使用生成器表達(dá)式去計算排列中fixed points出現(xiàn)的個數(shù)。然后在求和中使用itertools.permutations和其他生成器表達(dá)式計算包含n個數(shù)并且有k個fixed points的排列的總數(shù)。然后得到結(jié)果。當(dāng)然了，這個實(shí)現(xiàn)方法是效率低下的，不提倡在實(shí)際應(yīng)用中使用。再次重申，這只是為了掩飾生成器表達(dá)式以及itertools相關(guān)函數(shù)使用方法的示例。
|
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] |
