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