文章目錄
- 1. 函數的執行流程
- 1.1. 字節碼了解壓棧過程
- 1.2. 嵌套函數的壓棧
- 2. 遞歸
- 2.1. 遞歸函數
- 2.2. 遞歸的性能
- 2.3. 遞歸的優化
- 2.4. 間接遞歸
- 2.5. 遞歸總結
- 3. 匿名函數
- 4. Python 生成器
- 4.1. 基本結構
- 4.2. 使用場景
- 4.3. 協程 coroutine
- 4.4. yield from
1. 函數的執行流程
??函數的執行需要對函數進行 壓棧 ，什么是壓棧呢，簡而言之就是在函數執行時在棧中創建 棧幀 存放需要的 變量 以及 指針 的意思。具體涉及的知識非常多，這里就以一個 Python 腳本簡單進行分析。
def
foo1
(
b
,
b1
=
3
)
:
print
(
'call foo1'
,
b
,
b1
)
def
foo2
(
c
)
:
foo3
(
c
)
print
(
'call foo2'
,
c
)
def
foo3
(
d
)
:
print
(
'call foo3'
,
d
)
def
main
(
)
:
print
(
'call main'
)
foo1
(
100
,
101
)
foo2
(
20
)
print
(
'main ending'
)
main
(
)
??當我們運行上面代碼時，它的執行流程如下：
- 全局棧幀中生成 foo1、foo2、foo3、main 函數對象
- main 函數調用
- main 中查找內建函數 print 壓棧，將常量字符串壓棧，調用函數，彈出棧頂
- main 中全局查找函數 foo1 壓棧，將常量 100、101 壓棧，調用函數 foo1，創建棧幀。print 函數壓棧，字符串和變量 b、b1 壓棧，調用函數，彈出棧頂，返回值。
- main 中全局查找 foo2 函數壓棧，將常量 20 壓棧，調用 foo2，創建棧幀。foo3 函數壓棧，變量 c 引用壓棧，調用 foo3，創建棧幀。foo3 完成 print 函數調用返回。foo2 恢復調用，執行 print 語句后，返回值。main 中 foo2 調用結束后彈出棧頂，main 繼續執行 print 函數調用，彈出棧頂，main 函數返回。
1.1. 字節碼了解壓棧過程
??Python 代碼先被編譯為字節碼后，再由 Python 虛擬機來執行字節碼， Python 的字節碼是一種類似匯編指令的中間語言， 一個 Python 語句會對應若干字節碼指令，虛擬機一條一條執行字節碼指令， 從而完成程序執行。Python
dis 模塊
支持對 Python 代碼進行反匯編， 生成字節碼指令。下面針對上面的例子通過字節碼理解函數調用時的過程。
import
dis
print
(
dis
.
dis
(
main
)
)
# ======> result
53
0
LOAD_GLOBAL
0
(
print
)
2
LOAD_CONST
1
(
'call main'
)
4
CALL_FUNCTION
1
6
POP_TOP
54
8
LOAD_GLOBAL
1
(
foo1
)
10
LOAD_CONST
2
(
100
)
12
LOAD_CONST
3
(
101
)
14
CALL_FUNCTION
2
16
POP_TOP
55
18
LOAD_GLOBAL
2
(
foo2
)
20
LOAD_CONST
4
(
20
)
22
CALL_FUNCTION
1
24
POP_TOP
56
26
LOAD_GLOBAL
0
(
print
)
28
LOAD_CONST
5
(
'main ending'
)
30
CALL_FUNCTION
1
32
POP_TOP
34
LOAD_CONST
0
(
None
)
36
RETURN_VALUE
字節碼含義 ：
-
LOAD_GLOBAL：加載全局函數 (print) -
LOAD_CONST: 加載常量 -
CALL_FUNCTION: 函數調用 -
POP_TOP：彈出棧頂 -
RETURN_VALUE： 返回值
1.2. 嵌套函數的壓棧
def
outer
(
)
:
c
=
100
def
inner
(
)
:
nonlocal
c
c
+=
200
return
c
return
inner
a
=
outer
(
)
a
(
)
- 函數只有在執行的時候才會壓棧，所以在 outer 執行時，會開辟?？臻g壓棧 (c,inner)
-
執行完后，刪除?？臻g，但是由于 outer 返回了內部函數 inner，但并沒有執行，所以不會繼續壓棧，當執行 a 的時候，會重新壓棧，而此時內部函數已經記住了外部自由變量
c，并且每次調用 outer 都會重新生成一個 inner。
注意：這種情況叫做閉包，自由變量 c 會被當成內部函數 inner 的一個屬性，被調用。
PS ：內存兩大區域 (棧，堆)。垃圾回收，清理的是堆中的空間。函數的調用就是壓棧的過程，而變量的創建都是在堆中完成的。 棧中存儲的都是堆中的內存地址的指向，棧清空，并不會使堆中的對象被清除，只是指向已經被刪除。 函數，變量都是在堆內創建的，函數調用需要壓棧 。
2. 遞歸
??函數直接或者間接的調用自身就叫 遞歸 ，遞歸需要有邊界條件、遞歸前進段、遞歸返回段，當邊界條件不滿足的時候，遞歸前進，當邊界條件滿足時，遞歸返回。 注意：遞歸一定要有邊界條件，否則可能會造成內存溢出。
2.1. 遞歸函數
??前面我們學過斐波那契序列，利用遞歸函數，我們可以更簡潔的編寫一個計算斐波那契序列第 N 項，或者前 N 項的代碼：
在數學上，斐波納契數列以如下被以遞推的方法定義：
F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n >= 3，n ∈ N*）
# 公式版本
def
fib
(
n
)
:
if
n
<
3
:
return
1
return
fib
(
n
-
1
)
+
fib
(
n
-
2
)
# 公式版本之簡潔版
def
fib
(
n
)
:
return
1
if
n
<
3
else
fib
(
n
-
1
)
+
fib
(
n
-
2
)
很多人可能不明白其中原理，這里簡要說明一下，以 fib(6) 為例子:
- fib(6) 返回 fib(5) + fib(4)
- fib(5) 返回 fib(4) + fib(3)
- fib(4) 返回 fib(3) + fib(2)
- fib(3) 返回 fib(2) + fib(1)
- fib(2),fib(1) 是邊界，return 1，然后逐級調用返回
[外鏈圖片轉存失敗(img-AbD3k3t3-1562240946327)(https://github.com/colinlee19860724/Study_Notebook/raw/master/Photo/re_fib.png)]
遞歸的要求：
- 遞歸一定要有退出條件，遞歸調用一定要執行到這個退出條件。沒有退出條件的遞歸調用，就是無限調用
-
遞歸調用的深度不宜過深，Python 對遞歸的深度做了限制，以保護解釋器，超過遞歸深度限制，則拋出
RecursionError異常。
使用
import sys; sys.getrecursionlimit()獲取當前解釋器限制的最大遞歸深度
2.2. 遞歸的性能
??由于 Python 是預先計算等式右邊的，所以我們發現，上圖中，重復計算了
fib(4)
和
fib(3)
那么效率呢？由于只是計算了 fib(6)，如果
fib(35)
呢？可以預想，它要重復計算多少次啊。這里我們來測試一下它執行的時間。
# 遞歸版本
import
timeit
def
fib
(
n
)
:
return
1
if
n
<
3
else
fib
(
n
-
2
)
+
fib
(
n
-
1
)
start
=
timeit
.
default_timer
(
)
fib
(
35
)
duration
=
timeit
.
default_timer
(
)
-
start
print
(
'{:.6f}'
.
format
(
duration
)
)
# 1.783832
# 循環版本
def
fib
(
n
)
:
a
=
1
b
=
1
count
=
2
while
count
<
n
:
a
,
b
=
b
,
a
+
b
count
+=
1
return
b
start
=
timeit
.
default_timer
(
)
fib
(
35
)
duration
=
timeit
.
default_timer
(
)
-
start
print
(
'{:.6f}'
.
format
(
duration
)
)
# 0.000037
??經過對比，我們發現使用遞歸雖然代碼更優美了，但是運行時間還不如我們的普通循環的版本，這是因為遞歸重復計算了很多次，當規模到達一定程度時，那么這個時間是成指數遞增的。
總結一下現在的問題：
- 循環稍微復雜一點，但是只要不是死循環，可以多次迭代直至算出結果
- fib 函數代碼極簡易懂，但是只要獲取到最外層的函數調用，內部跌代結果都是中間結果。而且給定一個 n 都要進行近 2n 次遞歸，深度越深，效率越低。為了獲取斐波那契數列需要在外面套一個 n 次的循環，效率就更低了。
- 遞歸還有深度限制，如果 遞歸復雜 ， 函數反復壓棧 ，棧內存就很快溢出了。
2.3. 遞歸的優化
??如何優化呢？前面的版本使用遞歸函數時會重復計算一些相同的數據，那么我們來改進一下，在代碼層面對遞歸的特性進行優化。
import
timeit
def
fib
(
n
,
a
=
1
,
b
=
1
)
:
a
,
b
=
b
,
a
+
b
if
n
<
3
:
return
b
return
fib
(
n
-
1
,
a
,
b
)
start
=
timeit
.
default_timer
(
)
fib
(
35
)
duration
=
timeit
.
default_timer
(
)
-
start
print
(
'{:.6f}'
.
format
(
duration
)
)
# 0.000038
??代碼優化后，發現運行時間很快，因為計算的是
fib(n),fib(n-1)..fib(1)
并沒有進行重復計算，所以要使用遞歸，必須要考慮重復計算以及函數遞歸調用時產生的內存浪費等。
2.4. 間接遞歸
間接遞歸，就是通過別的函數，來調用函數本身，下面來看一個例子，來理解間接遞歸的概念：
def
foo1
(
)
:
foo2
(
)
def
foo2
(
)
:
foo1
(
)
foo1
(
)
# RecursionError: maximum recursion depth exceeded
??我們可以看到，這種遞歸調用是非常危險的，但是往往在代碼復雜的情況下，還是可能發生這種調用。要用代碼規范來避免這種遞歸調用的發生。
2.5. 遞歸總結
遞歸是一種很自然的表達，符合邏輯思維：
- 運行效率低，每一次調用函數都要開辟棧幀。
- 有深度限制，如果遞歸層次太深，函數反復壓棧，棧內存很快就溢出了。
- 如果是有限次數的遞歸，可以使用遞歸調用，或者使用循環代替，雖然代碼稍微復雜一點，但是只要不是死循環，可以多次疊代直至算出結果。
- 絕大多數遞歸，都可以使用循環實現， 能不用遞歸則不用遞歸 。
3. 匿名函數
??沒有名字的函數，在 Python 中被稱為匿名函數，考慮一下，我們之前都是通過 def 語句定義函數的名字，而開始定義一個函數的，那么不用名字該如何定義函數？函數沒有名字又該如何調用呢？
??Python 中借助 lambda 表達式構建匿名函數。它的格式為：
lambda
' 參數列表 '
：
' 返回值 '
# 等于:
def
xxx
(
參數列表
)
:
return
返回值
需要注意的是：
- 冒號左邊是參數列表，但不要括號。
- 冒號右邊是函數體，但不能出現等號。
- 函數體只能寫一行，不能使用分號分隔多個語句。(也被稱為單行函數)
- return 語句，可以不寫 return 關鍵字
下面來看一下各種匿名函數的寫法
(
lambda
x
,
y
:
x
+
y
)
(
4
,
5
)
# 9
(
lambda
x
,
y
=
10
:
x
+
y
)
(
10
)
# 20
(
lambda
x
,
y
=
10
:
x
+
y
)
(
x
=
10
)
# 20
(
lambda
x
,
y
=
10
:
x
+
y
)
(
10
,
y
=
10
)
# 20
(
lambda
x
,
y
=
10
,
*
args
:
x
+
y
)
(
10
,
y
=
10
)
# 20
(
lambda
x
,
y
=
10
,
*
args
,
**
kwargs
:
x
+
y
)
(
10
,
y
=
10
)
# 20
(
lambda
*
args
:
(
i
for
i
in
args
)
)
(
1
,
2
,
3
,
4
,
5
)
# generate<1,2,3,4,5>
(
lambda
*
args
:
(
i
for
i
in
args
)
)
(
*
range
(
5
)
)
# generate<0,1,2,3,4>
[
x
for
x
in
(
lambda
*
args
:
(
i
for
i
in
args
)
)
(
*
range
(
5
)
)
]
# [0, 1, 2, 3, 4]
[
x
for
x
in
(
lambda
*
args
:
map
(
lambda
x
:
x
+
1
,
(
i
for
i
in
args
)
)
)
(
*
range
(
5
)
)
]
# [1, 2, 3, 4, 5]
- lambda 是一個匿名函數，我們在它后面加括號就表示函數調用
- 在高階函數傳參時，使用 lambda 表達式，往往能簡化代碼
還記得，我們之前的默認值字典嗎，這里的：
d = collections.defaultdict(lambda :0)，其實就等于(lambda :0)()，即當我們傳入任意值時都返回 0
4. Python 生成器
??生成器指生成器對象，可以由生成器表達式得到，也可以使用 yield 關鍵字得到一個生成器函數，調用這個函數返回一個生成器對象。
??生成器函數，函數體中包含 yield 關鍵字的函數，就是生成器函數，調用后返回生成器對象。關于生成器對象，我們可以理解它就是一個
可迭代對象
，是一個
迭代器
，只不過它是
延遲計算
的，
惰性求值
的。
4.1. 基本結構
??我們說在函數中使用 yield 關鍵字來返回數據的函數，叫做 生成器函數 ，那么我們來寫一個生成器函數，看看和 return 函數有什么區別
def
func
(
)
:
for
i
in
range
(
2
)
:
yield
i
g
=
func
(
)
In
:
next
(
g
)
Out
:
0
In
:
next
(
g
)
Out
:
1
In
:
next
(
g
)
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
StopIteration Traceback
(
most recent call last
)
<
ipython
-
input
-
93
-
e734f8aca5ac
>
in
<
module
>
-
-
-
-
>
1
next
(
g
)
StopIteration
:
??這個報錯看起來是不是很熟悉？沒錯，和生成器表達式的結果是相同的，只不過生成器函數可以寫的更加的復雜，現在我們來看下生成器函數的執行過程。
- 當函數執行過程中遇到 yield 函數時，會暫停，并把 yield 表達式的值返回。
- 再次執行時會執行到下一個 yield 語句
yield 關鍵字，和return 關鍵字在生成器場景下， 不能一起使用 。因為 return 語句會導致當前函數立即返回，無法繼續執行，也無法繼續獲取下一個值，并且 return 語句的返回值也不能被next()獲取到，還會產生 StopIteration 的異常.
??再來總結一下生成器的特點：
-
包含
yield語句的生成器函數調用生成生成器對象的時候，生成器函數的函數體不會立即執行。 -
next(genreator)會從函數的當前位置向后執行到之后碰到的一個yield語句，會彈出值，并暫停函數執行。 -
再次調用
next函數，和上一條一樣的處理結果 -
繼續調用
next函數，生成器函數如果結束執行了（顯示或隱式調用了return語句），會拋出 StopIteration 異常
4.2. 使用場景
??我們想要生成一個無限自然數的序列時，生成器就是一個很好的方式
def
counter
(
)
:
c
=
0
while
True
:
c
+=
1
yield
c
c
=
counter
(
)
In
:
next
(
c
)
Out
:
1
In
:
next
(
c
)
Out
:
2
In
:
next
(
c
)
Out
:
3
又或者前面的斐波那契序列，我們也可以利用生成器的特點，惰性計算。
def
fib
(
n
,
a
=
0
,
b
=
1
)
:
for
i
in
range
(
n
)
:
yield
b
a
,
b
=
b
,
a
+
b
print
(
list
(
fib
(
5
)
)
)
# [1, 1, 2, 3, 5]
或者包含所有斐波那契序列的生成器
def
fib
(
)
:
a
=
0
b
=
1
while
True
:
yield
b
a
,
b
=
b
,
a
+
b
g
=
fib
(
)
for
i
in
range
(
101
)
:
print
(
next
(
g
)
)
4.3. 協程 coroutine
??協程是生成器的一種高級方法，比進程、線程更輕量級，是在用戶空間調度函數的一種實現，Python 3 的 asyncio 就是協程實現，已經加入到了標準庫中，Python 3.5 使用 async、await 關鍵字直接原生支持協程。協程在現階段來說比較復雜，后面會詳細進行說明，這里提一下實現思路：
- 有兩個生成器 A、B
- next(A) 后，A 執行到了 yield 語句后暫停，然后去執行 next(B),B 執行到 yield 語句也暫停，然后再次調用 next(A)，再次調用 next(B)
- 周而復始，就實現了調度的效果
- 還可以引入調度的策略來實現切換的方式
協程是一種非搶占式調度
4.4. yield from
??在 Python 3.3 以后，出現了
yield from
語法糖。它的用法是
def
counter
(
)
:
yield
from
range
(
10
)
- yield from 后面需要一個可迭代對象
-
yield from iterable實際上等同于for item in iterable: yield item
??當然
yield from
也可以結合生成器來使用，因為生成器也是一個可迭代對象啊。
def
fib
(
n
)
:
a
=
0
b
=
1
for
i
in
range
(
n
)
:
yield
b
a
,
b
=
b
,
a
+
b
def
counter
(
)
:
yield
from
fib
(
10
)
g
=
counter
(
)
print
(
list
(
g
)
)
# [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
??生成器包生成器，真是妙極了！
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
