备案控制台
探索云世界
开发者社区 开发与运维 文章 正文

性能优化：memoization

2016-08-05 3106
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介：

性能优化：memoization

memoization适用于递归计算场景，例如 fibonacci 数值 的计算。

'use strict';

let n = process.env.N || 50;

console.log('process $', process.pid);
console.log('fibonacci recursive version with n = ', n);
let count = 0;
function fibonacci(n) {
  count++;
  //console.log(count);
  if (n == 0 || n == 1) {
    return n;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}
fibonacci(n);
console.log('process memory usage', process.memoryUsage());
console.log('final count', count);

如果使用这种递归的写法去计算第 50 个 fibonacci 数值，需要执行 40730022147 次。随着执行次数的增加，执行所需时间成指数上涨：

memoization的技巧在于将计算过的结果『缓存』下来，避免重复计算带来的成本，例如将计算 fibonacci 的代码改写为如下形式：

'use strict';

let N = process.env.N || 50;
let count = 0;

let fibonacci = (function() {
  let memo = {};
  function f(n) {
    count++;
    let value;
    if (n in memo) {
      value = memo[n];
    } else {
      if (n == 0 || n == 1) {
        value = n;
      } else {
        value = f(n - 1) + f(n - 2);
      }
      memo[n] = value;
    }
  }
  return f;
})();

fibonacci(N);

console.log('process memory usage', process.memoryUsage());
console.log('final count', count);

计算第 50 个 fibonacci 值只需要 99 次，执行时间为 0.06 秒，只有递归版本执行时间（546.41 秒）的万分之一，使用的内存（RSS 值 20111360）只有递归版本（RSS 值为 36757504）的 54%。

值得注意的是：这里闭包使用的memo对象有可能造成内存泄露。

处理多个参数

如果需要处理多个参数，需要把缓存的内容变成多维数据结构，或者把多个参数结合起来作为一个索引。

例如：

'use strict';

let N = process.env.N || 50;

let fibonacci = (function() {
  let memo = {};
  function f(x, n) {
    let value;
    memo[x] = memo[x] || {};
    if (x in memo && n in memo[x]) {
      value = memo[x][n];
    } else {
      if (n == 0 || n == 1) {
        value = n;
      } else {
        value = f(n - 1) + f(n - 2);
      }
      memo[x][n] = value;
    }
    return value;
  }
  return f;
})();

fibonacci('a', N);
fibonacci('b', N);

console.log('process memory usage', process.memoryUsage());

上面执行了两次fibonacci函数，假设执行多次：

可以看到内存的增长也是有限的，并且最终控制在了22097920这个值。下面是另一种处理多个参数的情况（将多个参数组成一个索引）：

'use strict';

let N = process.env.N || 50;
let count;
let memo = {};
const slice = Array.prototype.slice;

let fibonacci = (function() {
  count = 0;
  function f(x, n) {
    count++;
    let args = slice.call(arguments);
    let value;
    memo[x] = memo[x] || {};
    if (args in memo) {
      value = memo[args];
    } else {
      if(n == 0 || n == 1) {
        value = n;
      } else {
        value = f(x, n - 1) + f(x, n - 2);
      }
      memo[args] = value;
    }
    return value;
  }
  return f;
})();

let result;
for (let i = 0; i < N; i++) {
  count = 0;
  result = fibonacci('#' + i, i);
  console.log('process memory usage', process.memoryUsage());
  console.log('final count', count);
  console.log('result of #' + i, result);
}

与上面版本相比，内存有所增加，速度有所下降：

50 次对比

100 次对比

1000 次对比

自动memoization 

function memoize(func) {
  let memo = {};
  let slice = Array.prototype.slice;
  return function() {
    let args = slice.call(arguments);
    if (args in memo) {
      return memo[args];
    } else {
      return memo[args] = func.apply(this, args);
    }
  };
}

但是需要注意的是，并不是所有函数都可以自动memoization，只有referential transparency（引用透明）的函数可以。所谓referential transparency的函数是指：函数的输出完全由其输入决定，且不会有副作用的函数。下面的函数就是一个反例：

var bar = 1;

// foo 函数的结果还受到全局变量 bar 的影响
function foo(baz) {
  return baz + bar;
}

foo(1);
bar++;
foo(1);

对比自动memoization前后的两个版本：

自动memoization处理后的版本有所提高，但相比手动完全memoization的版本效率还是差了很多。

其实memoization这个词来自人工智能研究领域，其词源为拉丁语memorandum，这个词的创造者为Donald Michie，这种函数的设计初衷是为了提升机器学习的性能。随着函数式编程语言（Functional Programming，简称 FP）的兴起，例如 JavaScript、Haskell 以及 Erlang，这种用法才变得越来越流行。在前端编程中，可以使用memoization去处理各种需要递归计算的场景，例如缓存 canvas 动画的计算结果。

上面自动memoization的结果并不理想，可以参考underscore和lodash的memoize来做优化。

使用lodash的memoize方法：

/**
 * @filename: fibonacci-memoization-with-lodash.js
 */
'use strict';

let n = process.env.N || 50;
let _ = require('lodash');
let memoize = _.memoize;
let fibonacci = require('./fibonacci-recursive.js');

let newFibonacci = memoize(fibonacci);
let result = newFibonacci(n);
console.log('process memory usage', process.memoryUsage());
console.log('result', result);

对比结果：

可以看到lodash的memoize方法减少了一半执行时间。进一步优化：

module.exports = function memoize(func, context) {
  function memoizeArg(argPos) {
    var cache = {};
    return function() {
      if (argPos == 0) {
        if (!(arguments[argPos] in cache)) {
          cache[arguments[argPos]] = func.apply(context, arguments);
        }
        return cache[arguments[argPos]];
      } else {
        if (!(arguments[argPos] in cache)) {
          cache[arguments[argPos]] = memoizeArg(argPos - 1);
        }
        return cache[arguments[argPos]].apply(this, arguments);
      }
    };
  }
  var arity = func.arity || func.length;
  return memoizeArg(arity - 1);
};

科普下：function arity指的是一个函数接受的参数个数，这是一个被废弃的属性，现在应使用Function.prototype.length。
https://stackoverflow.com/questions/4848149/get-a-functions-arity

zakas 的版本更加快，甚至比我们将fibonacci手动memoization的版本还快：

'use strict';
let n = process.env.N || 50;
let count = 0;

function memoizer(fundamental, cache) {
  cache = cache || {};
  let shell = function(arg) {
    if (!cache.hasOwnProperty(arg)) {
      cache[arg] = fundamental(shell, arg);
    }
    return cache[arg];
  };
  return shell;
}

let fibonacci = memoizer(function(recur, n) {
  count++;
  return recur(n - 1) + recur(n - 2);
}, {
  0: 0,
  1: 1
});

let result = fibonacci(n);
console.log('process memory usage', process.memoryUsage());
console.log('count', count);
console.log('result', result);

但是上面这些函数都存在问题，如果输入数目过大，会引发调用栈超过限制异常：RangeError: Maximum call stack size exceeded。

一种解决的方法就是将递归（recursion）修改为迭代（iteration）。例如下面这样的归并排序算法：

'use strict';

let n = process.env.N || 100;
let isMemoized = process.env.M;
let test = [];

function merge(left, right) {
  let result = [];

  while (left.length > 0 && right.length > 0) {
    if (left[0] < right[0]) {
      result.push(left.shift());
    } else {
      result.push(right.shift());
    }
  }

  return result.concat(left).concat(right);
}

function mergeSort(items) {
  if (items.length == 1) {
    return items;
  } else {
    let middle = Math.floor(items.length / 2);
    let left = items.slice(0, middle);
    let right = items.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
  }
}

for (let i = 0; i < n; i++) {
  test.push(Math.random() * 10);
}

let result;
if (isMemoized) {
  let memoize = require('./zakas-memo.js');
  mergeSort = memoize(mergeSort);
  result = mergeSort(test);
} else {
  result = mergeSort(test);
}
console.log('process memory usage', process.memoryUsage());

而上面的排序函数在经过memoization后虽然不会抛出RangeError: Maximum call stack size exceeded的异常，但是在极端情况下也会因为内存不够分配导致失败：

解决RangeError: Maximum call stack size exceeded异常的一种方法是将递归的代码改写为迭代的代码，例如fibonacci的递归式写法为：

'use strict';

module.exports = function fibonacci(n) {
  n = parseInt(n);
  console.log('n = ', n);
  if (isNaN(n)) {
    return null;
  } else {
    let first = 0;
    let prev = 1;
    let sum;
    let count = 0;
    if (n <= 1) {
      sum = n;
    } else {
      for (let i = 2; i <= n; i++) {
        sum = first + prev;
        first = prev;
        prev = sum;
        console.log('i = ' + i + ':' + ' sum = ' + sum);
      }
    }
    return sum;
  }
};

他山之石

在 JavaScript 中我们是通过函数的形式来是实现函数的memoization，在 Python 中还可以用另一种被称为decorator的形式：

#!/usr/bin/env python
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)

