Python 记忆化和缓存

Python 记忆化和缓存,许多算法可以受益于记忆化。首先回顾一些之前的示例,从而给出那些能获益于记忆化的函数类型特征。

前面介绍了几种常用的递归。最简单的递归形式是尾递归,它的参数易于和缓存中的值匹配。如果参数是整型值、字符串或者实例化的集合,那么可以快速比较参数来确定是否缓存了先前的计算结果。

从这些示例中可以看出,阶乘计算或查找斐波那契数等整型值计算的性能都会显著提升。适用于整型值的数值算法还包括查找质因子和计算整数的幂次方。

斐波那契数的递归版本的计算结果 F(n) 包含两个尾递归调用,定义如下:

Python 记忆化和缓存

这可以转化成一个循环,但设计上的任何改变都需要考量。递归定义的记忆化版本会非常快,并且无须过多地思考设计。

Syracuse函数是一类用于计算分形值的函数。Syracuse函数 S(n)定义如下:

Python 记忆化和缓存

递归调用后,会得到一个从起始值 C :

Python 记忆化和缓存

奇偶归一猜想(Collatz conjecture)是一个结果总为1的Syracuse函数。由 S(1) 开始的值会形成 1,4,2,1,… 的循环。探索该函数的行为需要记忆化的中间结果。一个有趣的问题是定位极长序列。请参阅https://projecteuler.net/problem=14,了解有关谨慎使用缓存的问题。

Syracuse函数的递归应用是一个具有“吸引子”的函数示例,其中数值被“吸引”至1。在一些高维函数中,吸引子可以是一条线,或是分形曲线。当吸引子是一个点时,记忆化会有所帮助,否则由于每个分形值都是唯一的,记忆化可能会成为障碍。

在处理集合时,缓存的好处可能会消失。如果集合的整型值、字符串或元组的数量碰巧相同,那么集合可能会重复,从而节省时间。然而,如果需要对集合进行多次计算,那么最好手动记忆化:执行一次计算并将结果赋给变量。

在使用可迭代对象、生成器函数和其他惰性对象时,缓存或记忆化是无用的。为了提供源序列中的下一个值,惰性函数会执行最少量的工作。
包含度量的原始数据通常使用浮点数。由于浮点数之间的精确比较可能无法正常工作,因此中间结果的记忆化也可能不起作用。

然而,包含计数的原始数据可能会受益于记忆化。由于它们都是整型值,因此可以确定整型比较(可能)会避免重新计算先前的值。一些应用于计数的统计函数会获益于使用fractions模块而非浮点数。当用Fraction(x,y)方法代替x/y,便能进行精确值匹配。可以使用float(some_fraction)方法来生成最终结果。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程