摘要：消息向迭代器獲取所表示的底層序列的下一個元素。為了對方法調用做出回應，迭代器可以執行任何計算來獲取或計算底層數據序列的下一個元素。這個迭代器應擁有方法，依次返回序列中的每個元素，最后到達序列末尾時產生異常。

來源：Chapter 5: Sequences and Coroutines
譯者：飛龍
協議：CC BY-NC-SA 4.0

在這一章中，我們通過開發新的工具來處理有序數據，繼續討論真實世界中的應用。在第二張中，我們介紹了序列接口，在 Python 內置的數據類型例如tuple和list中實現。序列支持兩個操作：獲取長度和由下標訪問元素。第三章中，我們開發了序列接口的用戶定義實現，用于表示遞歸列表的Rlist類。序列類型具有高效的表現力，并且可以讓我們高效訪問大量有序數據集。

但是，使用序列抽象表示有序數據有兩個重要限制。第一個是長度為n的序列的要占據比例為n的內存總數。于是，序列越長，表示它所占的內存空間就越大。

第二個限制是，序列只能表示已知且長度有限的數據集。許多我們想要表示的有序集合并沒有定義好的長度，甚至有些是無限的。兩個無限序列的數學示例是正整數和斐波那契數。無限長度的有序數據集也出現在其它計算領域，例如，所有推特狀態的序列每秒都在增長，所以并沒有固定的長度。與之類似，經過基站發送出的電話呼叫序列，由計算機用戶發出的鼠標動作序列，以及飛機上的傳感器產生的加速度測量值序列，都在世界演化過程中無限擴展。

在這一章中，我們介紹了新的構造方式用于處理有序數據，它為容納未知或無限長度的集合而設計，但僅僅使用有限的內存。我們也會討論這些工具如何用于一種叫做協程的程序結構，來創建高效、模塊化的數據處理流水線。

序列可以使用一種程序結構來表示，它不將每個元素顯式儲存在內存中，這是高效處理有序數據的核心概念。為了將這個概念用于實踐，我們需要構造對象來提供序列中所有元素的訪問，但是不要事先把所有元素計算出來并儲存。

這個概念的一個簡單示例就是第二章出現的range序列類型。range表示連續有界的整數序列。但是，它的每個元素并不顯式在內存中表示，當元素從range中獲取時，才被計算出來。所以，我們可以表示非常大的整數范圍。只有范圍的結束位置才被儲存為range對象的一部分，元素都被憑空計算出來。

>>> r = range(10000, 1000000000)
>>> r[45006230]
45016230

這個例子中，當構造范圍示例時，并不是這個范圍內的所有 999,990,000 個整數都被儲存。反之，范圍對象將第一個元素 10,000 與下標相加 45,006,230 來產生第 45,016,230 個元素。計算所求的元素值并不從現有的表示中獲取，這是惰性計算的一個例子。計算機科學將惰性作為一種重要的計算工具加以贊揚。

迭代器是提供底層有序數據集的有序訪問的對象。迭代器在許多編程語言中都是內建對象，包括 Python。迭代器抽象擁有兩個組成部分：一種獲取底層元素序列的下一個元素的機制，以及一種標識元素序列已經到達末尾，沒有更多剩余元素的機制。在帶有內建對象系統的編程語言中，這個抽象通常相當于可以由類實現的特定接口。Python 的迭代器接口會在下一節中描述。

迭代器的實用性來源于一個事實，底層數據序列并不能顯式在內存中表達。迭代器提供了一種機制，可以依次計算序列中的每個值，但是所有元素不需要連續儲存。反之，當下個元素從迭代器獲取的時候，這個元素會按照請求計算，而不是從現有的內存來源中獲取。

范圍可以惰性計算序列中的元素，因為序列的表示是統一的，并且任何元素都可以輕易從范圍的起始和結束位置計算出來。迭代器支持更廣泛的底層有序數據集的惰性生成，因為它們不需要提供底層序列任意元素的訪問途徑。反之，它們僅僅需要按照順序，在每次其它元素被請求的時候，計算出序列的下一個元素。雖然不像序列可訪問任意元素那樣靈活（叫做隨機訪問），有序數據序列的順序訪問對于數據處理應用來說已經足夠了。

