Python進階特性：Iterators、Generators和itertools

作為一門動态腳本語言，Python對程式設計初學者而言很友好，豐富的第三方庫能夠給使用者帶來很大的便利。而Python同時也能夠提供一些進階的特性友善使用者使用更為複雜的資料結構。本系列文章共有三篇，本文是系列的第一篇，将會介紹疊代器、生成器以及itertools子產品的相關用法。

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卻沒有

<code>&lt;</code><code>type</code> <code>&</code><code>#039;listiterator&#039;&gt;</code>

<code>Traceback (most recent call last):</code>

<code> </code><code>File</code> <code>&quot;&lt;stdin&gt;&quot;, line </code><code>1</code><code>, </code><code>in</code> <code>&lt;module&gt;</code>

<code>StopIteration</code>

<code>TypeError: </code><code>object</code> <code>of </code><code>type</code> <code>&</code><code>#039;listiterator&#039; has no len()</code>

當疊代結束卻仍然被繼續疊代通路時，Python解釋器會抛出StopIteration異常。然而，前述中提到疊代器可以疊代一個無窮集合，是以對于這種疊代器就必須由使用者負責確定不會造成無限循環的情況，請看下面的例子：

<code>class</code> <code>count_iterator(</code><code>object</code><code>):</code>

<code> </code><code>return</code> <code>self</code>

<code> </code><code>return</code> <code>y</code>

下面是例子，注意最後一行試圖将一個疊代器對象轉為list，這将導緻一個無限循環，因為這種疊代器對象将不會停止。

<code>&gt;&gt;&gt; counter </code><code>=</code> <code>count_iterator()</code>

<code>&gt;&gt;&gt; </code><code>next</code><code>(counter)</code>

<code>&gt;&gt;&gt; </code><code>list</code><code>(counter) </code><code># This will result in an infinite loop!</code>

最後，我們将修改以上的程式：如果一個對象沒有__iter__方法但定義了__getitem__方法，那麼這個對象仍然是可疊代的。在這種情況下，當Python的内建函數iter将會傳回一個對應此對象的疊代器類型，并使用__getitem__方法周遊list的所有元素。如果StopIteration或IndexError異常被抛出，則疊代停止。讓我們看看以下的例子：

<code>class</code> <code>SimpleList(</code><code>object</code><code>):</code>

<code> </code><code>def</code> <code>__init__(</code><code>self</code><code>, </code><code>*</code><code>items):</code>

<code> </code><code>self</code><code>.items </code><code>=</code> <code>items</code>

<code> </code><code>def</code> <code>__getitem__(</code><code>self</code><code>, i):</code>

<code> </code><code>return</code> <code>self</code><code>.items[i]</code>

用法在此：

<code>&gt;&gt;&gt; a </code><code>=</code> <code>SimpleList(</code><code>1</code><code>, </code><code>2</code><code>, </code><code>3</code><code>)</code>

現在來看一個更有趣的例子：根據初始條件使用疊代器生成Hofstadter Q序列。Hofstadter在他的著作《Gdel, Escher, Bach: An Eternal Golden Braid》中首次提到了這個嵌套的序列，并且自那時候開始關于證明這個序列對所有n都成立的問題就開始了。以下的代碼使用一個疊代器來生成給定n的Hofstadter序列，定義如下：

Q(n)=Q(n-Q(n-1))+Q(nQ(n2))

給定一個初始條件，舉個例子，qsequence([1, 1])将會生成H序列。我們使用StopIteration異常來訓示序列不能夠繼續生成了，因為需要一個合法的下标索引來生成下一個元素。例如如果初始條件是[1,2]，那麼序列生成将立即停止。

<code>class</code> <code>qsequence(</code><code>object</code><code>):</code>

<code> </code><code>self</code><code>.s.append(q)</code>

<code> </code><code>return</code> <code>q</code>

<code> </code><code>except</code> <code>IndexError:</code>

<code> </code><code>raise</code> <code>StopIteration()</code>

<code> </code><code>def</code> <code>current_state(</code><code>self</code><code>):</code>

<code> </code><code>return</code> <code>self</code><code>.s</code>

用法在此

<code>&gt;&gt;&gt; Q </code><code>=</code> <code>qsequence([</code><code>1</code><code>, </code><code>1</code><code>])</code>

<code>&gt;&gt;&gt; [</code><code>next</code><code>(Q) </code><code>for</code> <code>__ </code><code>in</code> <code>xrange</code><code>(</code><code>10</code><code>)]</code>

Generators