print(fib(100))

参考资料

来自：http://taobaofed.org/blog/2016/07/14/performance-optimization-memoization/
作者： 云翮
文章标签：
JavaScript
前端开发
机器学习/深度学习
Shell
缓存
xiaoqb
目录
相关文章
创业之路＆下一个五年
|
9月前
|
存储 缓存 NoSQL
性能优化方案及思考
周末闲暇在家，朋友让我帮忙优化一个接口，这个接口之前每次加载都需要40s左右，经过优化将性能提了10倍左右；又加了缓存直接接口响应目前为300ms左右，于是将自己的优化思路整理总结一下
创业之路＆下一个五年
90 0
愿天堂没有BUG（公众号同名）
|
9月前
|
消息中间件 监控 固态存储
榨干服务器：一次惨无人道的性能优化
做过2B类系统的同学都知道，2B系统最恶心的操作就是什么都喜欢批量，这不，我最近就遇到了一个恶心的需求——50个用户同时每人导入1万条单据，每个单据七八十个字段，请给我优化。
愿天堂没有BUG（公众号同名）
117 0
飘渺11
|
10月前
|
监控 网络协议 安全
聊聊服务器性能优化～（建议收藏）
聊聊服务器性能优化～（建议收藏）
飘渺11
266 0
1169542316312847
|
11月前
|
Web App开发 SQL 缓存
性能优化
性能优化 前言 以前写过一篇性能优化的笔记前端性能优化小结，那时候算是列了一些优化的点，最近又读了几篇性能优化相关的文章，加上自己动手做了一些实践，相比之前有了更深一点的理解
1169542316312847
136 0
周辰晨
|
消息中间件 缓存 弹性计算
记一次性能优化实践
干货
周辰晨
117 0
记一次性能优化实践
大摩羯先生
|
SQL 缓存 NoSQL
服务性能优化总结
服务性能优化总结
大摩羯先生
90 0
Yj家的孺子牛
|
Android开发 芯片 UED
初识性能优化
性能优化一词相信大家都经常听到，今天我们就简单的来认识以下性能优化，了解做性能优化的必要性以及优化的分类。
Yj家的孺子牛
148 0
初识性能优化
果冻虾仁
|
并行计算 程序员 Linux
C++服务性能优化的道与术-道篇：阿姆达尔定律
在之前的文章 《2004：当CPU温和地走入那个良夜》 中我讲到了2000年后摩尔定律的终结，CPU时钟频率定格，多核成为CPU发展的新方向，并行计算成为趋势。
果冻虾仁
186 0
C++服务性能优化的道与术-道篇：阿姆达尔定律
技术小能手
|
SQL 算法 大数据
性能优化是个手艺活
技术小能手
11522 0
ali别离
|
C++
C++性能优化
ali别离
7370 0

