對(duì)數(shù)學(xué)家來(lái)說(shuō)，Python這門(mén)語(yǔ)言有著很多吸引他們的地方。舉幾個(gè)例子：對(duì)于tuple、lists以及sets等容器的支持，使用與傳統(tǒng)數(shù)學(xué)類(lèi)似的符號(hào)標(biāo)記方式，還有列表推導(dǎo)式這樣與數(shù)學(xué)中集合推導(dǎo)式和集的結(jié)構(gòu)式(set-builder notation)很相似的語(yǔ)法結(jié)構(gòu)。

另外一些很吸引數(shù)學(xué)愛(ài)好者的特性是Python中的iterator(迭代器)、generator(生成器)以及相關(guān)的itertools包。這些工具幫助人們能夠很輕松的寫(xiě)出處理諸如無(wú)窮序列(infinite sequence)、隨機(jī)過(guò)程(stochastic processes)、遞推關(guān)系(recurrence relations)以及組合結(jié)構(gòu)(combinatorial structures)等數(shù)學(xué)對(duì)象的優(yōu)雅代碼。本文將涵蓋我關(guān)于迭代器和生成器的一些筆記，并且有一些我在學(xué)習(xí)過(guò)程中積累的相關(guān)經(jīng)驗(yàn)。
Iterators

迭代器(Iterator)是一個(gè)可以對(duì)集合進(jìn)行迭代訪問(wèn)的對(duì)象。通過(guò)這種方式不需要將集合全部載入內(nèi)存中，也正因如此，這種集合元素幾乎可以是無(wú)限的。你可以在Python官方文檔的“迭代器類(lèi)型(Iterator Type)”部分找到相關(guān)文檔。

讓我們對(duì)定義的描述再準(zhǔn)確些，如果一個(gè)對(duì)象定義了__iter__方法，并且此方法需要返回一個(gè)迭代器，那么這個(gè)對(duì)象就是可迭代的(iterable)。而迭代器是指實(shí)現(xiàn)了__iter__以及next(在Python 3中為_(kāi)_next__)兩個(gè)方法的對(duì)象，前者返回一個(gè)迭代器對(duì)象，而后者返回迭代過(guò)程的下一個(gè)集合元素。據(jù)我所知，迭代器總是在__iter__方法中簡(jiǎn)單的返回自己(self)，因?yàn)樗鼈冋亲约旱牡鳌?/p>

一般來(lái)說(shuō)，你應(yīng)該避免直接調(diào)用__iter__以及next方法。而應(yīng)該使用for或是列表推導(dǎo)式(list comprehension)，這樣的話Python能夠自動(dòng)為你調(diào)用這兩個(gè)方法。如果你需要手動(dòng)調(diào)用它們，請(qǐng)使用Python的內(nèi)建函數(shù)iter以及next，并且把目標(biāo)迭代器對(duì)象或是集合對(duì)象當(dāng)做參數(shù)傳遞給它們。舉個(gè)例子，如果c是一個(gè)可迭代對(duì)象，那么你可以使用iter(c)來(lái)訪問(wèn)，而不是c.__iter__()，類(lèi)似的，如果a是一個(gè)迭代器對(duì)象，那么請(qǐng)使用next(a)而不是a.next()來(lái)訪問(wèn)下一個(gè)元素。與之相類(lèi)似的還有l(wèi)en的用法。

說(shuō)到len，值得注意的是對(duì)迭代器而言沒(méi)必要去糾結(jié)length的定義。所以它們通常不會(huì)去實(shí)現(xiàn)__len__方法。如果你需要計(jì)算容器的長(zhǎng)度，那么必須得手動(dòng)計(jì)算，或者使用sum。本文末，在itertools模塊之后會(huì)給出一個(gè)例子。

有一些可迭代對(duì)象并不是迭代器，而是使用其他對(duì)象作為迭代器。舉個(gè)例子，list對(duì)象是一個(gè)可迭代對(duì)象，但并不是一個(gè)迭代器(它實(shí)現(xiàn)了__iter__但并未實(shí)現(xiàn)next)。通過(guò)下面的例子你可以看到list是如何使用迭代器listiterator的。同時(shí)值得注意的是list很好地定義了length屬性，而listiterator卻沒(méi)有。