生成器(Generator)是一種用更簡單的函數表達式定義的生成器。說的更具體一些，在生成器内部會用到yield表達式。生成器不會使用return傳回值，而當需要時使用yield表達式傳回結果。Python的内在機制能夠幫助記住目前生成器的上下文，也就是目前的控制流和局部變量的值等。每次生成器被調用都适用yield傳回疊代過程中的下一個值。__iter__方法是預設實作的，意味着任何能夠使用疊代器的地方都能夠使用生成器。下面這個例子實作的功能同上面疊代器的例子一樣，不過代碼更緊湊，可讀性更強。

<code>def</code> <code>count_generator():</code>

<code> </code><code>while</code> <code>True</code><code>:</code>

<code> </code><code>yield</code> <code>n</code>

現在讓我們嘗試用生成器來實作Hofstadter’s Q隊列。這個實作很簡單，不過我們卻不能實作前的類似于current_state那樣的函數了。因為據我所知，不可能在外部直接通路生成器内部的變量狀态，是以如current_state這樣的函數就不可能實作了(雖然有諸如gi_frame.f_locals這樣的資料結構可以做到，但是這畢竟是CPython的特殊實作，并不是這門語言的标準部分，是以并不推薦使用)。如果需要通路内部變量，一個可能的方法是通過yield傳回所有的結果，我會把這個問題留作練習。

<code>def</code> <code>hofstadter_generator(s):</code>

<code> </code><code>while</code> <code>True</code><code>:</code>

<code> </code><code>a.append(q)</code>

<code> </code><code>yield</code> <code>q</code>

<code> </code><code>return</code>

請注意，在生成器疊代過程的結尾有一個簡單的return語句，但并沒有傳回任何資料。從内部來說，這将抛出一個StopIteration異常。

下一個例子來自Groupon的面試題。在這裡我們首先使用兩個生成器來實作Bernoulli過程，這個過程是一個随機布爾值的無限序列，True的機率是p而False的機率為q=1-p。随後實作一個von Neumann extractor，它從Bernoulli process擷取輸入(0<p<1)，并且傳回另一個Bernoulli process(p=0.5)。

<code>import</code> <code>random</code>

<code>def</code> <code>bernoulli_process(p):</code>

<code> </code><code>raise</code> <code>ValueError(&quot;p should be between </code><code>0.0</code> <code>and</code> <code>1.0</code><code>.&quot;)</code>

<code> </code><code>yield</code> <code>random.random() &lt; p</code>

<code>def</code> <code>von_neumann_extractor(process):</code>

<code> </code><code>x, y </code><code>=</code> <code>process.</code><code>next</code><code>(), process.</code><code>next</code><code>()</code>

<code> </code><code>yield</code> <code>x</code>

最後，生成器是一種生成随機動态系統的很有利的工具。下面這個例子将示範著名的帳篷映射(tent map)動态系統是如何通過生成器實作的。(插句題外話，看看數值的不準确性是如何開始關聯變化并呈指數式增長的，這是一個如帳篷映射這樣的動态系統的關鍵特征)。

<code>... </code><code>while</code> <code>True</code><code>:</code>

<code>... </code><code>yield</code> <code>x</code>

<code>&gt;&gt;&gt; </code><code>for</code> <code>__ </code><code>in</code> <code>xrange</code><code>(</code><code>30</code><code>):</code>

<code>... </code><code>print</code> <code>t.</code><code>next</code><code>()</code>

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

<code>def</code> <code>collatz(n):</code>

<code> </code><code>yield</code> <code>n</code>

<code> </code><code>while</code> <code>n !</code><code>=</code> <code>1</code><code>:</code>

請注意在這個例子中，我們仍舊沒有手動抛出StopIteration異常，因為它會在控制流到達函數結尾的時候自動抛出。

請看用法：

<code>&gt;&gt;&gt; </code><code># If the Collatz conjecture is true then list(collatz(n)) for any n will</code>

<code>... </code><code># always terminate (though your machine might run out of memory first!)</code>

<code>&gt;&gt;&gt; </code><code>list</code><code>(collatz(</code><code>7</code><code>))</code>

<code>&gt;&gt;&gt; </code><code>list</code><code>(collatz(</code><code>13</code><code>))</code>

<code>&gt;&gt;&gt; </code><code>list</code><code>(collatz(</code><code>17</code><code>))</code>

<code>&gt;&gt;&gt; </code><code>list</code><code>(collatz(</code><code>19</code><code>))</code>

<code>Recursive Generators</code>

