免费自助建站哪家好,wordpress cmd,在网上注册公司的流程,网站 首页 关键词“备忘”的定义“memoization”(备忘)这个词是由Donald Michie在1968年提出的#xff0c;它基于拉丁语单词“memorandum”(备忘录)#xff0c;意思是“被记住”。虽然它和单词“memorization”在某种程度上有些相似#xff0c;但它并不是该单词的错误拼写。实际上#xff0…“备忘”的定义“memoization”(备忘)这个词是由Donald Michie在1968年提出的它基于拉丁语单词“memorandum”(备忘录)意思是“被记住”。虽然它和单词“memorization”在某种程度上有些相似但它并不是该单词的错误拼写。实际上Memoisation是一种用于通过计算来加速程序的技术它通过记住输入量的计算结果例如函数调用结果来实现其加速目的。如果遇到相同的输入或者具有相同参数的函数调用那么之前存储的结果就可以被再次使用从而避免一些不必要的计算。在很多情况下可以使用一个简单的数组来存储结果但也可以使用许多其他的数据结构例如关联数组它在Perl语言中叫做哈希在Python语言中称为字典。备忘功能可以由程序员显式地编程实现但是一些编程语言如Python都提供了自动备忘函数的机制。利用函数装饰器实现备忘功能在前面关于递归函数的那章中我们分别使用迭代和递归实现了斐波纳契数列的求解。我们已经证明如果直接利用斐波纳契数列的数学定义在一个递归函数中实现数列的求解正如下面的函数一样那么它将具有指数级的时间复杂度def fib(n):if n 0:return 0elif n 1:return 1else: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 helperdef fib(n):if n 0:return 0elif n 1:return 1else: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 fnself.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 helpermemoizedef fib(n):if n 0:return 0elif n 1:return 1else: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 helperargument_test_natural_numberdef factorial(n):if n 1:return 1else: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 factordef memoize(f):results {}def helper(n):if n not in results:results[n] f(n)return results[n]return helpermemoizedef linear_combination(n): returns the tuple (i,j,k,l) satisfyingn i*1 j*3 k*9 l*27 weighs (1,3,9,27)for factors in factors_set():sum 0for i in range(len(factors)):sum factors[i] * weighs[i]if sum n:return factors2、利用上面的代码就能很容易写出我们的函数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)
相关文章：