Python 迭代器接口包含兩個消息。__next__消息向迭代器獲取所表示的底層序列的下一個元素。為了對__next__方法調用做出回應，迭代器可以執行任何計算來獲取或計算底層數據序列的下一個元素。__next__的調用讓迭代器產生變化：它們向前移動迭代器的位置。所以多次調用__next__會有序返回底層序列的元素。在__next__的調用過程中，Python 通過StopIteration異常，來表示底層數據序列已經到達末尾。

下面的Letters類迭代了從a到d字母的底層序列。成員變量current儲存了序列中的當前字母。__next__方法返回這個字母，并且使用它來計算current的新值。

>>> class Letters(object):
        def __init__(self):
            self.current = "a"
        def __next__(self):
            if self.current > "d":
                raise StopIteration
            result = self.current
            self.current = chr(ord(result)+1)
            return result
        def __iter__(self):
            return self

__iter__消息是 Python 迭代器所需的第二個消息。它只是簡單返回迭代器，它對于提供迭代器和序列的通用接口很有用，在下一節會描述。

使用這個類，我們就可以訪問序列中的字母：

>>> letters = Letters()
>>> letters.__next__()
"a"
>>> letters.__next__()
"b"
>>> letters.__next__()
"c"
>>> letters.__next__()
"d"
>>> letters.__next__()
Traceback (most recent call last):
  File "", line 1, in 
  File "", line 12, in next
StopIteration

Letters示例只能迭代一次。一旦__next__()方法產生了StopIteration異常，它就從此之后一直這樣了。除非創建新的實例，否則沒有辦法來重置它。

迭代器也允許我們表示無限序列，通過實現永遠不會產生StopIteration異常的__next__方法。例如，下面展示的Positives類迭代了正整數的無限序列：

>>> class Positives(object):
        def __init__(self):
            self.current = 0;
        def __next__(self):
            result = self.current
            self.current += 1
            return result
        def __iter__(self):
            return self

Python 中，序列可以通過實現__iter__消息用于迭代。如果一個對象表示有序數據，它可以在for語句中用作可迭代對象，通過回應__iter__消息來返回迭代器。這個迭代器應擁有__next__()方法，依次返回序列中的每個元素，最后到達序列末尾時產生StopIteration異常。

>>> counts = [1, 2, 3]
>>> for item in counts:
        print(item)
1
2
3

在上面的實例中，counts列表返回了迭代器，作為__iter__()方法調用的回應。for語句之后反復調用迭代器的__next__()方法，并且每次都將返回值賦給item。這個過程一直持續，直到迭代器產生了StopIteration異常，這時for語句就終止了。

使用我們關于迭代器的知識，我們可以拿while、賦值和try語句實現for語句的求值規則：

>>> i = counts.__iter__()
>>> try:
        while True:
            item = i.__next__()
            print(item)
    except StopIteration:
        pass
1
2
3

在上面，調用counts的__iter__方法所返回的迭代器綁定到了名稱i上面，便于依次獲取每個元素。StopIteration異常的處理子句不做任何事情，但是這個異常的處理提供了退出while循環的控制機制。

上面的Letters和Positives對象需要我們引入一種新的字段，self.current，來跟蹤序列的處理過程。在上面所示的簡單序列中，這可以輕易實現。但對于復雜序列，__next__()很難在計算中節省空間。生成器允許我們通過利用 Python 解釋器的特性定義更復雜的迭代。

生成器是由一類特殊函數，叫做生成器函數返回的迭代器。生成器函數不同于普通的函數，因為它不在函數體中包含return語句，而是使用yield語句來返回序列中的元素。

生成器不使用任何對象屬性來跟蹤序列的處理過程。它們控制生成器函數的執行，每次__next__方法調用時，它們執行到下一個yield語句。Letters迭代可以使用生成器函數實現得更加簡潔。

>>> def letters_generator():
        current = "a"
        while current <= "d":
            yield current
            current = chr(ord(current)+1)
>>> for letter in letters_generator():
        print(letter)
