詳解Python的迭代器、生成器以及相關的itertools包

更新時間：2015年04月02日 10:31:50 作者：Sahand Saba

這篇文章主要介紹了詳解Python的迭代器、生成器以及相關的itertools包,Iterators、Generators是Python的高級特性,亦是Python學習當中必會的基本知識,需要的朋友可以參考下

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

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

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

讓我們對定義的描述再準確些，如果一個對象定義了__iter__方法，并且此方法需要返回一個迭代器，那么這個對象就是可迭代的(iterable)。而迭代器是指實現(xiàn)了__iter__以及next(在Python 3中為__next__)兩個方法的對象，前者返回一個迭代器對象，而后者返回迭代過程的下一個集合元素。據(jù)我所知，迭代器總是在__iter__方法中簡單的返回自己(self)，因為它們正是自己的迭代器。

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

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

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

>>> 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()

當?shù)Y(jié)束卻仍然被繼續(xù)迭代訪問時，Python解釋器會拋出StopIteration異常。然而，前述中提到迭代器可以迭代一個無窮集合，所以對于這種迭代器就必須由用戶負責確保不會造成無限循環(huán)的情況，請看下面的例子：

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，這將導致一個無限循環(huán)，因為這種迭代器對象將不會停止。

>>> 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的內(nèi)建函數(shù)iter將會返回一個對應此對象的迭代器類型，并使用__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)在來看一個更有趣的例子：根據(jù)初始條件使用迭代器生成Hofstadter Q序列。Hofstadter在他的著作《G?del, Escher, Bach: An Eternal Golden Braid》中首次提到了這個嵌套的序列，并且自那時候開始關于證明這個序列對所有n都成立的問題就開始了。以下的代碼使用一個迭代器來生成給定n的Hofstadter序列，定義如下：

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

給定一個初始條件，舉個例子，qsequence([1, 1])將會生成H序列。我們使用StopIteration異常來指示序列不能夠繼續(xù)生成了，因為需要一個合法的下標索引來生成下一個元素。例如如果初始條件是[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]

Generators

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

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

來看看用法：

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

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的面試題。在這里我們首先使用兩個生成器來實現(xiàn)Bernoulli過程，這個過程是一個隨機布爾值的無限序列，True的概率是p而False的概率為q=1-p。隨后實現(xiàn)一個von Neumann extractor，它從Bernoulli process獲取輸入(0<p<1)，并且返回另一個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

最后，生成器是一種生成隨機動態(tài)系統(tǒng)的很有利的工具。下面這個例子將演示著名的帳篷映射(tent map)動態(tài)系統(tǒng)是如何通過生成器實現(xiàn)的。(插句題外話，看看數(shù)值的不準確性是如何開始關聯(lián)變化并呈指數(shù)式增長的，這是一個如帳篷映射這樣的動態(tài)系統(tǒng)的關鍵特征)。

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

另一個相似的例子是Collatz序列。

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異常，因為它會在控制流到達函數(shù)結(jié)尾的時候自動拋出。

請看用法：

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

Recursive Generators

生成器可以像其它函數(shù)那樣遞歸。讓我們來看一個自實現(xiàn)的簡單版本的itertools.permutations，這個生成器通過給定一個item列表生成其全排列(在實際中請使用itertools.permutations，那個實現(xiàn)更快)?；舅枷牒芎唵危簩α斜碇械拿恳粋€元素，我們通過將它與列表第一個元素交換將其放置到第一的位置上去，而后重新遞歸排列列表的剩余部分。

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]

Generator Expressions

生成器表達式可以讓你通過一個簡單的，單行聲明定義生成器。這跟Python中的列表推導式非常類似，舉個例子，下面的代碼將定義一個生成器迭代所有的完全平方。注意生成器表達式的返回結(jié)果是一個生成器類型對象，它實現(xiàn)了next和__iter__兩個方法。

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

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

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

正如前面提到的，生成器表達式能夠用在任何需要迭代器作為參數(shù)的地方。舉個例子，我們可以通過如下代碼計算前十個全平方數(shù)的累加和：

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

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

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

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

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

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模塊提供的枚舉器有兩個好處：代碼能夠在單行內(nèi)完成，并且很容易擴展到更高維度。我并未比較for方法和itertools兩種方法的性能，也許跟n有很大關系。如果你想的話請自行測試評判。

第二個例子，來做一些有趣的數(shù)學題：使用生成器表達式、itertools.combinations以及itertools.permutations來計算排列的逆序數(shù)，并且計算一個列表全排列逆序數(shù)之和。如OEIS A001809所示，求和的結(jié)果趨近于n!n(n-1)/4。在實際使用中直接通過這公式計算要比上面的代碼更高效，不過我寫這個例子是為了練習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]

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

您可能感興趣的文章:

利用tkinter實現(xiàn)下拉框聯(lián)動
這篇文章主要介紹了利用tkinter實現(xiàn)下拉框聯(lián)動問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
2023-01-01
Python實現(xiàn)獲取命令行輸出結(jié)果的方法
這篇文章主要介紹了Python實現(xiàn)獲取命令行輸出結(jié)果的方法,涉及Python命令執(zhí)行及文件讀寫等相關操作技巧,需要的朋友可以參考下
2017-06-06
python如何使用代碼運行助手
在本篇文章里小編給大家分享了關于python代碼運行助手用法，需要的朋友們可以學習下。
2020-07-07
PYQT5實現(xiàn)控制臺顯示功能的方法
今天小編大家分享一篇PYQT5實現(xiàn)控制臺顯示功能的方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
2019-06-06
matplotlib繪制鼠標的十字光標的實現(xiàn)(自定義方式，官方實例)
這篇文章主要介紹了matplotlib繪制鼠標的十字光標(自定義方式，官方實例)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧
2021-01-01
解讀python正則表達式括號問題
這篇文章主要介紹了python正則表達式括號問題解讀，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教
2022-09-09
Django中間件攔截未登錄url實例詳解
在本篇文章里小編給各位整理了關于Django中間件攔截未登錄url的實例內(nèi)容以及相關知識點，有需要的朋友們可以學習下。
2019-09-09
詳解Python中的Numpy、SciPy、MatPlotLib安裝與配置
這篇文章主要介紹了詳解Python中的Numpy、SciPy、MatPlotLib安裝與配置，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2017-11-11
python中分組函數(shù)groupby和分組運算函數(shù)agg的使用
本文主要介紹了python中分組函數(shù)groupby和分組運算函數(shù)agg的使用，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下
2021-10-10
Python標準庫datetime之datetime模塊用法分析詳解
這篇文章主要介紹了Python標準庫datetime之datetime模塊用法分析詳解，文章圍繞主題展開詳細的內(nèi)容介紹，具有一定的參考價值，需要的小伙伴可以參考一下
2022-07-07