日拱一卒，伯克利教你Python核心技術，迭代器和生成器

語言: CN / TW / HK
時間 2022-06-04 15:15:23

大家好，日拱一卒，我是梁唐。

我們繼續伯克利CS61A公開課之旅，這一次我們討論的是lab11，也就是第11次實驗課。

這節課講的內容是Python當中很重要的兩個概念迭代器和生成器。這兩個是Python當中非常重要的概念，在機器學習、深度學習的程式碼當中也經常使用，算是演算法工程師必學必瞭解的基礎技能之一。因此它有多重要，不用我多說相信大家也能感受到。

這門課每次實驗的題目之前，都有大量的相關技術的說明。將學習和練習非常好得結合在了一起，技術說明和教程的部分質量也很高，雖然篇幅不算很長，但很能囊括重點。也因此，我每次寫文都會將這部分翻譯過來。如果覺得文件中不夠清楚，或者是理解起來有些困難，那麼可以考慮去B站看一下教學影片，會清晰很多。

課程連結

實驗原始文件

我的Github

首先，我們還是先去官方文件當中下載本次實驗用到的檔案。

我們要改動的只有lab11.py和lab11_extra.py，剩餘的檔案都是測試用途，保持原樣即可。

下載完成之後， 讓我們進入正題。

Topics

Iterables and Iterators

迭代器（iterator）是可以被迭代訪問的物件。一種迭代迭代器當中所有元素的方式是for迴圈：

python for item in iteralbe: # do something

for迴圈可以使用在任何可迭代物件（iterable）中。我們之前描述for迴圈的時候，說的是它可以用在任何序列上——所有的序列都是可迭代的。但除了序列之外也有其他物件也是可迭代的。實際上，for迴圈會被直譯器轉錄成類似下面這樣的程式碼：

python iterator = iter(iterable) try: while True: elem = next(iterator) # do something except StopIteration: pass

我們簡單看一下程式碼的細節：

  • 首先，iter是一個內建函式，它應用在可迭代物件上，生成一個對應的迭代器。迭代器是一個可以在可迭代物件上迭代的物件，它會一直記錄下一個被迭代的元素
  • next函式應用在迭代器上，用來獲取序列中的下一個元素
  • 當序列中沒有下一個元素時，會丟擲StopIteration異常。在for迴圈當中，這個異常會被捕獲，程式可以繼續執行

這段描述看起來有一點點亂，主要問題在於可迭代物件和迭代器是兩個概念。比如一個a = [1, 2, 3]，這裡的a是一個可迭代物件，但不是迭代器。我們可以使用iter(a)生成一個能夠迭代a陣列的迭代器。然後用這個迭代器去訪問a陣列。

對同一個可迭代物件呼叫若干次iter會得到多個迭代器，它們之間不會共享狀態（否則我們只能迭代一個可迭代物件一次）。你也可以對一個迭代器呼叫iter，這會返回相同的迭代器，而不會發生任何變化。注意，你不能對一個可迭代物件使用next

讓我們來看看iter和next函式實際應用在一個我們熟悉的可迭代物件——list上的例子。

因為我們可以對迭代器也使用iter，這說明了迭代器本身也是可迭代物件。你可以對任何使用可迭代物件的地方使用迭代器，但要注意的是，迭代器會儲存狀態，你只能通過迭代器迭代一次。

推論：一個可迭代物件就像是一本書（可以在紙張之間翻動瀏覽）而迭代器就像是書籤（儲存位置，可以快速找到下一頁）。對一本書呼叫iter會得到一個書籤，書籤之間彼此互不影響。對書籤本身呼叫iter返回它自身，不會對書籤停留的位置做任何改變。對書籤呼叫next將它移動到下一頁，但不會改變書中的內容。對一本書呼叫next沒有意義，也不符合語法

Iterable uses

我們知道list是一個內建的iterable型別。你也應該用過range(start, end)函式，它會根據start和end建立一個可迭代的升序整數序列。

在很多時候range非常有用，包括重複執行若干次某個特定的操作，也可以很方便地得到一個下標序列。

