朱廣蔚 ·Python 中的生成器實現原理
1. 如何生成一個巨大的序列
1.1 需求描述
要求生成一個包含很多元素的序列，假設：
- 存儲 1 個整數需要 4 個字節
- 現在要創建一個包含 1 G 個整數的序列，從 0 到 1 * 1024 * 1024 * 1024 - 1
- 如果需要為序列中的每個整數分配內存，則需要分配的內存為 1G * 4 = 4G
1.2 通過列表推導
Python 提供了列表推導用于生成列表，下面使用列表推導生成一個包含 0 到 4 之間所有整數的列表，代碼如下：
>>> list = [i for i in range(4)]
>>> list
[0, 1, 2, 3]
- 在第 1 行，使用列表推導創建一個包含 4 個元素的列表
- 在第 2 行，顯示新創建的列表
- 在第 3 行，創建了一個包含 0、1、2、3 等 4 個元素的列表
如果生成一個從 0 到 1G 的列表，代碼如下：
>>> N = 1024 * 1024 * 1024
>>> list = [i for i in range(N)]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "<stdin>", line 1, in <listcomp>
MemoryError
- 在第 1 行，設定 N 為 1G
- 在第 2 行，使用列表推導創建一個包含 N 個元素的列表
- 在第 6 行，程序運行出錯，提示 MemoryError
使用列表推導創建包含 1G 個整數的列表時，需要為這 1G 個整數分配至少 4G 的內存，需要消耗大量的內存，超出了 Python 的限制，因此出現了 MemoryError 的錯誤。
另外，創建這個巨大的列表需要消耗大量的時間，因此執行第 2 行的語句后，系統失去響應，大約 10 多秒后才出現錯誤信息。
1.3 通過動態計算
列表推導需要一次性的為 1G 個整數分配內存空間，帶來了兩個問題：
- 列表占用了大量的物理內存
- 創建列表的時間過長
Python 提供了一種動態計算的思路解決以上問題，它的思想如下：
- 要生成的序列是有規則的，在這個例子中，要求生成連續遞增的序列
- 使用一個特殊的對象 generator，該對象被稱為生成器 generator，生成器按照規則依次輸出該序列
- Python 提供了內置方法 next(generator)，該方法通知生成器產生下一個數據并返回該數據
- 不需要為 generator 預先分配內存，通過調用 next(generator) 可以動態獲取序列的下一個數據
創建一個輸出從 0 到 1G 的生成器，代碼如下：
>>> N = 1024 * 1024 * 1024
>>> generator = (i for i in range(N))
>>> next(generator)
0
>>> next(generator)
1
>>> next(generator)
2
- 在第 1 行，設定 N 為 1G
- 在第 2 行，使用類似于列表推導的語法創建一個生成器，它輸出從 0 到 1G 的序列
- 注意：創建生成器的語法采用小括號 ()，創建列表的語法采用方括號 []
- 在第 3 行，使用 next(generator)，通知 generator 生產一個數據
- 在第 4 行，generator 輸出從 0 到 1G 序列中的第 0 個整數
- 在第 5 行，使用 next(generator)，通知 generator 生產一個數據
- 在第 6 行，generator 輸出從 0 到 1G 序列中的第 1 個整數
- 在第 7 行，使用 next(generator)，通知 generator 生產一個數據
- 在第 8 行，generator 輸出從 0 到 1G 序列中的第 2 個整數
注意：在第 2 行，創建一個輸出從 0 到 1G 的序列的生成器，因為不需要分配內存，創建生成器的速度非?？欤瑤缀跏撬查g完成的。與之相比，在上一節中創建一個輸出從 0 到 1G 的序列的列表，因為需要分配內存，創建列表的速度非常慢，并且導致了 MemoryError。
2. 生成器概述
2.1 生成器的定義
在 Python 中，生成器是一個特殊的對象，它按照一定的規則依次輸出數據。Python 的內置函數 next(generator) 通知生成器輸出一個新的數據，當生成器輸出全部數據后，產生一個特殊的異常 StopIteration，用于標記生成器輸出結束。
下面的代碼創建一個產生 0 到 3 之間所有整數的生成器：
>>> generator = (i for i in range(3))
>>> next(generator)
0
>>> next(generator)
1
>>> next(generator)
2
>>> next(generator)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
StopIteration
- 在第 1 行，創建一個產生 0 到 3 之間所有整數的生成器
- 注意：創建生成器的語法采用小括號 ()，創建列表的語法采用方括號 []
- 在第 2 行，生成器產生第 0 個整數
- 在第 4 行，生成器產生第 1 個整數
- 在第 6 行，生成器產生第 2 個整數
- 在第 8 行，生成器產生第 3 個整數
- 在第 11 行，因為生成器生成的序列只包含 3 個整數，此時已經生成全部的整數，因此拋出異常 StopIteration
2.2 使用 while 循環訪問生成器
根據生成器的原理，可以循環的調用 next(generator) 輸出全部的序列，示例如下：
generator = (i for i in range(3))
while True:
try:
item = next(generator)
print(item)
except StopIteration:
break
- 在第 1 行，創建一個產生 0 到 3 之間所有整數的生成器
- 在第 3 行，創建一個循環
- 在第 5 行，調用 next(generator) 通知生成器返回一個數據
- 在第 7 行，當生成器輸出結束后，拋出異常 StopIteration
運行程序，輸出結果如下：
0
1
2
2.3 使用 for 循環訪問生成器
通常使用 for 循環訪問生成器，示例如下：
generator = (i for i in range(3))
for item in generator:
print(item)
- 在第 1 行，創建一個產生 0 到 3 之間所有整數的生成器
- 在第 3 行，使用 for 循環訪問生成器
運行程序，輸出結果如下：
0
1
2
3. 創建生成器
3.1 通過推導創建生成器
可以使用類似于列表推導的語法創建一個生成器，語法如下：
(expression for i in iterable)
該生成器遍歷對象 iterable，依次產生數據 expression，它的工作流程如下：
for i in iterable:
generate expression
注意：創建生成器的語法與列表推導的語法相似，不同之處在于，創建生成器的語法采用小括號 ()，創建列表的語法采用方括號 []。
通過推導創建生成器的示例如下：
generator = (i*2 for i in range(5))
for i in generator:
print(i)
- 循環變量 i 從 0 變化到 4
- 生成器每次產生數據 i*2
運行程序，輸出結果如下：
0
2
4
6
8
3.2 通過復雜的推導創建生成器
可以使用類似于列表推導的語法創建一個生成器，語法如下：
(expression for i in iterable if condition)
該生成器遍歷對象 iterable，如果條件 condition 為真，則產生數據 expression，它的工作流程如下：
for i in iterable:
if condition:
generate expression
通過復雜推導創建生成器的示例如下：
generator = (i for i in range(10) if i % 2 == 0)
for i in generator:
print(i)
- 循環變量 i 從 0 變化到 9
- 如果 i % 2 == 0，表示 i 是偶數
- 生成器每次產生從 0 到 9 之間的偶數
運行程序，輸出結果如下：
0
2
4
6
8
3.3 通過 yield 創建生成器
在生成器的生命周期中，生成器根據一定的規則產生一系列的數據，生成器可以使用 yield 關鍵字產生一個數據。例如，一個生成特定范圍內的奇數序列的函數：
def generateOddNumbers(n):
for i in range(n):
if i % 2 == 1:
yield i
generator = generateOddNumbers(10)
for i in generator:
print(i)
- 在第 1 行，定義了函數 generateOddNumbers(n)，它返回一個生成器，該生成器產生從 0 到 n 范圍內的奇數
- 在第 2 行到第 4 行，使用 for 循環生成從 0 到 n 范圍內的奇數
- 在第 3 行，如果 i % 2 == 1 為真，表示 i 是奇數
- 在第 4 行，使用 yield i 生成一個數據 i
- 在第 6 行，generateOddNumbers(10) 返回一個生成器，該生成器產生從 0 到 10 范圍內的奇數
- 在第 7 行，使用 for 循環遍歷該生成器
運行該程序，輸出如下：
1
3
5
7
9
注意：包含 yield 關鍵字的函數被稱為生成器函數，調用生成器函數會返回一個生成器。在上面的例子中，函數 generateOddNumbers(n) 包含 yield 關鍵字，是一個生成器函數，它返回一個生成器，該生成器產生從 0 到 n 范圍內的奇數。
4. 使用 yield 實現遍歷堆棧的生成器
4.1 通過單鏈表實現堆棧
通過單鏈表實現堆棧，圖示如下：
在上圖中，每個節點有兩個字段: item 和 next，item 用于存儲數據，next 指向下一個節點，head 指針指向堆棧的頂部。描述堆棧的 Python 代碼如下：
class Node:
def __init__(self, item):
self.item = item
self.next = None
class Stack:
def __init__(self):
self.head = None
def push(self, item):
node = Node(item)
node.next = self.head
self.head = node
stack = Stack()
stack.push('a')
stack.push('b')
stack.push('c')
- 在第 1 行，定義了類 Node 用于描述鏈表中的節點
- 在第 6 行，定義了類 Stack 描述堆棧
- 在第 8 行，定義了頭指針 head，指向鏈表中的首個節點
- 在第 10 行，定義了成員方法 push，將元素壓如到堆棧中
- 在第 11 行，創建一個新節點 node
- 在第 12 行，新節點 node 的 next 指向頭結點
- 在第 13 行，頭結點指向新節點
- 在第 15 行，創建一個對象 stack
- 在第 16 行到第 18 行，依次壓入 3 個元素 ‘a’、‘b’、‘c’
4.2 使用 yield 關鍵字實現生成器函數
def stackGenerate(stack):
cursor = stack.head
while cursor != None:
yield cursor.item
cursor = cursor.next
- 在第 1 行，定義函數 stackGenerate(stack)
- 該函數包含 yield 關鍵字，是一個生成器函數，它返回一個生成器
- 生成器遍歷堆棧，按出棧的順序輸出數據
- 在第 2 行，變量 cursor 指向了當前正在遍歷的元素，初始化被設置為鏈表的頭結點
- 在第 3 行，使用循環遍歷堆棧
- 如果變量 cursor 等于 None，表示已經到達鏈表的尾部，即遍歷完全部的元素了
- 在第 4 行，使用 yield 輸出當前正在遍歷的元素
- 在第 5 行，將 cursor 指向下一個元素
4.3 通過 while 循環遍歷堆棧
使用 while 循環顯式的使用 next、StopIteration 完成對 stack 的遍歷，代碼如下：
generator = stackGenerate(stack)
while True:
try:
item = next(generator)
print(item)
except StopIteration:
break
- 在第 1 行，stackGenerate(stack) 返回一個遍歷堆棧的生成器
- 在第 4 行，next(generator) 獲取生成器的輸出
- 在第 6 行，當生成器輸出結束后，拋出異常 StopIteration
程序依次壓入 ‘a’、‘b’、‘c’，遍歷時以壓入相反的順序輸出，結果如下：
c
b
a
4.4 通過 for … in 循環遍歷堆棧
通過 for … in 循環對生成器進行遍歷，代碼如下：
generator = stackGenerate(stack)
for item in generator:
print(item)
與上一節的代碼相比，代碼要簡潔很多，程序輸出相同的結果如下：
c
b
a
2025 imooc.com All Rights Reserved |