a
b
c
d

即使我們永不顯式定義__iter__()或__next__()方法，Python 會理解當我們使用yield語句時，我們打算定義生成器函數。調用時，生成器函數并不返回特定的產出值，而是返回一個生成器（一種迭代器），它自己就可以返回產出的值。生成器對象擁有__iter__和__next__方法，每個對__next__的調用都會從上次停留的地方繼續執行生成器函數，直到另一個yield語句執行的地方。

__next__第一次調用時，程序從letters_generator的函數體一直執行到進入yield語句。之后，它暫停并返回current值。yield語句并不破壞新創建的環境，而是為之后的使用保留了它。當__next__再次調用時，執行在它停留的地方恢復。letters_generator作用域中current和任何所綁定名稱的值都會在隨后的__next__調用中保留。

我們可以通過手動調用__next__()來遍歷生成器：

>>> letters = letters_generator()
>>> type(letters)

>>> letters.__next__()
"a"
>>> letters.__next__()
"b"
>>> letters.__next__()
"c"
>>> letters.__next__()
"d"
>>> letters.__next__()
Traceback (most recent call last):
  File "", line 1, in 
StopIteration

在第一次__next__()調用之前，生成器并不會開始執行任何生成器函數體中的語句。

Python 中，迭代只會遍歷一次底層序列的元素。在遍歷之后，迭代器在__next__()調用時會產生StopIteration異常。許多應用需要迭代多次元素。例如，我們需要對一個列表迭代多次來枚舉所有的元素偶對：

>>> def all_pairs(s):
        for item1 in s:
            for item2 in s:
                yield (item1, item2)
>>> list(all_pairs([1, 2, 3]))
[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]

序列本身不是迭代器，但是它是可迭代對象。Python 的可迭代接口只包含一個消息，__iter__，返回一個迭代器。Python 中內建的序列類型在__iter__方法調用時，返回迭代器的新實例。如果一個可迭代對象在每次調用__iter__時返回了迭代器的新實例，那么它就能被迭代多次。

新的可迭代類可以通過實現可迭代接口來定義。例如，下面的可迭代對象LetterIterable類在每次調用__iter__時返回新的迭代器來迭代字母。

>>> class LetterIterable(object):
        def __iter__(self):
            current = "a"
            while current <= "d":
                yield current
                current = chr(ord(current)+1)

__iter__方法是個生成器函數，它返回一個生成器對象，產出從"a"到"d"的字母。

Letters迭代器對象在單次迭代之后就被“用完”了，但是LetterIterable對象可被迭代多次。所以，LetterIterable示例可以用于all_pairs的參數。

>>> letters = LetterIterable()
>>> all_pairs(letters).__next__()
("a", "a")

流提供了一種隱式表示有序數據的最終方式。流是惰性計算的遞歸列表。就像第三章的Rlist類那樣，Stream實例可以響應對其第一個元素和剩余部分的獲取請求。同樣，Stream的剩余部分還是Stream。然而不像RList，流的剩余部分只在查找時被計算，而不是事先存儲。也就是說流的剩余部分是惰性計算的。

為了完成這個惰性求值，流會儲存計算剩余部分的函數。無論這個函數在什么時候調用，它的返回值都作為流的一部分，儲存在叫做_rest的屬性中。下劃線表示它不應直接訪問?？稍L問的屬性rest是個方法，它返回流的剩余部分，并在必要時計算它。使用這個設計，流可以儲存計算剩余部分的方式，而不用總是顯式儲存它們。

>>> class Stream(object):
        """A lazily computed recursive list."""
        def __init__(self, first, compute_rest, empty=False):
            self.first = first
            self._compute_rest = compute_rest
            self.empty = empty
            self._rest = None
            self._computed = False
        @property
        def rest(self):
            """Return the rest of the stream, computing it if necessary."""
            assert not self.empty, "Empty streams have no rest."
            if not self._computed:
                self._rest = self._compute_rest()
                self._computed = True
            return self._rest
        def __repr__(self):
            if self.empty:
                return ""
            return "Stream({0}, )".format(repr(self.first))
>>> Stream.empty = Stream(None, None, True)