除此之外，還有很多其他內建的函式，接收一個iterable物件，返回一個有用的結果：

  • map(f, iterable) - 建立一個迭代器，對iterable中的x，得到f(x)
  • filter(f, iterable) - 建立一個迭代器，對iterable中的x，得到所有f(x) == True的x
  • zip(iter1, iter2) - 對iter1中的所有x和iter2中的所有y，建立一個迭代器，得到所有的(x, y)的pair
  • reversed(iterable) - 建立一個迭代器可以反向遍歷iterable
  • list(iterable) - 建立一個list，得到iterable中的所有元素
  • tuple(iterable) - 建立一個tuple，包含iterable中的所有元素
  • sorted(iterable) - 建立一個排好序的list，包含iterable中的所有元素

Generators

生成器

一個生成器函式返回一個特殊的迭代器型別，叫做生成器。生成器函式使用yield語句代替了return語句。呼叫一個生成器函式將會返回一個生成器物件，而不是執行函式中的程式碼。

比如，讓我們看一下下面這個生成器的程式碼：

呼叫countdown將會返回一個生成器物件，這個物件能夠從n數到0。因為生成器都是迭代器，所以我們可以對結果呼叫iter，這會得到一個同樣的物件。注意，函式的主體並沒有執行，螢幕上什麼也沒有輸出，也沒有數字被返回。

那麼，我們如何執行程式呢？因為生成器也是一種迭代器，所以我們可以對它們呼叫next方法！

當next被呼叫的時候，程式會從函式主體的第一行開始執行，一直到遇到yield語句。yield語句之後的內容將被evaluate並返回。

和我們之前介紹的函式不同，生成器會記住狀態。當我們執行多次next的時候，生成器每次會從上一次的yield語句繼續執行。和第一次呼叫next一樣，程式會一直執行直到遇到下一個yield語句。

你能預測我們繼續對c呼叫4次next的結果嗎？

對countdown多次呼叫會建立不同的生成器，它們擁有專屬的狀態。通常，生成器不會重啟。如果你想要重新得到一個序列，你可以建立另外一個生成器物件。

接下來是上面內容的一些總結：

  • 生成器函式擁有yield語句，並且會返回一個生成器物件

  • 對生成器物件呼叫iter會得到一個同樣的物件，並且不會修改生成器的狀態

  • 生成器的函式主體不會被執行，直到呼叫next函式。對一個生成器物件呼叫next函式，會執行並且返回序列中的下一個元素。如果序列已經結束了，丟擲StopIteration異常

  • 生成器會記住下一次執行next時的狀態。

  • 第一次呼叫next時：

    • 進入函式，執行程式知道遇到yield
    • 返回yield語句中的值，記住yield語句的位置

  • 持續呼叫next時：

    • 從上一次yield語句的下一行開始執行，遇見yield停止
    • 返回yield語句中的值，記住當前執行的位置

另外一個很有用的工具是yield from（Python 3.3及以後版本）。yield from 將會從另外一個迭代器或者是可迭代物件當中迭代所有的元素。

Required Questions

WWPD

Q1: WWPD: Iterators

閱讀Python程式碼填寫Python程式碼的輸出。

使用ok命令python3 ok -q iterators -u進行測試，如果你覺得會報錯，輸入Error。如果會遇到StopIteration異常，輸入StopIteration。如果得到一個迭代器，輸入Iterator

```python

s = [1, 2, 3, 4] t = iter(s) next(s)

next(t)

next(t)

iter(s)

next(iter(s))

next(iter(t))

next(iter(s))

next(iter(t))

next(t)

r = range(6) r_iter = iter(r) next(r_iter)

[x + 1 for x in r]

[x + 1 for x in r_iter]

next(r_iter)

list(range(-2, 4)) # Converts an iterable into a list

map_iter = map(lambda x : x + 10, range(5)) next(map_iter)

next(map_iter)

list(map_iter)

for e in filter(lambda x : x % 2 == 0, range(1000, 1008)): ... print(e) ...

[x + y for x, y in zip([1, 2, 3], [4, 5, 6])]

for e in zip([10, 9, 8], range(3)): ... print(tuple(map(lambda x: x + 2, e))) ...

```

題目不算難，但當中有一些題還是挺刁鑽的，需要仔細想想。如果一直做不對可以放到Python直譯器裡執行一下。

Q2: WWPD: Generators

閱讀Python程式碼填寫輸出結果

使用ok命令進行測試：python3 ok -q generators -u

如果程式報錯輸入Error，如果返回的是函式，輸入Function，如果是生成器，輸入Generator