热门文章

最新文章

  • 1
    随机生成UserAgent的python库（fake-useragent库）
  • 2
    使用zxing识别一幅包含多个二维码的图片
  • 3
    阿里云的SLB，植入cookie和重写cookie有什么区别？
  • 4
    基于Flink的实时日志分析系统实践
  • 5
    如何在服务器上跑python程序
  • 6
    电池技术多年没有较大发展，成为移动设备最大制约
  • 7
    Spread for WinRT 7新功能使用指南
  • 8
    codeforces Soldier and Number Game（dp+素数筛选）
  • 9
    九度oj-1001-Java
  • 10
    Android:随笔——对页面的View进行截图
  • 1
    分解商业周期时间序列：线性滤波器、HP滤波器、Baxter滤波器、Beveridge Nelson分解等去趋势2
    9
  • 2
    分解商业周期时间序列：线性滤波器、HP滤波器、Baxter滤波器、Beveridge Nelson分解等去趋势法1
    9
  • 3
    灰色关联分析(Grey Relation Analysis,GRA)中国经济社会发展指标
    9
  • 4
    极值分析：分块极大值BLOCK-MAXIMA、阈值超额法、广义帕累托分布GPD拟合降雨数据时间序列
    9
  • 5
    GARCH-DCC模型和DCC（MVT）建模估计
    8
  • 6
    ARIMA、ARIMAX、 动态回归和OLS 回归预测多元时间序列
    10
  • 7
    R语言预测期货波动率的实现：ARCH与HAR-RV与GARCH，ARFIMA模型比较
    10
  • 8
    spss modeler用决策树神经网络预测ST的股票
    9
  • 9
    K-means和层次聚类分析癌细胞系微阵列数据和树状图可视化比较
    8
  • 10
    matlab中使用VMD(变分模态分解)对信号去噪
    8

    • 相关课程

    更多
  • 网站性能前端监控课程
  • MySQL企业常见架构与调优经验分享
  • 云数据库优化经典案例

    • 相关电子书

    更多
  • 如何做小程序性能优化
  • 性能优化方法论
  • AliSQL性能优化与功能突破的演进之路

    • 相关实验场景

    更多
  • 高性能特性体验：ePQ 的详解与实战
    • 下一篇
    阿里云oss简介和使用流程
    为什么选择阿里云什么是云计算全球基础设施技术领先稳定可靠安全合规分析师报告
    产品和定价全部产品免费试用产品动态产品定价价格计算器云上成本管理
    解决方案技术解决方案
    文档与社区文档开发者社区天池大赛培训与认证
    权益中心免费试用高校计划企业扶持计划推荐返现计划
    支持与服务基础服务企业增值服务迁云服务官网公告健康看板信任中心
    关注阿里云
    关注阿里云公众号或下载阿里云APP，关注云资讯，随时随地运维管控云服务
    阿里云APP阿里云微信
    联系我们：4008013260
    法律声明Cookies政策廉正举报安全举报联系我们加入我们
    阿里巴巴集团淘宝网天猫全球速卖通阿里巴巴国际交易市场1688阿里妈妈飞猪阿里云计算AliOS万网高德UC友盟优酷钉钉支付宝达摩院淘宝海外阿里云盘饿了么
    © 2009-2024 Aliyun.com 版权所有 增值电信业务经营许可证： 浙B2-20080101 域名注册服务机构许可： 浙D3-20210002 京D3-20220015
    浙公网安备 33010602009975号浙B2-20080101-4