JS专题之memoization

zhisheng 发布于2019-08-23 15:08 / 839人阅读

摘要：前言在计算机领域，记忆是主要用于加速程序计算的一种优化技术，它使得函数避免重复演算之前已被处理过的输入，而返回已缓存的结果。被执行了不是素数，其他数字默认是素数。我们可以看出，如果从开始打印斐波那契数列，函数被执行了次。

前言

在计算机领域，记忆（memoization）是主要用于加速程序计算的一种优化技术，它使得函数避免重复演算之前已被处理过的输入，而返回已缓存的结果。  -- wikipedia

Memoization 的原理就是把函数的每次执行结果都放入一个对象中，在接下来的执行中，在对象中查找是否已经有相应执行过的值，如果有，直接返回该值，没有才真正执行函数体的求值部分。在对象里找值是要比执行函数的速度要快的。

另外，Memoization 只适用于确定性算法，对于相同的输入总是生成相同的输出，即纯函数。

一、简单实现

通过 Memoization 的定义和原理，我们就可以初步实现 Memoization 了。

let memoize = function(func) {
  let cache = {};
  return function(key) {
    if (!cache[key])
      cache[key] = func.apply(this, arguments);
    return cache[key];
  }
}

是不是很简单~ 函数记忆其实就是利用闭包，将函数参数作为存储对象的键（key），函数结果作为存储对象的 value 值。

二、underscore 实现

underscore 的源码中有 Memoization 方法的封装，它支持传入一个 hasher 用来计算缓存对象 key 的计算方式。

_.memoize = function(func, hasher) {
  var memoize = function(key) {
    // 把存储对象的引用拿出来，便于后面代码使用
    var cache = memoize.cache;

    // hasher 是计算 key 值的方法函数。
    // 如果传入了 hasher，则用 hasher 函数来计算 key
    // 否则用 参数 key（即 memoize 方法传入的第一个参数）当 key
    var address = "" + (hasher ? hasher.apply(this, arguments) : key);

    // 如果 key 还没有对应的 hash 值（意味着没有缓存值，没有计算过该输入）
    // 就执行回调函数，并缓存结果值
    if (!_.has(cache, address))
      cache[address] = func.apply(this, arguments);

    // 从缓存对象中取结果值
    return cache[address];
  };

  // cache 对象被当做 key-value 键值对缓存中间运算结果
  memoize.cache = {};

  // 返回 momoize 函数, 由于返回函数内部引用了 memoize.cache, 构成了闭包，变量保存在了内存中。
  return memoize;
};

三、应用 - 判断素数

质数为在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数。

我们通过判断素数的函数，看看使用了函数记忆后的效果。

function isPrime(value) {
  console.log("isPrime 被执行了！");
  var prime = value != 1; // 1 不是素数，其他数字默认是素数。
  for (var i = 2; i < value; i++) {
    if (value % i == 0) {
      prime = false;
      break;
    }
  }
  return prime
}

let momoizedIsPrime = memoize(isPrime);

momoizedIsPrime(5) // isPrime 被执行了！
momoizedIsPrime(5) // 第二次执行，没有打印日志！

四、应用 - 计算斐波那契数列

斐波那契数列的特点是后一个数等于前面两个数的和

指的是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，斐波那契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=Fn-1+Fn-2

计算斐波那契数列是用来演示函数记忆很好的例子，因为计算斐波那契数列函数里面用了大量的递归。

var count = 0;
var fibonacci = function(n) {
  count++;
  return n < 2 ? n : fibonacci(n - 2) + fibonacci(n - 1);
}

for(var i = 0; i<= 10; i++) {
    console.log(`i: ${i}, ` + fibonacci(i));
}

// i: 0, 0
// i: 1, 1
// i: 2, 1
// i: 3, 2
// i: 4, 3
// i: 5, 5
// i: 6, 8
// i: 7, 13
// i: 8, 21
// i: 9, 34
// i: 10, 55

console.log(count);  // 453 !!!

我们可以看出，如果从 0 开始打印斐波那契数列，fibonacci 函数被执行了 453 次。那我们就牺牲一小部分内存，用来缓存每次计算的值。

fibonacci = memoize(fibonacci);

for(var i = 0; i<= 10; i++) {
    console.log(`i: ${i}, ` + fibonacci(i));
}
console.log(count); // 12

通过 memoize 函数记忆，使得函数执行次数只需要 12 次，大大优化了函数执行计算的性能消耗，

总结

函数记忆（memoization）将函数的参数和结果值，保存在对象当中，用一部分的内存开销来提高程序计算的性能，常用在递归和重复运算较多的场景。

GPU云服务器云服务器 Memoization memoize 专题页专题系列

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/101566.html

JavaScript专题之函数记忆

摘要：专题系列第十七篇，讲解函数记忆与菲波那切数列的实现定义函数记忆是指将上次的计算结果缓存起来，当下次调用时，如果遇到相同的参数，就直接返回缓存中的数据。 JavaScript 专题系列第十七篇，讲解函数记忆与菲波那切数列的实现定义函数记忆是指将上次的计算结果缓存起来，当下次调用时，如果遇到相同的参数，就直接返回缓存中的数据。举个例子： function add(a, b) { ...

RobinTang 2019-08-21 16:18 评论0 收藏0
JS专题之垃圾回收

摘要：如果没有引用指向该对象零引用，对象将被垃圾回收机制回收。经过增量标记改进后，垃圾回收的最大停顿时间可以减少到原来的左右。解除引用的真正作用是让值脱离执行环境，以便垃圾收集器下次运行时将其回收。前言在讲 JS 的垃圾回收（Garbage Collection）之前，我们回顾上一篇《JS专题之memoization》，memoization 的原理是以参数作为 key，函数结果作为 v...

liujs 2019-08-23 15:08 评论0 收藏0
Memoization in JavaScript

摘要：源码函数调用过，没有变化，参数时返回缓存值。而通过，可以把上一次的计算结果保存下来，而避免重复计算。这意味着将跳过渲染组件，并重用最后渲染的结果。 1. 基本概念在一个CPU密集型应用中，我们可以使用Memoization来进行优化，其主要用于通过存储昂贵的函数调用的结果来加速程序，并在再次发生相同的输入时返回缓存的结果。例如一个简单的求平方根的函数： const sqrt = Ma...

ccj659 2019-08-23 17:13 评论0 收藏0
JS专题之数组去重

摘要：将元素作为对象的键，默认键对应的值为如果对象中没有这个键，则将这个元素放入结果数组中去。前言数组去重在日常开发中的使用频率还是较高的，也是网上随便一抓一大把的话题，所以，我写这篇文章目的在于归纳和总结，既然很多人都在提的数组去重，自己到底了解多少呢。又或者是如果自己在开发中遇到了去重的需求，自己能想到更好的解决方案吗。这次我们来理一理怎么做数组去重才能做得最合适，既要考虑兼容性，...

only_do 2019-08-26 13:29 评论0 收藏0
【译】你可能不需要派生状态

摘要：所有派生状态导致的问题无异于两种无条件的根据来更新无论和是否匹配来更新。派生状态最常见的错误就是将这两者混和在一起。因此通常被用于性能优化而不是来判断派生状态的正确性。我们可以使用派生状态来存储过滤列表这种方式避免了重新计算。原文链接：https://reactjs.org/blog/2018... 翻译这篇文章的起因是因为在一次需求迭代中错误的使用了getDerivedState...

dinfer 2019-08-23 13:39 评论0 收藏0