遞歸列表可使用嵌套表達式來定義。例如，我們可以創建RList，來表達1和5的序列，像下面這樣：

>>> r = Rlist(1, Rlist(2+3, Rlist.empty))

與之類似，我們可以創建一個Stream來表示相同序列。Stream在請求剩余部分之前，并不會實際計算下一個元素5。

>>> s = Stream(1, lambda: Stream(2+3, lambda: Stream.empty))

這里，1是流的第一個元素，后面的lambda表達式是用于計算流的剩余部分的函數。被計算的流的第二個元素又是一個返回空流的函數。

訪問遞歸列表r和流s中的元素擁有相似的過程。但是，5儲存在了r之中，而對于s來說，它在首次被請求時通過加法來按要求計算。

>>> r.first
1
>>> s.first
1
>>> r.rest.first
5
>>> s.rest.first
5
>>> r.rest
Rlist(5)
>>> s.rest
Stream(5, )

當make_integer_stream首次被調用時，它返回了一個流，流的first是序列中第一個整數（默認為1）。但是，make_integer_stream實際是遞歸的，因為這個流的compute_rest以自增的參數再次調用了make_integer_stream。這會讓make_integer_stream變成遞歸的，同時也是惰性的。

>>> ints.first
1
>>> ints.rest.first
2
>>> ints.rest.rest
Stream(3, )

無論何時請求整數流的rest，都僅僅遞歸調用make_integer_stream。

操作序列的相同高階函數 -- map和filter -- 同樣可應用于流，雖然它們的實現必須修改來惰性調用它們的參數函數。map_stream在一個流上映射函數，這會產生一個新的流。局部定義的compute_rest函數確保了無論什么時候rest被計算出來，這個函數都會在流的剩余部分上映射。

>>> def map_stream(fn, s):
        if s.empty:
            return s
        def compute_rest():
            return map_stream(fn, s.rest)
        return Stream(fn(s.first), compute_rest)

流可以通過定義compute_rest函數來過濾，這個函數在流的剩余部分上調用過濾器函數。如果過濾器函數拒絕了流的第一個元素，剩余部分會立即計算出來。因為filter_stream是遞歸的，剩余部分可能會多次計算直到找到了有效的first元素。

>>> def filter_stream(fn, s):
        if s.empty:
            return s
        def compute_rest():
            return filter_stream(fn, s.rest)
        if fn(s.first):
            return Stream(s.first, compute_rest)
        return compute_rest()

map_stream和filter_stream展示了流式處理的常見模式：無論流的剩余部分何時被計算，局部定義的compute_rest函數都會對流的剩余部分遞歸調用某個處理函數。

為了觀察流的內容，我們需要將其截斷為有限長度，并轉換為 Python list。

>>> def truncate_stream(s, k):
        if s.empty or k == 0:
            return Stream.empty
        def compute_rest():
            return truncate_stream(s.rest, k-1)
        return Stream(s.first, compute_rest)
>>> def stream_to_list(s):
        r = []
        while not s.empty:
            r.append(s.first)
            s = s.rest
        return r

這些便利的函數允許我們驗證map_stream的實現，使用一個非常簡單的例子，從3到7的整數平方。

>>> s = make_integer_stream(3)
>>> s
Stream(3, )
>>> m = map_stream(lambda x: x*x, s)
>>> m
Stream(9, )
>>> stream_to_list(truncate_stream(m, 5))
[9, 16, 25, 36, 49]

我們可以使用我們的filter_stream函數來定義素數流，使用埃拉托斯特尼篩法（sieve of Eratosthenes），它對整數流進行過濾，移除第一個元素的所有倍數數值。通過成功過濾出每個素數，所有合數都從流中移除了。

>>> def primes(pos_stream):
        def not_divible(x):
            return x % pos_stream.first != 0
        def compute_rest():
            return primes(filter_stream(not_divible, pos_stream.rest))
        return Stream(pos_stream.first, compute_rest)

通過截斷primes流，我們可以枚舉素數的任意前綴：

>>> p1 = primes(make_integer_stream(2))
>>> stream_to_list(truncate_stream(p1, 7))
[2, 3, 5, 7, 11, 13, 17]

