文章目錄
- 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元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