>>> 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ù)迭代訪問(wèn)時(shí)，Python解釋器會(huì)拋出StopIteration異常。然而，前述中提到迭代器可以迭代一個(gè)無(wú)窮集合，所以對(duì)于這種迭代器就必須由用戶負(fù)責(zé)確保不會(huì)造成無(wú)限循環(huán)的情況，請(qǐng)看下面的例子：
 

class count_iterator(object):
  n = 0
 
  def __iter__(self):
    return self
 
  def next(self):
    y = self.n
    self.n += 1
    return y

下面是例子，注意最后一行試圖將一個(gè)迭代器對(duì)象轉(zhuǎn)為list，這將導(dǎo)致一個(gè)無(wú)限循環(huán)，因?yàn)檫@種迭代器對(duì)象將不會(huì)停止。
 

>>> counter = count_iterator()
>>> next(counter)
0
>>> next(counter)
1
>>> next(counter)
2
>>> next(counter)
3
>>> list(counter) # This will result in an infinite loop!

最后，我們將修改以上的程序：如果一個(gè)對(duì)象沒(méi)有__iter__方法但定義了__getitem__方法，那么這個(gè)對(duì)象仍然是可迭代的。在這種情況下，當(dāng)Python的內(nèi)建函數(shù)iter將會(huì)返回一個(gè)對(duì)應(yīng)此對(duì)象的迭代器類(lèi)型，并使用__getitem__方法遍歷list的所有元素。如果StopIteration或IndexError異常被拋出，則迭代停止。讓我們看看以下的例子：
 

class SimpleList(object):
  def __init__(self, *items):
    self.items = items
 
  def __getitem__(self, i):
    return self.items[i]

用法在此：
 

>>> 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)在來(lái)看一個(gè)更有趣的例子：根據(jù)初始條件使用迭代器生成Hofstadter Q序列。Hofstadter在他的著作《G?del, Escher, Bach: An Eternal Golden Braid》中首次提到了這個(gè)嵌套的序列，并且自那時(shí)候開(kāi)始關(guān)于證明這個(gè)序列對(duì)所有n都成立的問(wèn)題就開(kāi)始了。以下的代碼使用一個(gè)迭代器來(lái)生成給定n的Hofstadter序列，定義如下：

Q(n)=Q(n-Q(n-1))+Q(n?Q(n?2))

給定一個(gè)初始條件，舉個(gè)例子，qsequence([1, 1])將會(huì)生成H序列。我們使用StopIteration異常來(lái)指示序列不能夠繼續(xù)生成了，因?yàn)樾枰粋€(gè)合法的下標(biāo)索引來(lái)生成下一個(gè)元素。例如如果初始條件是[1,2]，那么序列生成將立即停止。
 

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

用法在此：
 

>>> 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)是一種用更簡(jiǎn)單的函數(shù)表達(dá)式定義的生成器。說(shuō)的更具體一些，在生成器內(nèi)部會(huì)用到y(tǒng)ield表達(dá)式。生成器不會(huì)使用return返回值，而當(dāng)需要時(shí)使用yield表達(dá)式返回結(jié)果。Python的內(nèi)在機(jī)制能夠幫助記住當(dāng)前生成器的上下文，也就是當(dāng)前的控制流和局部變量的值等。每次生成器被調(diào)用都適用yield返回迭代過(guò)程中的下一個(gè)值。__iter__方法是默認(rèn)實(shí)現(xiàn)的，意味著任何能夠使用迭代器的地方都能夠使用生成器。下面這個(gè)例子實(shí)現(xiàn)的功能同上面迭代器的例子一樣，不過(guò)代碼更緊湊，可讀性更強(qiáng)。
 

def count_generator():
  n = 0
  while True:
   yield n
   n += 1

來(lái)看看用法：

>>> 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 counter
True
>>> type(counter)
<type 'generator'>

