动态规划之使用备忘录来改进Javascript函数

2024-04-02 19:55

短信预约 -IT技能 免费直播动态提醒

动态规划已出现了十多年。根据维基百科，它既是一种数学优化方法，也是一种计算机编程方法。一个问题要真正应用动态规划，必须具有两个关键属性：最优结构和重叠子结构。本文不会细讲动态规划，而是将关注重叠子结构如何成为动态规划的关键属性之一。由于这关系到接下来的存储解决方案问题，所以对它的讨论非常重要。

本文将介绍什么是备忘录，备忘录对Javascript开发人员来说具有哪些价值，以及如何使用它来改进Javascript函数，从而对备忘录本身以及备忘录对优化应用程序的意义有一个深入了解。

在本文中，我们将讨论以下几个主题：

什么是备忘录
备忘录的主要概念
函数使用备忘录和不用备忘录的比较
备忘录的意义

什么是备忘录?

备忘录是缓存的一种形式，是一种方便进入和后续使用的值存储方法。备忘录是将已解决问题的结果记录下来，这样下次需要再次执行相同操作时，就不必重新计算了。不过，一个函数要使用备忘录，需要满足一定条件：它必须是引用透明的，即只有在调用函数的效果与用函数的返回值替换函数调用的效果完全相同的情况下才可以使用。

在Ruby、C++、Python等大多数编程语言中都有备忘录，这些语言中甚至有很多库可以简化。在本文中，我们将重点关注Javascript。编程语言或许不同，但其中的概念和思想是一致的。

备忘录的概念

备忘录需要理解以下两个概念：

1.引用透明

如果一个表达式可以在不改变程序行为的情况下被其对应的值替换(反之亦然)，那么它就被称为引用透明。这要求表达式必须是纯的，即对于相同的输入，表达式的值必须相同，并且它的求值必须没有副作用。非引用透明的表达式称为引用不透明。

有了上面的解释，我们可以很快地把它和备忘录的行为联系起来，这个概念让我们可以写出一个带备忘录的函数。

2.查找表

查找表(LUT)是一个数组，它用更为简单的数组索引操作取代运行时计算。该过程被称为“直接寻址”，LUT与哈希表的不同之处在于它检索的是一个值。

比较函数使用备忘录和不用备忘录

以经典的斐波那契数列定义为例：

function Fibo(n) {  
   if (n < 2) {  
       return n;  
   }  
   return Fibo(n - 1) + Fibo(n - 2);  
}

你可能预料到了，一旦开始使用大于20的数字，这个过程就会变得非常缓慢。而当你处理35左右的数字时，计算机估计也撑不住了。

解决方法是记录调用函数的返回结果

var IterMemoFib = function() {  
    var cache = [1, 1];  
    var fib = function(n) {  
        if (n >= cache.length) {  
            for (var i = cache.length; i <= n; i++) {  
               cache[i] = cache[i - 2] + cache[i - 1];  
           }  
       }  
       return cache[n];  
   }  

  return fib;  
}();

这部分有点麻烦，也不完全可读，或者你也可以让计算机来协助完成：

Fib = Fib.memoize();

由于技术(浏览器安全策略)限制，备忘录函数的参数只能是数组或标量值，不能是对象。

下面的代码扩展了Function对象以添加备忘录功能。如果函数是一个方法，则可以将对象传递给memoize()。

Function.prototype.memoize = function () {  
var pad = {};  
var self = this;  
 var obj = arguments.length > 0 ? arguments[i] : null;  
  
 var memoizedFn = function () {  
 // Copy the arguments object into an array: allows it to be used as  
   // a cache key.  
   var args = [];  
   for (var i = 0; i < arguments.length; i++) {  
     args[i] = arguments[i];  
  }  
  
   // Evaluate the memoized function if it hasn't been evaluated with  
   // these arguments before.  
   if (!(args in pad)) {  
     pad[args] = self.apply(obj, arguments);  
  }  
  
   return pad[args];  
};  
   
 memoizedFn.unmemoize = function () {  
   return self;  
 };  
  
 return memoizedFn;  
};  
   
Function.prototype.unmemoize = function () {  
 alert("Attempt to unmemoize an unmemoized function.");  
 return null;  
};