[[385610]]

遞歸函數(shù)使用起來非?？?，簡潔優(yōu)雅，可以用來炫耀編程技巧。但是，在大多數(shù)情況下，遞歸函數(shù)具有非常高的時(shí)間和空間復(fù)雜性，我們應(yīng)該避免使用它。更好的解決方案之一是在可能的情況下使用動(dòng)態(tài)規(guī)劃，對(duì)于能夠分解為子問題的問題，動(dòng)態(tài)規(guī)劃可能是最佳方法。然而某些動(dòng)態(tài)規(guī)劃的狀態(tài)轉(zhuǎn)移方程不太容易定義。

今天分享 Python 的另一種牛的技術(shù)--閉包，可以用來作為替代遞歸函數(shù)。它可能不會(huì)勝過動(dòng)態(tài)規(guī)劃，但在思考方面要容易得多。換句話說，由于思想的抽象，我們有時(shí)可能難以使用動(dòng)態(tài)規(guī)劃，但是使用閉包會(huì)容易一些。

什么是 Python 閉包?

首先，讓我使用一個(gè)簡單的示例來說明什么是 Python 中的閉包?？聪旅娴暮瘮?shù)：

def outer(): 
    x = 1 
    def inner(): 
        print(f'x in outer function: {x}') 
    return inner 

在一個(gè)函數(shù)內(nèi)部定義另外一個(gè)函數(shù)，并返回這個(gè)函數(shù)，這種特性就是閉包。檢查 outer 函數(shù)的返回值，可以確認(rèn)這是一個(gè)函數(shù)。

>>> def outer(): 
...     x = 1 
...     def inner(): 
...         print(f'x in outer function: {x}') 
...     return inner 
... 
>>> outer 
<function outer at 0x7fb2ecdac9d0> 
>>> outer() 
<function outer.<locals>.inner at 0x7fb2ecdaca60> 
>>> 

閉包這種特性能做什么呢?因?yàn)楹瘮?shù)返回的是一個(gè)函數(shù)，我們就可以調(diào)用這個(gè)函數(shù)，比如：

>>> outer()() 
x in outer function: 1 
>>> 

不過我們一般會(huì)這么使用閉包，這樣太丑陋了。你可能會(huì)好奇這個(gè)跟遞歸有什么關(guān)系?別著急，讓我們慢慢體會(huì)閉包的牛逼之處。

閉包內(nèi)的變量訪問

從前述的運(yùn)行結(jié)果來看，inner 函數(shù)可以訪問 outer 函數(shù)內(nèi)部定義的變量 x，但是卻無法修改它，下面的代碼運(yùn)行時(shí)會(huì)報(bào)錯(cuò)：

>>> def outer(): 
...     x = 1 
...     def inner(): 
...         print(f'x in outer function (before modifying): {x}') 
...         x += 1 
...         print(f'x in outer function (after modifying): {x}') 
...     return inner 
... 
>>> f = outer() 
>>> f() 
Traceback (most recent call last): 
  File "<stdin>", line 1, in <module> 
  File "<stdin>", line 4, in inner 
UnboundLocalError: local variable 'x' referenced before assignment 
>>> 

為了解決這個(gè)問題，我們可以加上 nonlocal 關(guān)鍵字，告訴 inner 函數(shù)，這不是一個(gè)本地變量：

>>> def outer(): 
...     x = 1 
...     def inner(): 
...         nonlocal x 
...         print(f'x in outer function (before modifying): {x}') 
...         x += 1 
...         print(f'x in outer function (after modifying): {x}') 
...     return inner 
... 
>>> 
>>> f = outer() 
>>> f() 
x in outer function (before modifying): 1 
x in outer function (after modifying): 2 
>>> f() 
x in outer function (before modifying): 2 
x in outer function (after modifying): 3 
>>> f() 
x in outer function (before modifying): 3 
x in outer function (after modifying): 4 
>>> 

有沒有發(fā)現(xiàn)，x 的值竟然被保存了下來，每次調(diào)用一下，就增加了 1，這就是閉包的妙處。

用閉包來替換遞歸

利用上述閉包會(huì)保留調(diào)用結(jié)果的特性，我們可以用這個(gè)來替換遞歸，比如利用閉包計(jì)算斐波那契數(shù)列：

def fib(): 
    x1 = 0 
    x2 = 1 
    def get_next_number(): 
        nonlocal x1, x2 
        x3 = x1 + x2 
        x1, x2 = x2, x3 
        return x3 
    return get_next_number 

可以這樣調(diào)用來生產(chǎn)斐波那契數(shù)列：

