Python中利用函数装饰器实现备忘功能
“备忘”的定义
“memoization”（备忘）这个词是由Donald Michie在1968年提出的，它基于拉丁语单词“memorandum”（备忘录），意思是“被记住”。虽然它和单词“memorization”在某种程度上有些相似，但它并不是该单词的错误拼写。实际上，Memoisation是一种用于通过计算来加速程序的技术，它通过记住输入量的计算结果，例如函数调用结果，来实现其加速目的。如果遇到相同的输入或者具有相同参数的函数调用，那么之前存储的结果就可以被再次使用，从而避免一些不必要的计算。在很多情况下，可以使用一个简单的数组来存储结果，但也可以使用许多其他的数据结构，例如关联数组，它在Perl语言中叫做哈希，在Python语言中称为字典。
备忘功能可以由程序员显式地编程实现，但是一些编程语言如Python，都提供了自动备忘函数的机制。
利用函数装饰器实现备忘功能
在前面关于递归函数的那章中，我们分别使用迭代和递归实现了斐波纳契数列的求解。我们已经证明，如果直接利用斐波纳契数列的数学定义，在一个递归函数中实现数列的求解，正如下面的函数一样，那么它将具有指数级的时间复杂度：
def fib(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fib(n-1) + fib(n-2)
此外，我们还提出了一种提高递归实现的时间复杂度的方法，即通过添加一个字典来记住之前函数的计算结果。这是一个显式地使用备忘技术的例子，只是当时我们并没有这么称呼它。这种方法的缺点是，原始递归实现的明晰性和优雅性丢失了。
造成以上缺点的原因是，我们改变了递归函数fib的代码。不过下面的代码不会改变我们的fib函数，所以它的明晰性和易读性并没有丢失。为了实现该目的，我们使用自定义的函数memoize()。函数memoize()以函数作为参数，并使用一个字典“memo”来存储函数的结果。虽然变量“memo”和函数“f”仅仅具有局部备忘功能，但是它们通过函数“helper”被一个闭包捕获，而memoize()将函数“helper”作为引用返回。所以，对memoize(fib)的调用将会返回一个helper()的引用，而在helper()中实现了fib()函数的功能以及一个用于保存还未存储的结果到字典“memo”中的包装器，并防止重新计算“memo”中已有的结果。
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))
现在让我们了解下所谓的装饰器，首先看一下上面代码中将备忘功能指派到fib函数的这一行：
fib = memoize(fib)
一种说法是，函数memoize()装饰了函数fib。
将Memoize封装成类
我们还可以将结果的缓存封装到一个类中，如下面的例子所示：
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]
因为我们使用了字典，所以不能使用可变参数，即参数必须是不可变的。
Python中的装饰器
Python中的装饰器是一个可调用的Python对象，用于修改一个函数、方法或者类的定义。原始的对象，也就是即将被改变的那个对象，作为参数传递给一个装饰器，而装饰器则返回一个修改过的对象，例如一个修改过的函数，它会被绑定到定义中使用的名字上。Python中的装饰器与Java中的注解有一个相似的语法，即Python中的装饰器语法可以看作是纯粹的语法糖，使用“@”作为关键字。
示例：使用装饰器实现备忘功能
其实，前面我们已经使用了装饰器，只是没有这么称呼它而已。实际上，本章开头例子中的memoize函数就是一个装饰器，我们使用它来记住fib函数的结果，只是我们没有使用Python中装饰器特殊的语法而已，即艾特字符“@”。
相比于写成下面的形式
fib = memoize(fib)
我们可以这样写
@memoize
但这一行必须直接写在被装饰的函数之前，在我们的例子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))
利用装饰器检查参数
在讲解递归函数的那章中我们介绍了阶乘函数，在那里我们希望保持函数尽可能简单，而不想掩盖基本理念，所以代码中没有包含任何参数检查代码。然而，如果别人以负数或者浮点数作为参数来调用我们的函数，那么函数将会陷入一个死循环。
下面的程序使用一个装饰器函数来确保传给函数“factorial”的参数是一个正整数：
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磅的所有整数重量的东西（例如，糖或者面粉），求最少的砝码数量。
第一个方法可能是使用1、2、4、8、16和32磅重量的这些砝码。如果我们将砝码放在天平的一端，而将物品放在另一端，那么这种方法用到的砝码数量将是最小的。然而，我们也可以将砝码同时放在天平的两端，此时我们仅仅需要重量为1、3、9、27的砝码。
编写一个Python函数weigh()，该函数计算需要的砝码以及它们在天平盘中的分布，以此来称量1磅到40磅中任何一个整数重量的物品。
解决方法
1、我们需要前面章节“Linear Combinations”中的函数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、利用上面的代码，就能很容易写出我们的函数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")
熱AI工具
Undresser.AI Undress
人工智慧驅動的應用程序，用於創建逼真的裸體照片
AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。
Undress AI Tool
免費脫衣圖片
Clothoff.io
AI脫衣器
Video Face Swap
使用我們完全免費的人工智慧換臉工具，輕鬆在任何影片中換臉！
熱門文章
熱工具
記事本++7.3.1
好用且免費的程式碼編輯器
SublimeText3漢化版
中文版，非常好用
禪工作室 13.0.1
強大的PHP整合開發環境
Dreamweaver CS6
視覺化網頁開發工具
SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)
PHP和Python：解釋了不同的範例
Apr 18, 2025 am 12:26 AM
PHP主要是過程式編程，但也支持面向對象編程（OOP）；Python支持多種範式，包括OOP、函數式和過程式編程。 PHP適合web開發，Python適用於多種應用，如數據分析和機器學習。
在PHP和Python之間進行選擇：指南
Apr 18, 2025 am 12:24 AM
PHP適合網頁開發和快速原型開發，Python適用於數據科學和機器學習。 1.PHP用於動態網頁開發，語法簡單，適合快速開發。 2.Python語法簡潔，適用於多領域，庫生態系統強大。
PHP和Python：深入了解他們的歷史
Apr 18, 2025 am 12:25 AM
PHP起源於1994年，由RasmusLerdorf開發，最初用於跟踪網站訪問者，逐漸演變為服務器端腳本語言，廣泛應用於網頁開發。 Python由GuidovanRossum於1980年代末開發，1991年首次發布，強調代碼可讀性和簡潔性，適用於科學計算、數據分析等領域。
sublime怎麼運行代碼python
Apr 16, 2025 am 08:48 AM
在 Sublime Text 中運行 Python 代碼，需先安裝 Python 插件，再創建 .py 文件並編寫代碼，最後按 Ctrl B 運行代碼，輸出會在控制台中顯示。
Python vs. JavaScript：學習曲線和易用性
Apr 16, 2025 am 12:12 AM
Python更適合初學者，學習曲線平緩，語法簡潔；JavaScript適合前端開發，學習曲線較陡，語法靈活。 1.Python語法直觀，適用於數據科學和後端開發。 2.JavaScript靈活，廣泛用於前端和服務器端編程。
Golang vs. Python：性能和可伸縮性
Apr 19, 2025 am 12:18 AM
Golang在性能和可擴展性方面優於Python。 1)Golang的編譯型特性和高效並發模型使其在高並發場景下表現出色。 2)Python作為解釋型語言，執行速度較慢，但通過工具如Cython可優化性能。
vscode在哪寫代碼
Apr 15, 2025 pm 09:54 PM
在 Visual Studio Code（VSCode）中編寫代碼簡單易行，只需安裝 VSCode、創建項目、選擇語言、創建文件、編寫代碼、保存並運行即可。 VSCode 的優點包括跨平台、免費開源、強大功能、擴展豐富，以及輕量快速。
notepad 怎麼運行python
Apr 16, 2025 pm 07:33 PM
在 Notepad 中運行 Python 代碼需要安裝 Python 可執行文件和 NppExec 插件。安裝 Python 並為其添加 PATH 後，在 NppExec 插件中配置命令為“python”、參數為“{CURRENT_DIRECTORY}{FILE_NAME}”，即可在 Notepad 中通過快捷鍵“F6”運行 Python 代碼。
