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