現(xiàn)在讓我們嘗試用生成器來(lái)實(shí)現(xiàn)Hofstadter's Q隊(duì)列。這個(gè)實(shí)現(xiàn)很簡(jiǎn)單，不過(guò)我們卻不能實(shí)現(xiàn)前的類(lèi)似于current_state那樣的函數(shù)了。因?yàn)閾?jù)我所知，不可能在外部直接訪問(wèn)生成器內(nèi)部的變量狀態(tài)，因此如current_state這樣的函數(shù)就不可能實(shí)現(xiàn)了(雖然有諸如gi_frame.f_locals這樣的數(shù)據(jù)結(jié)構(gòu)可以做到，但是這畢竟是CPython的特殊實(shí)現(xiàn)，并不是這門(mén)語(yǔ)言的標(biāo)準(zhǔn)部分，所以并不推薦使用)。如果需要訪問(wèn)內(nèi)部變量，一個(gè)可能的方法是通過(guò)yield返回所有的結(jié)果，我會(huì)把這個(gè)問(wèn)題留作練習(xí)。
 

def hofstadter_generator(s):
  a = s[:]
  while True:
    try:
      q = a[-a[-1]] + a[-a[-2]]
      a.append(q)
      yield q
    except IndexError:
      return

請(qǐng)注意，在生成器迭代過(guò)程的結(jié)尾有一個(gè)簡(jiǎn)單的return語(yǔ)句，但并沒(méi)有返回任何數(shù)據(jù)。從內(nèi)部來(lái)說(shuō)，這將拋出一個(gè)StopIteration異常。

下一個(gè)例子來(lái)自Groupon的面試題。在這里我們首先使用兩個(gè)生成器來(lái)實(shí)現(xiàn)Bernoulli過(guò)程，這個(gè)過(guò)程是一個(gè)隨機(jī)布爾值的無(wú)限序列，True的概率是p而False的概率為q=1-p。隨后實(shí)現(xiàn)一個(gè)von Neumann extractor，它從Bernoulli process獲取輸入(0<p<1)，并且返回另一個(gè)Bernoulli process(p=0.5)。
 

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ī)動(dòng)態(tài)系統(tǒng)的很有利的工具。下面這個(gè)例子將演示著名的帳篷映射(tent map)動(dòng)態(tài)系統(tǒng)是如何通過(guò)生成器實(shí)現(xiàn)的。(插句題外話，看看數(shù)值的不準(zhǔn)確性是如何開(kāi)始關(guān)聯(lián)變化并呈指數(shù)式增長(zhǎng)的，這是一個(gè)如帳篷映射這樣的動(dòng)態(tài)系統(tǒng)的關(guān)鍵特征)。

>>> 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.1
0.2
0.4
0.8
0.4
0.8
0.4
0.8
0.4
0.8
0.4
0.8
0.4
0.8
0.4
0.8
0.4
0.799999999999
0.400000000001
0.800000000003
0.399999999994
0.799999999988
0.400000000023
0.800000000047
0.399999999907
0.799999999814
0.400000000373
0.800000000745
0.39999999851
0.79999999702

另一個(gè)相似的例子是Collatz序列。
 

def collatz(n):
  yield n
  while n != 1:
   n = n / 2 if n % 2 == 0 else 3 * n + 1
   yield n

請(qǐng)注意在這個(gè)例子中，我們?nèi)耘f沒(méi)有手動(dòng)拋出StopIteration異常，因?yàn)樗鼤?huì)在控制流到達(dá)函數(shù)結(jié)尾的時(shí)候自動(dòng)拋出。

請(qǐng)看用法：
 

>>> # 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ù)那樣遞歸。讓我們來(lái)看一個(gè)自實(shí)現(xiàn)的簡(jiǎn)單版本的itertools.permutations，這個(gè)生成器通過(guò)給定一個(gè)item列表生成其全排列(在實(shí)際中請(qǐng)使用itertools.permutations，那個(gè)實(shí)現(xiàn)更快)。基本思想很簡(jiǎn)單：對(duì)列表中的每一個(gè)元素，我們通過(guò)將它與列表第一個(gè)元素交換將其放置到第一的位置上去，而后重新遞歸排列列表的剩余部分。
 

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

>>> 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á)式可以讓你通過(guò)一個(gè)簡(jiǎn)單的，單行聲明定義生成器。這跟Python中的列表推導(dǎo)式非常類(lèi)似，舉個(gè)例子，下面的代碼將定義一個(gè)生成器迭代所有的完全平方。注意生成器表達(dá)式的返回結(jié)果是一個(gè)生成器類(lèi)型對(duì)象，它實(shí)現(xiàn)了next和__iter__兩個(gè)方法。
 