>>> def fib(): 
...     x1 = 0 
...     x2 = 1 
...     def get_next_number(): 
...         nonlocal x1, x2 
...         x3 = x1 + x2 
...         x1, x2 = x2, x3 
...         return x3 
...     return get_next_number 
... 
>>> fibonacci = fib() 
>>> for i in range(2, 21): 
...     num = fibonacci() 
...     print(f'The {i}th Fibonacci number is {num}') 
... 
The 2th Fibonacci number is 1 
The 3th Fibonacci number is 2 
The 4th Fibonacci number is 3 
The 5th Fibonacci number is 5 
The 6th Fibonacci number is 8 
The 7th Fibonacci number is 13 
The 8th Fibonacci number is 21 
The 9th Fibonacci number is 34 
The 10th Fibonacci number is 55 
The 11th Fibonacci number is 89 
The 12th Fibonacci number is 144 
The 13th Fibonacci number is 233 
The 14th Fibonacci number is 377 
The 15th Fibonacci number is 610 
The 16th Fibonacci number is 987 
The 17th Fibonacci number is 1597 
The 18th Fibonacci number is 2584 
The 19th Fibonacci number is 4181 
The 20th Fibonacci number is 6765 
>>> 

而使用遞歸方法計(jì)算斐波那契數(shù)列的方法如下所示：

def fib_recursion(n:int) -> int: 
    if n <= 1: 
        return n 
    return fib_recursion(n-1) + fib_recursion(n-2) 

把之前的閉包版本封裝一下：

def fib(): 
    x1 = 0 
    x2 = 1 
    def get_next_number(): 
        nonlocal x1, x2 
        x3 = x1 + x2 
        x1, x2 = x2, x3 
        return x3 
    return get_next_number 
 
def fib_closure(n): 
    f = fib() 
    for i in range(2, n+1): 
        num = f() 
    return num 

這樣使用 fib_closure(20) 就可以計(jì)算出結(jié)果：

In [4]: fib_closure(20) 
Out[4]: 6765 
 
In [5]: fib_recursion(20) 
Out[5]: 6765 
 
In [6]: 

現(xiàn)在使用 IPython 來測試下這兩者的性能：

In [6]: %time fib_closure(20) 
CPU times: user 10 µs, sys: 1e+03 ns, total: 11 µs 
Wall time: 14.1 µs 
Out[6]: 6765 
 
In [7]: %time fib_recursion(20) 
CPU times: user 2.76 ms, sys: 15 µs, total: 2.78 ms 
Wall time: 2.8 ms 
Out[7]: 6765 

可以看出兩差相差近 1000 倍，這還只是計(jì)算到第 20 個(gè)數(shù)的情況下，如果計(jì)算到 100，那使用遞歸會(huì)計(jì)算很久甚至無法計(jì)算出來。

閉包的其他用處

Python 的閉包不僅僅用于替換遞歸，還有很多場景可以使用閉包。比如學(xué)生成績的分類函數(shù)：

學(xué)生成績數(shù)據(jù)：

students = { 
    'Alice': 98, 
    'Bob': 67, 
    'Chris': 85, 
    'David': 75, 
    'Ella': 54, 
    'Fiona': 35, 
    'Grace': 69 
} 

現(xiàn)在需要根據(jù)學(xué)生成績進(jìn)行分類，通常情況下我們會(huì)寫多個(gè)函數(shù)來進(jìn)行分類，而分類的標(biāo)準(zhǔn)又會(huì)經(jīng)常變化，這時(shí)候閉包就很方便了：

def make_student_classifier(lower_bound, upper_bound): 
    def classify_student(exam_dict): 
        return {k:v for (k,v) in exam_dict.items() if lower_bound <= v < upper_bound} 
    return classify_student 
 
grade_A = make_student_classifier(80, 100) 
grade_B = make_student_classifier(70, 80) 
grade_C = make_student_classifier(50, 70) 
grade_D = make_student_classifier(0, 50) 

如果分類標(biāo)準(zhǔn)變化，直接個(gè)性函數(shù)的參數(shù)即可，主要代碼邏輯不變，如果想查找成績分類為 A 的學(xué)生，只需要調(diào)用 grade_A(students) 即可：

In [13]: grade_A(students) 
Out[13]: {'Alice': 98, 'Chris': 85} 

閉包使用上述分類函數(shù)很容易修改且更加易讀。

最后的話

本文介紹了一種稱為 Python 閉包的技術(shù)。在大多數(shù)情況下，可以使用它來重寫遞歸函數(shù)，并且在很大程度上優(yōu)于后者。

實(shí)際上，從性能的角度來看，閉包可能不是某些問題的最佳解決方案，尤其是在使用動(dòng)態(tài)規(guī)劃的情況下。但是，閉包寫起來要容易一些，比遞歸性能高。當(dāng)我們對(duì)性能不是很敏感時(shí)，有時(shí)寫動(dòng)態(tài)計(jì)劃會(huì)有點(diǎn)浪費(fèi)時(shí)間，但是閉包可能就足夠了。

閉包也可以用來定義一些邏輯相同但命名不同的函數(shù)，比如本文中的分類函數(shù)，在這些情況下，它更加整潔而優(yōu)雅，更加易讀。

下次試試閉包吧，別用效率低下的遞歸了。

本文轉(zhuǎn)載自微信公眾號(hào)「Python七號(hào)」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系Python七號(hào)公眾號(hào)。