生成器可以像其它函數那樣遞歸。讓我們來看一個自實作的簡單版本的itertools.permutations，這個生成器通過給定一個item清單生成其全排列(在實際中請使用itertools.permutations，那個實作更快)。基本思想很簡單：對清單中的每一個元素，我們通過将它與清單第一個元素交換将其放置到第一的位置上去，而後重新遞歸排列清單的剩餘部分。

<code>def</code> <code>permutations(items):</code>

<code> </code><code>if</code> <code>len</code><code>(items) </code><code>=</code><code>=</code> <code>0</code><code>:</code>

<code> </code><code>yield</code> <code>[]</code>

<code> </code><code>pi </code><code>=</code> <code>items[:]</code>

<code> </code><code>for</code> <code>i </code><code>in</code> <code>xrange</code><code>(</code><code>len</code><code>(pi)):</code>

<code> </code><code>for</code> <code>p </code><code>in</code> <code>permutations(pi[</code><code>1</code><code>:]):</code>

<code> </code><code>yield</code> <code>[pi[</code><code>0</code><code>]] </code><code>+</code> <code>p</code>

<code>&gt;&gt;&gt; </code><code>for</code> <code>p </code><code>in</code> <code>permutations([</code><code>1</code><code>, </code><code>2</code><code>, </code><code>3</code><code>]):</code>

<code>... </code><code>print</code> <code>p</code>

Generator Expressions

生成器表達式可以讓你通過一個簡單的，單行聲明定義生成器。這跟Python中的清單推導式非常類似，舉個例子，下面的代碼将定義一個生成器疊代所有的完全平方。注意生成器表達式的傳回結果是一個生成器類型對象，它實作了next和__iter__兩個方法。

<code>&gt;&gt;&gt; g </code><code>=</code> <code>(x </code><code>*</code><code>*</code> <code>2</code> <code>for</code> <code>x </code><code>in</code> <code>itertools.count(</code><code>1</code><code>))</code>

<code>&lt;generator </code><code>object</code> <code>&lt;genexpr&gt; at </code><code>0x1029a5fa0</code><code>&gt;</code>

<code>&gt;&gt;&gt; [g.</code><code>next</code><code>() </code><code>for</code> <code>__ </code><code>in</code> <code>xrange</code><code>(</code><code>10</code><code>)]</code>

同樣可以使用生成器表達式實作Bernoulli過程，在這個例子中p=0.4。如果一個生成器表達式需要另一個疊代器作為循環訓示器，并且這個生辰器表達式使用在無限序列上的，那麼itertools.count将是一個很好的選擇。若非如此，xrange将是一個不錯的選擇。

<code>&gt;&gt;&gt; g </code><code>=</code> <code>(random.random() &lt; </code><code>0.4</code> <code>for</code> <code>__ </code><code>in</code> <code>itertools.count())</code>

<code>[</code><code>False</code><code>, </code><code>False</code><code>, </code><code>False</code><code>, </code><code>True</code><code>, </code><code>True</code><code>, </code><code>False</code><code>, </code><code>True</code><code>, </code><code>False</code><code>, </code><code>False</code><code>, </code><code>True</code><code>]</code>

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

<code>&gt;&gt;&gt; </code><code>sum</code><code>(x </code><code>*</code><code>*</code> <code>2</code> <code>for</code> <code>x </code><code>in</code> <code>xrange</code><code>(</code><code>10</code><code>))</code>

更多生成器表達式的例子将在下一節給出。

itertools子產品

itertools子產品提供了一系列疊代器能夠幫助使用者輕松地使用排列、組合、笛卡爾積或其他組合結構。

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

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

<code>from</code> <code>itertools </code><code>import</code> <code>combinations, product</code>

<code>def</code> <code>visit(</code><code>*</code><code>indices):</code>

<code> </code><code>print</code> <code>indices</code>

<code># Loop through all possible indices of a 3-D array</code>

<code>for</code> <code>i </code><code>in</code> <code>xrange</code><code>(n):</code>

<code> </code><code>for</code> <code>j </code><code>in</code> <code>xrange</code><code>(n):</code>

<code> </code><code>for</code> <code>k </code><code>in</code> <code>xrange</code><code>(n):</code>

<code> </code><code>visit(i, j, k)</code>

<code># Equivalent using itertools.product</code>

<code>for</code> <code>indices </code><code>in</code> <code>product(</code><code>*</code><code>([</code><code>xrange</code><code>(n)] </code><code>*</code> <code>d)):</code>

<code> </code><code>visit(</code><code>*</code><code>indices)</code>

<code># Now loop through all indices 0 &lt;= i &lt; j &lt; k &lt;= n</code>

<code> </code><code>for</code> <code>j </code><code>in</code> <code>xrange</code><code>(i </code><code>+</code> <code>1</code><code>, n):</code>