>>> 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 g
True
>>> [g.next() for __ in xrange(10)]
[9, 16, 25, 36, 49, 64, 81, 100, 121, 144]

同樣可以使用生成器表達(dá)式實(shí)現(xiàn)Bernoulli過(guò)程，在這個(gè)例子中p=0.4。如果一個(gè)生成器表達(dá)式需要另一個(gè)迭代器作為循環(huán)指示器，并且這個(gè)生辰器表達(dá)式使用在無(wú)限序列上的，那么itertools.count將是一個(gè)很好的選擇。若非如此，xrange將是一個(gè)不錯(cuò)的選擇。
 

>>> 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ù)的地方。舉個(gè)例子，我們可以通過(guò)如下代碼計(jì)算前十個(gè)全平方數(shù)的累加和：
 

>>> sum(x ** 2 for x in xrange(10))
285

更多生成器表達(dá)式的例子將在下一節(jié)給出。
itertools模塊

itertools模塊提供了一系列迭代器能夠幫助用戶輕松地使用排列、組合、笛卡爾積或其他組合結(jié)構(gòu)。

在開(kāi)始下面的部分之前，注意到上面給出的所有代碼都是未經(jīng)優(yōu)化的，在這里只是充當(dāng)一個(gè)示例的作用。在實(shí)際使用中，你應(yīng)該避免自己去實(shí)現(xiàn)排列組合除非你能夠有更好的想法，因?yàn)槊杜e的數(shù)量可是按照指數(shù)級(jí)增加的。

讓我們先從一些有趣的用例開(kāi)始。第一個(gè)例子來(lái)看如何寫(xiě)一個(gè)常用的模式：循環(huán)遍歷一個(gè)三維數(shù)組的所有下標(biāo)元素，并且循環(huán)遍歷滿足0≤i<j<k≤n條件的所有下標(biāo)。

from itertools import combinations, product
 
n = 4
d = 3
 
def visit(*indices):
  print indices
 
# Loop through all possible indices of a 3-D array
for i in xrange(n):
  for j in xrange(n):
    for k in xrange(n):
      visit(i, j, k)
 
# Equivalent using itertools.product
for indices in product(*([xrange(n)] * d)):
  visit(*indices)
 
# Now loop through all indices 0 <= i < j < k <= n
for 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.combinations
for indices in combinations(xrange(n), d):
  visit(*indices)

使用itertools模塊提供的枚舉器有兩個(gè)好處：代碼能夠在單行內(nèi)完成，并且很容易擴(kuò)展到更高維度。我并未比較for方法和itertools兩種方法的性能，也許跟n有很大關(guān)系。如果你想的話請(qǐng)自行測(cè)試評(píng)判。

第二個(gè)例子，來(lái)做一些有趣的數(shù)學(xué)題：使用生成器表達(dá)式、itertools.combinations以及itertools.permutations來(lái)計(jì)算排列的逆序數(shù)，并且計(jì)算一個(gè)列表全排列逆序數(shù)之和。如OEIS A001809所示，求和的結(jié)果趨近于n!n(n-1)/4。在實(shí)際使用中直接通過(guò)這公式計(jì)算要比上面的代碼更高效，不過(guò)我寫(xiě)這個(gè)例子是為了練習(xí)itertools枚舉器的使用。
 

import itertools
import 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)))

用法如下：
 

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

第三個(gè)例子，通過(guò)brute-force counting方法計(jì)算recontres number。recontres number的定義在此。首先，我們寫(xiě)了一個(gè)函數(shù)在一個(gè)求和過(guò)程中使用生成器表達(dá)式去計(jì)算排列中fixed points出現(xiàn)的個(gè)數(shù)。然后在求和中使用itertools.permutations和其他生成器表達(dá)式計(jì)算包含n個(gè)數(shù)并且有k個(gè)fixed points的排列的總數(shù)。然后得到結(jié)果。當(dāng)然了，這個(gè)實(shí)現(xiàn)方法是效率低下的，不提倡在實(shí)際應(yīng)用中使用。再次重申，這只是為了掩飾生成器表達(dá)式以及itertools相關(guān)函數(shù)使用方法的示例。
 

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)

用法：
 

# Usage:
>>> [count_partial_derangements(6, i) for i in xrange(7)]
[265, 264, 135, 40, 15, 0, 1]

最新評(píng)論