流和迭代器不同，因為它們可以多次傳遞給純函數，并且每次都產生相同的值。素數流并沒有在轉換為列表之后“用完”。也就是說，在將流的前綴轉換為列表之后，p1的第一個元素仍舊是2。

>>> p1.first
2

就像遞歸列表提供了序列抽象的簡單實現，流提供了簡單、函數式的遞歸數據結構，它通過高階函數的使用實現了惰性求值。

這篇文章的大部分專注于將復雜程序解構為小型、模塊化組件的技巧。當一個帶有復雜行為的函數邏輯劃分為幾個獨立的、本身為函數的步驟時，這些函數叫做輔助函數或者子過程。子過程由主函數調用，主函數負責協調子函數的使用。

這一節中，我們使用協程，引入了一種不同的方式來解構復雜的計算。它是一種針對有序數據的任務處理方式。就像子過程那樣，協程會計算復雜計算的一小步。但是，在使用協程時，沒有主函數來協調結果。反之，協程會自發鏈接到一起來組成流水線?？赡苡幸恍﹨f程消耗輸入數據，并把它發送到其它協程。也可能有一些協程，每個都對發送給它的數據執行簡單的處理步驟。最后可能有另外一些協程輸出最終結果。

協程和子過程的差異是概念上的：子過程在主函數中位于下級，但是協程都是平等的，它們協作組成流水線，不帶有任何上級函數來負責以特定順序調用它們。

這一節中，我們會學到 Python 如何通過yield和send()語句來支持協程的構建。之后，我們會看到協程在流水線中的不同作用，以及協程如何支持多任務。

在之前一節中，我們介紹了生成器函數，它使用yield來返回一個值。Python 的生成器函數也可以使用(yield)語句來接受一個值。生成器對象上有兩個額外的方法：send()和close()，創建了一個模型使對象可以消耗或產出值。定義了這些對象的生成器函數叫做協程。

協程可以通過(yield)語句來消耗值，向像下面這樣：

value = (yield)

使用這個語法，在帶參數調用對象的send方法之前，執行流會停留在這條語句上。

coroutine.send(data)

之后，執行會恢復，value會被賦為data的值。為了發射計算終止的信號，我們需要使用close()方法來關閉協程。這會在協程內部產生GeneratorExit異常，它可以由try/except子句來捕獲。

下面的例子展示了這些概念。它是一個協程，用于打印匹配所提供的模式串的字符串。

>>> def match(pattern):
        print("Looking for " + pattern)
        try:
            while True:
                s = (yield)
                if pattern in s:
                    print(s)
        except GeneratorExit:
            print("=== Done ===")

我們可以使用一個模式串來初始化它，之后調用__next__()來開始執行：

>>> m = match("Jabberwock")
>>> m.__next__()
Looking for Jabberwock

對__next__()的調用會執行函數體，所以"Looking for jabberwock"會被打印。語句會一直持續執行，直到遇到line = (yield)語句。之后，執行會暫停，并且等待一個發送給m的值。我們可以使用send來將值發送給它。

>>> m.send("the Jabberwock with eyes of flame")
the Jabberwock with eyes of flame
>>> m.send("came whiffling through the tulgey wood")
>>> m.send("and burbled as it came")
>>> m.close()
=== Done ===

當我們以一個值調用m.send時，協程m內部的求值會在line = (yield)語句處恢復，這里會把發送的值賦給line變量。m中的語句會繼續求值，如果匹配的話會打印出那一行，并繼續執行循環，直到再次進入line = (yield)。之后，m中的求值會暫停，并在m.send調用后恢復。

我們可以將使用send()和yield的函數鏈到一起來完成復雜的行為。例如，下面的函數將名為text的字符串分割為單詞，并把每個單詞發送給另一個協程。

每個單詞都發送給了綁定到next_coroutine的協程，使next_coroutine開始執行，而且這個函數暫停并等待。它在next_coroutine暫停之前會一直等待，隨后這個函數恢復執行，發送下一個單詞或執行完畢。