<code> </code><code>for</code> <code>k </code><code>in</code> <code>xrange</code><code>(j </code><code>+</code> <code>1</code><code>, n):</code>

<code># And equivalent using itertools.combinations</code>

<code>for</code> <code>indices </code><code>in</code> <code>combinations(</code><code>xrange</code><code>(n), d):</code>

使用itertools子產品提供的枚舉器有兩個好處：代碼能夠在單行内完成，并且很容易擴充到更高次元。我并未比較for方法和itertools兩種方法的性能，也許跟n有很大關系。如果你想的話請自行測試評判。

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

<code>import</code> <code>itertools</code>

<code>import</code> <code>math</code>

<code>def</code> <code>inversion_number(A):</code>

<code> </code><code>&quot;&quot;&quot;Return the number of inversions </code><code>in</code> <code>list</code> <code>A.&quot;&quot;&quot;</code>

<code> </code><code>return</code> <code>sum</code><code>(</code><code>1</code> <code>for</code> <code>x, y </code><code>in</code> <code>itertools.combinations(</code><code>xrange</code><code>(</code><code>len</code><code>(A)), </code><code>2</code><code>) </code><code>if</code> <code>A[x] &gt; A[y])</code>

<code>def</code> <code>total_inversions(n):</code>

<code> </code><code>&quot;&quot;&quot;Return total number of inversions </code><code>in</code> <code>permutations of n.&quot;&quot;&quot;</code>

<code> </code><code>return</code> <code>sum</code><code>(inversion_number(A) </code><code>for</code> <code>A </code><code>in</code> <code>itertools.permutations(</code><code>xrange</code><code>(n)))</code>

用法如下：

<code>&gt;&gt;&gt; [total_inversions(n) </code><code>for</code> <code>n </code><code>in</code> <code>xrange</code><code>(</code><code>10</code><code>)]</code>

<code>&gt;&gt;&gt; [math.factorial(n) </code><code>*</code> <code>n </code><code>*</code> <code>(n </code><code>-</code> <code>1</code><code>) </code><code>/</code> <code>4</code> <code>for</code> <code>n </code><code>in</code> <code>xrange</code><code>(</code><code>10</code><code>)]</code>

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

<code>def</code> <code>count_fixed_points(p):</code>

<code> </code><code>&quot;&quot;&quot;Return the number of fixed points of p as a permutation.&quot;&quot;&quot;</code>

<code> </code><code>return</code> <code>sum</code><code>(</code><code>1</code> <code>for</code> <code>x </code><code>in</code> <code>p </code><code>if</code> <code>p[x] </code><code>=</code><code>=</code> <code>x)</code>

<code>def</code> <code>count_partial_derangements(n, k):</code>

<code> </code><code>&quot;&quot;&quot;Returns the number of permutations of n with k fixed points.&quot;&quot;&quot;</code>

<code> </code><code>return</code> <code>sum</code><code>(</code><code>1</code> <code>for</code> <code>p </code><code>in</code> <code>itertools.permutations(</code><code>xrange</code><code>(n)) </code><code>if</code> <code>count_fixed_points(p) </code><code>=</code><code>=</code> <code>k)</code>

用法：

<code># Usage:</code>

<code>&gt;&gt;&gt; [count_partial_derangements(</code><code>6</code><code>, i) </code><code>for</code> <code>i </code><code>in</code> <code>xrange</code><code>(</code><code>7</code><code>)]</code>

本文轉自 wt7315 51CTO部落格，原文連結:http://blog.51cto.com/wt7315/1902166

Python進階特性：Iterators、Generators和itertools

繼續閱讀

來自python的【條件控制/語句循環/break/continue/else/pass】一、條件控制二、語句循環

無法解析的外部符号 wmain，該符号在函數 "void cdecl mainCRTStartupHelper(struct HINSTANCE *,unsigned short con......

TestLink導出用例轉換工具(XML2Excel)

YAML簡介和PyYAML安全操作YAML支援的類型YAML的優點：yaml的基本文法python操作

Small tricks

libsvm for python 安裝

學習軟體測試基礎測試第七天

Zeppelin 配置通路 REST APIApache Zeppelin Configuration REST API

【Torch】最簡潔logging使用指南

27. Remove Element(清單)題目代碼

Cloud Studio初體驗

使用 ctypes 進行 Python 和 C 的混合程式設計

【python】【資料處理】畫多元資料分布圖

【python】netconf協定對接管理裝置

「Python 網絡自動化」NETCONF —— Python 使用 NETCONF 管理配置 H3C 網絡裝置

在python中建立excel并寫入