Python中神奇的迭代器和生成器
給定字符串 s 和 t ，判斷 s 是否為 t 的子序列。
字符串的一個子序列是原始字符串刪除一些（也可以不刪除）字符而不改變剩余字符相對位置形成的新字符串。（例如，"ace"是"abcde"的一個子序列，而"aec"不是）。
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/is-subsequence
要解決這個問題，常規(guī)算法是貪心算法。我們維護(hù)兩個指針指向兩個字符串的開頭，然后對第二個字符串一路掃過去，如果某個字符和第一個指針指的一樣，那么就把第一個指針前進(jìn)一步。第一個指針移出第一個序列最后一個元素的時候，返回 True，否則返回 False。
不過，這個算法正常寫的話，寫下來怎么也得八行左右：
def is_subsequence(s: str, t: str) -> bool:
n, m = len(s), len(t)
i = j = 0
while i < n and j < m:
if s[i] == t[j]:
i += 1
j += 1
return i == n
print(is_subsequence("ace", "abcde"))
print(is_subsequence("aec", "abcde"))
但如果我們使用迭代器和生成器，代碼量將大幅度減少：
def is_subsequence(s: str, t: str) -> bool:
t = iter(t)
return all(i in t for i in s)
print(is_subsequence("ace", "abcde"))
print(is_subsequence("aec", "abcde"))
而且運(yùn)行結(jié)果正確與上面一樣，都是：
True
False
但如果你對python的生成器運(yùn)行機(jī)制不太了解，一定會看的一臉懵逼。
不過不用擔(dān)心，我今天分享的主題便是python的迭代器和生成器剖析。
本文目錄
迭代器和可迭代對象
列表生成式與列表生成器
函數(shù)生成器(generator)
迭代器和生成器的關(guān)系
利用生成器判斷子序列詳解
總結(jié)
迭代器和可迭代對象
在 Python 中一切皆對象，對象的抽象就是類，而對象的集合就是容器。
列表（list: [0, 1, 2]），元組（tuple: (0, 1, 2)），字典（dict: {0:0, 1:1, 2:2}），集合（set: set([0, 1, 2])）都是容器。對于容器，可以認(rèn)為是多個元素在一起的單元；而不同容器的區(qū)別，正是在于內(nèi)部數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)方法。
所有的容器都是可迭代對象（iterable）：
from collections.abc import Iterable
params = [
1234,
'1234',
[1, 2, 3, 4],
set([1, 2, 3, 4]),
{1: 1, 2: 2, 3: 3, 4: 4},
(1, 2, 3, 4)
]
for param in params:
print(f'{param}是否為可迭代對象? ', isinstance(param, Iterable))
運(yùn)行結(jié)果：
1234是否為可迭代對象? False
1234是否為可迭代對象? True
[1, 2, 3, 4]是否為可迭代對象? True
{1, 2, 3, 4}是否為可迭代對象? True
{1: 1, 2: 2, 3: 3, 4: 4}是否為可迭代對象? True
(1, 2, 3, 4)是否為可迭代對象? True
可以看到所有的集合容器都是可迭代對象（iterable），字符串也是可迭代對象，唯有單個數(shù)字不是可迭代對象。
而可迭代對象，可以通過 iter() 函數(shù)返回一個迭代器，當(dāng)然迭代器本身也屬于可迭代對象：
from collections.abc import Iterable, Iterator
params = [
'1234',
[1, 2, 3, 4],
set([1, 2, 3, 4]),
{1: 1, 2: 2, 3: 3, 4: 4},
(1, 2, 3, 4)
]
for param in params:
param = iter(param)
print("----------")
print(f'{param}是否為可迭代對象? ', isinstance(param, Iterable))
print(f'{param}是否為迭代器對象? ', isinstance(param, Iterator))
運(yùn)行結(jié)果：
這意味著迭代器本身也可以獲取它自己的迭代器，例如：
for i in iter(l):
print(i, end=",")
print()
for i in iter(iter(l)):
print(i, end=",")
運(yùn)行結(jié)果：
1,2,3,4,
1,2,3,4,
迭代器（iterator）提供了一個 __next__的方法。調(diào)用這個方法后，你要么得到這個容器的下一個對象，要么得到一個 StopIteration 的錯誤：
l = [1, 2, 3, 4]
l = iter(l)
while True:
print(l.__next__())
結(jié)果：
1
2
3
4
---------------------------------------------------------------------------
StopIteration Traceback (most recent call last)
<ipython-input-16-e106f3a7bd73> in <module>()
2 l = iter(l)
3 while True:
----> 4 print(l.__next__())
StopIteration:
當(dāng)然上面的l.__next__()應(yīng)該改寫成next(l)，next()方法的本質(zhì)就是調(diào)用目標(biāo)對象的__next__()方法。
實際上for循環(huán)：
l = [1, 2, 3, 4]
for i in l:
print(i)
的本質(zhì)等價于：
l = [1, 2, 3, 4]
l_iter = iter(l)
while True:
try:
i = next(l_iter)
except StopIteration:
break
print(i)
for in 語句將這個過程隱式化了。
列表生成式與列表生成器
列表生成式即List Comprehensions，是Python內(nèi)置的非常簡單卻強(qiáng)大的可以用來創(chuàng)建list的生成式。
print([x * x for x in range(1, 11)])
print([x * x for x in range(1, 11) if x % 2 == 0])
##還可以使用兩層循環(huán)，可以生成全排列：
print([m + n for m in 'ABC' for n in 'XYZ'])
print([str(x)+str(y) for x in range(1,6) for y in range(11,16)])
##for循環(huán)其實可以同時使用兩個甚至多個變量，比如dict的items()可以同時迭代key和value：
d = {'x': 'A', 'y': 'B', 'z': 'C' }
print([k + '=' + v for k, v in d.items()])
結(jié)果：
[1, 4, 9, 16, 25, 36, 49, 64, 81, 100]
[4, 16, 36, 64, 100]
['AX', 'AY', 'AZ', 'BX', 'BY', 'BZ', 'CX', 'CY', 'CZ']
['111', '112', '113', '114', '115', '211', '212', '213', '214', '215', '311', '312', '313', '314', '315', '411', '412', '413', '414', '415', '511', '512', '513', '514', '515']
['x=A', 'y=B', 'z=C']
通過列表生成式，我們可以直接創(chuàng)建一個列表。但是，受到內(nèi)存限制，列表容量肯定是有限的。而且，創(chuàng)建一個包含100萬個元素的列表，不僅占用很大的存儲空間，如果我們僅僅需要訪問前面幾個元素，那后面絕大多數(shù)元素占用的空間都白白浪費(fèi)了。
所以，如果列表元素可以按照某種算法推算出來，那我們是否可以在循環(huán)的過程中不斷推算出后續(xù)的元素呢？這樣就不必創(chuàng)建完整的list，從而節(jié)省大量的空間。在Python中，這種一邊循環(huán)一邊計算的機(jī)制，稱為生成器：generator。
只要把一個列表生成式的[]改成()，就創(chuàng)建了一個generator：
g = (x * x for x in range(10))
generator保存的是算法，每次調(diào)用next(g)，就計算出g的下一個元素的值，直到計算到最后一個元素，沒有更多的元素時，拋出StopIteration的錯誤。
用一個示例，感受一下生成器相對生成式的優(yōu)勢，首先創(chuàng)建一個查看當(dāng)前內(nèi)存情況的方法：
import os
import psutil
## 顯示當(dāng)前 python 程序占用的內(nèi)存大小
def show_memory_info(hint):
pid = os.getpid()
p = psutil.Process(pid)
info = p.memory_full_info()
memory = info.uss / 1024. / 1024
print(f'{hint}內(nèi)存使用: {memory} MB')
測試一下列表生成式：
def test_iterator():
show_memory_info('initing iterator')
list_1 = [i for i in range(100000000)]
show_memory_info('after iterator initiated')
print(sum(list_1))
show_memory_info('after sum called')
%time test_iterator()
結(jié)果：
initing iterator內(nèi)存使用: 48.69140625 MB
after iterator initiated內(nèi)存使用: 3936.2890625 MB
4999999950000000
after sum called內(nèi)存使用: 3936.29296875 MB
Wall time: 9.39 s
測試一下列表生成器：
def test_generator():
show_memory_info('initing generator')
list_2 = (i for i in range(100000000))
show_memory_info('after generator initiated')
print(sum(list_2))
show_memory_info('after sum called')
%time test_generator()
結(jié)果：
initing generator內(nèi)存使用: 48.8515625 MB
after generator initiated內(nèi)存使用: 48.85546875 MB
4999999950000000
after sum called內(nèi)存使用: 49.11328125 MB
Wall time: 7.95 s
聲明一個迭代器很簡單，[i for i in range(100000000)]就可以生成一個包含一億元素的列表。每個元素在生成后都會保存到內(nèi)存中，你通過上面的代碼可以看到，它們占用了巨量的內(nèi)存，內(nèi)存不夠的話就會出現(xiàn) OOM 錯誤。
不過，我們并不需要在內(nèi)存中同時保存這么多東西，比如對元素求和，我們只需要知道每個元素在相加的那一刻是多少就行了，用完就可以扔掉了。
函數(shù)生成器(generator)
如果推算的算法比較復(fù)雜，用類似列表生成式的for循環(huán)無法實現(xiàn)的時候，還可以用函數(shù)來實現(xiàn)。
比如，著名的斐波拉契數(shù)列（Fibonacci），除第一個和第二個數(shù)外，任意一個數(shù)都可由前兩個數(shù)相加得到：
1, 1, 2, 3, 5, 8, 13, 21, 34, ...
斐波拉契數(shù)列用列表生成式寫不出來，但是用函數(shù)把它打印出來卻很容易：
def fib(max):
n, a, b = 0, 0, 1
while n < max:
print(b)
a, b = b, a + b
n = n + 1
fib(6)
打印結(jié)果：
1
1
2
3
5
8
上面的函數(shù)和生成器(generator)僅一步之遙，只要把print(b)改為yield b，fib函數(shù)就會變成生成器(generator)：
def fib(max):
n, a, b = 0, 0, 1
while n < max:
yield b
a, b = b, a + b
n = n + 1
這就是除了列表生成器以外定義generator的另一種方法。
如果一個函數(shù)定義中包含yield關(guān)鍵字，那么這個函數(shù)就不再是一個普通函數(shù)，而是一個generator：
fib(6)
結(jié)果：
<generator object fib at 0x0000000005F04A98>
在前面的列表生成器中我已經(jīng)講過，對于生成器可以使用for循環(huán)進(jìn)行遍歷：
for i in fib(6):
print(i)
打印結(jié)果：
1
1
2
3
5
8
這里，最難理解的就是generator和函數(shù)的執(zhí)行流程不一樣。函數(shù)是順序執(zhí)行，遇到return語句或者最后一行函數(shù)語句就返回。而變成generator的函數(shù)，在每次調(diào)用next()的時候執(zhí)行，遇到y(tǒng)ield語句返回，再次執(zhí)行時從上次返回的yield語句處繼續(xù)執(zhí)行。
舉個簡單的例子，定義一個generator，依次返回數(shù)字1，3，5：
def odd():
print('step 1')
yield 1
print('step 2')
yield(3)
print('step 3')
yield(5)
調(diào)用該generator時，首先要生成一個generator對象，然后用next()函數(shù)不斷獲得下一個返回值：
o = odd()
while True:
print(next(o))
結(jié)果：
step 1
1
step 2
3
step 3
5
---------------------------------------------------------------------------
StopIteration Traceback (most recent call last)
<ipython-input-7-554c5fb505f8> in <module>()
1 o = odd()
2 while True:
----> 3 print(next(o))
StopIteration:
可以看到，odd不是普通函數(shù)，而是generator，在執(zhí)行過程中，遇到y(tǒng)ield就中斷，下次又繼續(xù)執(zhí)行。執(zhí)行3次yield后，已經(jīng)沒有yield可以執(zhí)行了，所以，第4次調(diào)用next()就拋出StopIteration異常。
對于函數(shù)生成器(generator)來說，遇到return語句就是結(jié)束generator的指令（函數(shù)體最后一行語句其實隱式執(zhí)行了return None），for循環(huán)隨之結(jié)束。
迭代器和生成器的關(guān)系
其實生成器就是一種特殊的迭代器，而迭代器包括了生成器并不等價于生成器，它們都可以通過next()方法不斷的獲取下一個對象，都具備記憶已經(jīng)讀取的位置的特點。
例如：
l = [1, 2, 3, 4]
l_iter = iter(l)
完成可以理解為產(chǎn)生了一個列表生成器：
l = [1, 2, 3, 4]
l_iter = (i for i in l)
也可以理解成產(chǎn)生了一個函數(shù)生成器：
l = [1, 2, 3, 4]
def func_generator(l):
for i in l:
yield i
l_iter = func_generator(l)
利用生成器判斷子序列詳解
有了前面的基礎(chǔ)知識，相信文章開頭的代碼還稍微有點眉目了。現(xiàn)在我們再回到文章開頭的代碼，詳細(xì)分析一下：
def is_subsequence(s: str, t: str) -> bool:
t = iter(t)
return all(i in t for i in s)
print(is_subsequence("ace", "abcde"))
print(is_subsequence("aec", "abcde"))
首先t = iter(t)我們可以理解為產(chǎn)生了一個生成器：
t = (i for i in t)
而i in t基本上等價于：
while True:
val = next(t)
if val == i:
yield True
測試一下：
t = "abcde"
t = (i for i in t)
print('a' in t)
print('c' in t)
print(next(t))
結(jié)果：
True
True
d
可以看到最后一行直接返回了匹配到c的下一個值'd'。
這樣我們再測試：
t = "abcde"
t = (i for i in t)
print('a' in t)
print('c' in t)
print('b' in t)
結(jié)果：
True
True
False
于是就可以順利的使用生成器計算子序列的每個元素是否滿足條件：
t = iter("abcde")
[i in t for i in "aec"]
結(jié)果：
[True, True, False]
而all()函數(shù)即可判斷是否全部都滿足條件：
print(all([True, True, False]), all([True, True, True]))
結(jié)果：
False True
而上述代碼all(i in t for i in s)沒有申明all([i in t for i in s])列表生成式形式則代表是對一個列表生成器進(jìn)行all運(yùn)算。
總結(jié)
于是到此，我們就很優(yōu)雅地解決了這道題。不過一定要注意，實際工作中盡量不要用這種技巧，因為你的領(lǐng)導(dǎo)和同事有可能并不知道生成器的用法，你即使寫了詳細(xì)的注釋他們也難以理解，不如用常規(guī)方法解決比較好！經(jīng)過今天的學(xué)習(xí)，希望你已經(jīng)在生成器這個技術(shù)知識點上比其他人更加熟練了。
今天本文分享了容器、可迭代對象、迭代器和生成器四種不同的對象：
容器是可迭代對象，可迭代對象調(diào)用 iter() 函數(shù)可以得到一個迭代器。 迭代器可以通過 next() 函數(shù)來得到下一個元素，從而支持遍歷。 生成器是一種特殊的迭代器（迭代器卻不見得是生成器）。
推薦閱讀:
入門: 最全的零基礎(chǔ)學(xué)Python的問題 | 零基礎(chǔ)學(xué)了8個月的Python | 實戰(zhàn)項目 |學(xué)Python就是這條捷徑
干貨:爬取豆瓣短評，電影《后來的我們》 | 38年NBA最佳球員分析 | 從萬眾期待到口碑撲街！唐探3令人失望 | 笑看新倚天屠龍記 | 燈謎答題王 ｜用Python做個海量小姐姐素描圖 ｜
趣味:彈球游戲 | 九宮格 | 漂亮的花 | 兩百行Python《天天酷跑》游戲!
AI: 會做詩的機(jī)器人 | 給圖片上色 | 預(yù)測收入 | 碟中諜這么火，我用機(jī)器學(xué)習(xí)做個迷你推薦系統(tǒng)電影
年度爆款文案
點閱讀原文,領(lǐng)全套AI資料！
