Python中利用函數(shù)裝飾器實現(xiàn)備忘功能
“備忘”的定義
“memoization”(備忘)這個詞是由Donald Michie在1968年提出的,它基于拉丁語單詞“memorandum”(備忘錄),意思是“被記住”。雖然它和單詞“memorization”在某種程度上有些相似,但它并不是該單詞的錯誤拼寫。實際上,Memoisation是一種用于通過計算來加速程序的技術(shù),它通過記住輸入量的計算結(jié)果,例如函數(shù)調(diào)用結(jié)果,來實現(xiàn)其加速目的。如果遇到相同的輸入或者具有相同參數(shù)的函數(shù)調(diào)用,那么之前存儲的結(jié)果就可以被再次使用,從而避免一些不必要的計算。在很多情況下,可以使用一個簡單的數(shù)組來存儲結(jié)果,但也可以使用許多其他的數(shù)據(jù)結(jié)構(gòu),例如關(guān)聯(lián)數(shù)組,它在Perl語言中叫做哈希,在Python語言中稱為字典。
備忘功能可以由程序員顯式地編程實現(xiàn),但是一些編程語言如Python,都提供了自動備忘函數(shù)的機制。
利用函數(shù)裝飾器實現(xiàn)備忘功能
在前面關(guān)于遞歸函數(shù)的那章中,我們分別使用迭代和遞歸實現(xiàn)了斐波納契數(shù)列的求解。我們已經(jīng)證明,如果直接利用斐波納契數(shù)列的數(shù)學(xué)定義,在一個遞歸函數(shù)中實現(xiàn)數(shù)列的求解,正如下面的函數(shù)一樣,那么它將具有指數(shù)級的時間復(fù)雜度:
def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n-1) + fib(n-2)
此外,我們還提出了一種提高遞歸實現(xiàn)的時間復(fù)雜度的方法,即通過添加一個字典來記住之前函數(shù)的計算結(jié)果。這是一個顯式地使用備忘技術(shù)的例子,只是當時我們并沒有這么稱呼它。這種方法的缺點是,原始遞歸實現(xiàn)的明晰性和優(yōu)雅性丟失了。
造成以上缺點的原因是,我們改變了遞歸函數(shù)fib的代碼。不過下面的代碼不會改變我們的fib函數(shù),所以它的明晰性和易讀性并沒有丟失。為了實現(xiàn)該目的,我們使用自定義的函數(shù)memoize()。函數(shù)memoize()以函數(shù)作為參數(shù),并使用一個字典“memo”來存儲函數(shù)的結(jié)果。雖然變量“memo”和函數(shù)“f”僅僅具有局部備忘功能,但是它們通過函數(shù)“helper”被一個閉包捕獲,而memoize()將函數(shù)“helper”作為引用返回。所以,對memoize(fib)的調(diào)用將會返回一個helper()的引用,而在helper()中實現(xiàn)了fib()函數(shù)的功能以及一個用于保存還未存儲的結(jié)果到字典“memo”中的包裝器,并防止重新計算“memo”中已有的結(jié)果。
def memoize(f): memo = {} def helper(x): if x not in memo: memo[x] = f(x) return memo[x] return helper def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n-1) + fib(n-2) fib = memoize(fib) print(fib(40))
現(xiàn)在讓我們了解下所謂的裝飾器,首先看一下上面代碼中將備忘功能指派到fib函數(shù)的這一行:
fib = memoize(fib)
一種說法是,函數(shù)memoize()裝飾了函數(shù)fib。
將Memoize封裝成類
我們還可以將結(jié)果的緩存封裝到一個類中,如下面的例子所示:
class Memoize: def __init__(self, fn): self.fn = fn self.memo = {} def __call__(self, *args): if args not in self.memo: self.memo[args] = self.fn(*args) return self.memo[args]
因為我們使用了字典,所以不能使用可變參數(shù),即參數(shù)必須是不可變的。
Python中的裝飾器
Python中的裝飾器是一個可調(diào)用的Python對象,用于修改一個函數(shù)、方法或者類的定義。原始的對象,也就是即將被改變的那個對象,作為參數(shù)傳遞給一個裝飾器,而裝飾器則返回一個修改過的對象,例如一個修改過的函數(shù),它會被綁定到定義中使用的名字上。Python中的裝飾器與Java中的注解有一個相似的語法,即Python中的裝飾器語法可以看作是純粹的語法糖,使用“@”作為關(guān)鍵字。
示例:使用裝飾器實現(xiàn)備忘功能
其實,前面我們已經(jīng)使用了裝飾器,只是沒有這么稱呼它而已。實際上,本章開頭例子中的memoize函數(shù)就是一個裝飾器,我們使用它來記住fib函數(shù)的結(jié)果,只是我們沒有使用Python中裝飾器特殊的語法而已,即艾特字符“@”。
相比于寫成下面的形式
fib = memoize(fib)
我們可以這樣寫
@memoize
但這一行必須直接寫在被裝飾的函數(shù)之前,在我們的例子fib()中,如下所示:
def memoize(f): memo = {} def helper(x): if x not in memo: memo[x] = f(x) return memo[x] return helper @memoize def fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n-1) + fib(n-2) #fib = memoize(fib) print(fib(40))
利用裝飾器檢查參數(shù)
在講解遞歸函數(shù)的那章中我們介紹了階乘函數(shù),在那里我們希望保持函數(shù)盡可能簡單,而不想掩蓋基本理念,所以代碼中沒有包含任何參數(shù)檢查代碼。然而,如果別人以負數(shù)或者浮點數(shù)作為參數(shù)來調(diào)用我們的函數(shù),那么函數(shù)將會陷入一個死循環(huán)。
下面的程序使用一個裝飾器函數(shù)來確保傳給函數(shù)“factorial”的參數(shù)是一個正整數(shù):
def argument_test_natural_number(f): def helper(x): if type(x) == int and x > 0: return f(x) else: raise Exception("Argument is not an integer") return helper @argument_test_natural_number def factorial(n): if n == 1: return 1 else: return n * factorial(n-1) for i in range(1,10): print(i, factorial(i)) print(factorial(-1))
練習
1、我們的練習是一個古老的謎題。1612年,法國耶穌會士Claude-Gaspar Bachet提出了該謎題,即使用一個天平稱出從1磅到40磅的所有整數(shù)重量的東西(例如,糖或者面粉),求最少的砝碼數(shù)量。
第一個方法可能是使用1、2、4、8、16和32磅重量的這些砝碼。如果我們將砝碼放在天平的一端,而將物品放在另一端,那么這種方法用到的砝碼數(shù)量將是最小的。然而,我們也可以將砝碼同時放在天平的兩端,此時我們僅僅需要重量為1、3、9、27的砝碼。
編寫一個Python函數(shù)weigh(),該函數(shù)計算需要的砝碼以及它們在天平盤中的分布,以此來稱量1磅到40磅中任何一個整數(shù)重量的物品。
解決方法
1、我們需要前面章節(jié)“Linear Combinations”中的函數(shù)linear_combination()。
def factors_set(): factors_set = ( (i,j,k,l) for i in [-1,0,1] for j in [-1,0,1] for k in [-1,0,1] for l in [-1,0,1]) for factor in factors_set: yield factor def memoize(f): results = {} def helper(n): if n not in results: results[n] = f(n) return results[n] return helper @memoize def linear_combination(n): """ returns the tuple (i,j,k,l) satisfying n = i*1 + j*3 + k*9 + l*27 """ weighs = (1,3,9,27) for factors in factors_set(): sum = 0 for i in range(len(factors)): sum += factors[i] * weighs[i] if sum == n: return factors
2、利用上面的代碼,就能很容易寫出我們的函數(shù)weigh()。
def weigh(pounds): weights = (1,3,9,27) scalars = linear_combination(pounds) left = "" right = "" for i in range(len(scalars)): if scalars[i] == -1: left += str(weights[i]) + " " elif scalars[i] == 1: right += str(weights[i]) + " " return (left,right) for i in [2,3,4,7,8,9,20,40]: pans = weigh(i) print("Left pan: " + str(i) + " plus " + pans[0]) print("Right pan: " + pans[1] + "n")
- python裝飾器相當于函數(shù)的調(diào)用方式
- python函數(shù)裝飾器之帶參數(shù)的函數(shù)和帶參數(shù)的裝飾器用法示例
- Python函數(shù)裝飾器原理與用法詳解
- 讓你Python到很爽的加速遞歸函數(shù)的裝飾器
- Python裝飾器限制函數(shù)運行時間超時則退出執(zhí)行
- 使用python裝飾器計算函數(shù)運行時間的實例
- python裝飾器-限制函數(shù)調(diào)用次數(shù)的方法(10s調(diào)用一次)
- 淺析Python編寫函數(shù)裝飾器
- python函數(shù)裝飾器用法實例詳解
- python使用裝飾器和線程限制函數(shù)執(zhí)行時間的方法
- python通過裝飾器檢查函數(shù)參數(shù)數(shù)據(jù)類型的方法
- Python如何創(chuàng)建裝飾器時保留函數(shù)元信息
相關(guān)文章
Python 實現(xiàn)數(shù)據(jù)結(jié)構(gòu)-循環(huán)隊列的操作方法
這篇文章主要介紹了Python 實現(xiàn)數(shù)據(jù)結(jié)構(gòu)-循環(huán)隊列的操作方法,需要的朋友可以參考下2019-07-07