如果我們將上面定義的match和這個函數鏈到一起，我們就可以創建出一個程序，只打印出匹配特定單詞的單詞。

>>> text = "Commending spending is offending to people pending lending!"
>>> matcher = match("ending")
>>> matcher.__next__()
Looking for ending
>>> read(text, matcher)
Commending
spending
offending
pending
lending!
=== Done ===

read函數向協程matcher發送每個單詞，協程打印出任何匹配pattern的輸入。在matcher協程中，s = (yield)一行等待每個發送進來的單詞，并且在執行到這一行之后將控制流交還給read。

協程基于如何使用yield和send()而具有不同的作用：

生產者創建序列中的物品，并使用send()，而不是(yield)。

過濾器使用(yield)來消耗物品并將結果使用send()發送給下一個步驟。

消費者使用(yield)來消耗物品，但是從不發送。

上面的read函數是一個生產者的例子。它不使用(yield)，但是使用send來生產數據。函數match是個消費者的例子。它不使用send發送任何東西，但是使用(yield)來消耗數據。我們可以將match拆分為過濾器和消費者。過濾器是一個協程，只發送與它的模式相匹配的字符串。

>>> def match_filter(pattern, next_coroutine):
        print("Looking for " + pattern)
        try:
            while True:
                s = (yield)
                if pattern in s:
                    next_coroutine.send(s)
        except GeneratorExit:
            next_coroutine.close()

消費者是一個函數，只打印出發送給它的行：

>>> def print_consumer():
        print("Preparing to print")
        try:
            while True:
                line = (yield)
                print(line)
        except GeneratorExit:
            print("=== Done ===")

當過濾器或消費者被構建時，必須調用它的__next__方法來開始執行：

>>> printer = print_consumer()
>>> printer.__next__()
Preparing to print
>>> matcher = match_filter("pend", printer)
>>> matcher.__next__()
Looking for pend
>>> read(text, matcher)
spending
pending
=== Done ===

即使名稱filter暗示移除元素，過濾器也可以轉換元素。下面的函數是個轉換元素的過濾器的示例。它消耗字符串并發送一個字典，包含了每個不同的字母在字符串中的出現次數。

>>> def count_letters(next_coroutine):
        try:
            while True:
                s = (yield)
                counts = {letter:s.count(letter) for letter in set(s)}
                next_coroutine.send(counts)
        except GeneratorExit as e:
            next_coroutine.close()

我們可以使用它來計算文本中最常出現的字母，并使用一個消費者，將字典合并來找出最常出現的鍵。

>>> def sum_dictionaries():
        total = {}
        try:
            while True:
                counts = (yield)
                for letter, count in counts.items():
                    total[letter] = count + total.get(letter, 0)
        except GeneratorExit:
            max_letter = max(total.items(), key=lambda t: t[1])[0]
            print("Most frequent letter: " + max_letter)

為了在文件上運行這個流水線，我們必須首先按行讀取文件。之后，將結果發送給count_letters，最后發送給sum_dictionaries。我們可以服用read協程來讀取文件中的行。

>>> s = sum_dictionaries()
>>> s.__next__()
>>> c = count_letters(s)
>>> c.__next__()
>>> read(text, c)
Most frequent letter: n

生產者或過濾器并不受限于唯一的下游。它可以擁有多個協程作為它的下游，并使用send()向它們發送數據。例如，下面是read的一個版本，向多個下游發送字符串中的單詞：

>>> def read_to_many(text, coroutines):
        for word in text.split():
            for coroutine in coroutines:
                coroutine.send(word)
        for coroutine in coroutines:
            coroutine.close()

我們可以使用它來檢測多個單詞中的相同文本：

>>> m = match("mend")
>>> m.__next__()
Looking for mend
>>> p = match("pe")
>>> p.__next__()
Looking for pe
>>> read_to_many(text, [m, p])
Commending
spending
people
pending
=== Done ===
=== Done ===

首先，read_to_many在m上調用了send(word)。這個協程正在等待循環中的text = (yield)，之后打印出所發現的匹配，并且等待下一個send。之后執行流返回到了read_to_many，它向p發送相同的行。所以，text中的單詞會按照順序打印出來。