```python def gen(): print("Starting here") i = 0 while i < 6: print("Before yield") yield i print("After yield") i += 1

next(gen)

gen

g = gen() g

g == iter(g)

next(g)

next(g)

next(g)

g2 = gen() next(g2)

iter(g2)

next(iter(g))

next(gen())

```

關於生成器的基礎問題，幾乎沒有難度。

Coding Practice

Q3: Scale

實現生成器函式scale(s, k)，它從給定的可迭代物件s中yield元素，再乘上k。作為特別挑戰，試著使用yield from實現函式！

```python def scale(s, k): """Yield elements of the iterable s scaled by a number k.

>>> s = scale([1, 5, 2], 5)
>>> type(s)
<class 'generator'>
>>> list(s)
[5, 25, 10]

>>> m = scale(naturals(), 2)
>>> [next(m) for _ in range(5)]
[2, 4, 6, 8, 10]
"""
"*** YOUR CODE HERE ***"

```

使用ok進行測試：python3 ok -q scale

答案

我們可以使用for迴圈迭代一個可迭代物件，將拿到的結果yield即可。

python def scale(s, k): for i in s: yield i * k

如果要使用yield from語句來完成，需要得到一個新的迭代物件，這個迭代物件裡的結果是s中的結果再乘上k。那麼我們有沒有辦法可以得到這個迭代物件呢？

當然是有的，就是使用map函式：

python def scale(s, k): yield from map(lambda x: x * k, s)

Q4: Trap

實現一個生成器函式，可以yield可迭代物件s中前k個元素。當s中沒有元素時丟擲ValueError異常。你可以假設s至少有k個元素。

```python def trap(s, k): """Return a generator that yields the first K values in iterable S, but raises a ValueError exception if any more values are requested.

>>> t = trap([3, 2, 1], 2)
>>> next(t)
3
>>> next(t)
2
>>> next(t)
ValueError
>>> list(trap(range(5), 5))
ValueError
>>> t2 = trap(map(abs, reversed(range(-6, -4))), 2)
>>> next(t2)
5
>>> next(t2)
6
>>> next(t2)
ValueError
"""
"*** YOUR CODE HERE ***"

```

使用ok命令進行測試：python3 ok -q trap

答案

我們先對s生成一個迭代器，然後使用迴圈yield``k次，最後丟擲異常即可。

python def trap(s, k): it = iter(s) for _ in range(k): yield next(it) raise ValueError("no more values")

Optional Questions

選做題，這部分在lab11_extra.py中

Q5: Hailstone

實現一個生成器，使得能夠返回作業1中的hailstone序列。

下面是關於hailstone序列的一個快速回顧：

  1. 選擇一個正整數n作為開始
  2. 如果n是偶數，將它除以2
  3. 如果n是奇數，將它乘3再加1
  4. 重複以上過程，直到n等於1

python def hailstone(n): """ >>> for num in hailstone(10): ... print(num) ... 10 5 16 8 4 2 1 """ "*** YOUR CODE HERE ***"

使用ok命令進行測試：python3 ok -q hailstone

答案

生成器的簡單應用，照著題意實現即可。

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

Q6: Repeated

實現一個函式（不是生成器），返回可迭代物件t中第一個重複k次的元素。

```python def repeated(t, k): """Return the first value in iterable T that appears K times in a row.

>>> s = [3, 2, 1, 2, 1, 4, 4, 5, 5, 5]
>>> repeated(trap(s, 7), 2)
4
>>> repeated(trap(s, 10), 3)
5
>>> print(repeated([4, None, None, None], 3))
None
"""
assert k > 1
"*** YOUR CODE HERE ***"

```

使用ok命令進行測試：python3 ok -q repeated

答案

因為測試樣例陣列中的元素存在None，為了嚴謹起見，所以我們先建立迭代器，取出t中的第一個元素作為last

python def repeated(t, k): assert k > 1 "*** YOUR CODE HERE ***" it = iter(t) last, cnt = next(it), 1 for i in it: if i == last: cnt += 1 if cnt == k: return i else: last, cnt = i, 1

Q7: Merge

實現merge(s0, s1)，接收兩個可迭代物件s0和s1，它們的元素都是有序的。merge按順序從s0和s1中yield元素 ，消除重複。你可以假設s0和s1當中本身沒有重複，並沒有不為空。你不能假設元素是有限的，有可能其中一個是一個無窮的資料流。

你可能會用到next(s, v)和next元素差不多，唯一不同的是當s沒有元素的時候，不會丟擲異常，而是會返回v。

檢視doctest獲得更多資訊

```python def merge(s0, s1): """Yield the elements of strictly increasing iterables s0 and s1, removing repeats. Assume that s0 and s1 have no repeats. s0 or s1 may be infinite sequences.

>>> m = merge([0, 2, 4, 6, 8, 10, 12, 14], [0, 3, 6, 9, 12, 15])
>>> type(m)
<class 'generator'>
>>> list(m)
[0, 2, 3, 4, 6, 8, 9, 10, 12, 14, 15]
>>> def big(n):
...    k = 0
...    while True: yield k; k += n
>>> m = merge(big(2), big(3))
>>> [next(m) for _ in range(11)]
[0, 2, 3, 4, 6, 8, 9, 10, 12, 14, 15]
"""
i0, i1 = iter(s0), iter(s1)
e0, e1 = next(i0, None), next(i1, None)
"*** YOUR CODE HERE ***"

```

使用ok來進行測試：python3 ok -q merge

答案

本來想用遞迴來搞定，但是存在一個問題，就是已經next取出來的元素沒辦法再放回去，遞迴求解會導致遺漏部分元素，所以只能使用迭代的方法。

最外層的迴圈條件時當兩個元素不同時為None時執行，然後我們依次判斷兩個元素是否有空，以及元素之間大小關係即可。

python def merge(s0, s1): i0, i1 = iter(s0), iter(s1) e0, e1 = next(i0, None), next(i1, None) "*** YOUR CODE HERE ***" while e0 is not None or e1 is not None: if e0 is None: yield e1 e1 = next(i1, None) elif e1 is None: yield e0 e0 = next(i0, None) else: if e0 == e1: yield e0 e0, e1 = next(i0, None), next(i1, None) elif e0 < e1: yield e0 e0 = next(i0, None) else: yield e1 e1 = next(i1, None)

Q8: Remainder Generator

就像函式一樣，生成器也可以是高階的。對於這個問題，我們需要實現一個remainders_generator函式，它從一系列生成器物件當中獲取元素。

remainders_generator讀入一個整數m，yield m個不同的生成器。第一個生成器是m的倍數（對m取模餘數為0），第二個生成器是對m取模餘數為1的生成器，以此類推。

```python def remainders_generator(m): """ Takes in an integer m, and yields m different remainder groups of m.

>>> remainders_mod_four = remainders_generator(4)
>>> for rem_group in remainders_mod_four:
...     for _ in range(3):
...         print(next(rem_group))
0
4
8
1
5
9
2
6
10
3
7
11
"""
"*** YOUR CODE HERE ***"

```

注意，如果你實現正確的話，每一個通過remainder_generator得到的生成器都是無限的。你可以一直呼叫next而不會得到StopIteration異常。

提示：考慮定義一個innder生成器函式，它應該讀入什麼引數？你在哪裡呼叫它呢？

使用ok命令來進行測試：python3 ok -q remainders_generator

答案

我們在一個生成器內部實現一個生成器，然後在外部呼叫內部的生成器，返回生成器物件。

```python def remainders_generator(m): def inner(r): while True: yield r r += m

for i in range(m):
    yield inner(i)

```

Q9: Zip Generator

實現zip_generator生成器，它接收一系列可迭代物件。第n次yield的結果是一個list，是傳入資料中下標n的集合。當最短的可迭代物件元素為空時停止

python def zip_generator(*iterables): """ Takes in any number of iterables and zips them together. Returns a generator that outputs a series of lists, each containing the nth items of each iterable. >>> z = zip_generator([1, 2, 3], [4, 5, 6], [7, 8]) >>> for i in z: ... print(i) ... [1, 4, 7] [2, 5, 8] """ "*** YOUR CODE HERE ***"

使用ok命令進行測試：python3 ok -q zip_generator

答案

傳入的引數是可迭代物件，而不是迭代器，所以我們要先建立它們的迭代器。

之後我們使用while無限迴圈，每次yield所有迭代器執行next之後的結果。當有迭代器沒有元素時next會丟擲異常，由於我們沒有捕獲異常，這個異常會繼續往上丟擲，實現停止的效果。

python def zip_generator(*iterables): itors = [iter(it) for it in iterables] while True: yield [next(it) for it in itors]

「」
「」