优化的三种算法（递归计算场景性能优化）

优化的三种算法（递归计算场景性能优化）可以看到内存的增长也是有限的，并且最终控制在了22097920这个值。下面是另一种处理多个参数的情况（将多个参数组成一个索引）：上面执行了两次fibonacci函数，假设执行多次：处理多个参数如果需要处理多个参数，需要把缓存的内容变成多维数据结构，或者把多个参数结合起来作为一个索引。例如：

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 次。随着执行次数的增加，执行所需时间成指数上涨：

'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);}

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

自动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 pythondef memoize(f): memo = {} def helper(x): if x not in memo: memo[x] = f(x) return memo[x] return helper@memoizedef fib(n): if n == 0: return 0 elif n == 1: return 1 else: return fib(n - 1) fib(n - 2)print(fib(100))

参考资料

• https://www.sitepoint.com/implementing-memoization-in-javascript/

• Referential transparency)

• https://addyosmani.com/blog/faster-javascript-memoization/

• http://unscriptable.com/index.php/2009/05/01/a-better-javascript-memoizer/

• http://www.nczonline.net/blog/2009/01/27/speed-up-your-javascript-part-3/

• http://books.google.co.uk/books?id=PXa2bby0oQ0C&pg=PA44&lpg=PA44&dq=crockford memoization&source=bl&ots=HImnm6r1iH&sig=lrdT9Sk4F4yQ-xQ-TLTx4SpLkuk&hl=en&ei=C-hyTvaIEofB8QO21Nn_DQ&sa=X&oi=book_result&ct=result&resnum=4&ved=0CDMQ6AEwAw#v=onepage&q&f=false

• http://my.safaribooksonline.com/book/programming/javascript/9781449399115/functions/function_propertiesma_memoization_patter#X2ludGVybmFsX0ZsYXNoUmVhZGVyP3htbGlkPTk3ODE0NDkzOTkxMTUvNzY=

• memoize function javascript | npm memoize | lodash memoize | underscore memoize

• http://unscriptable.com/2009/05/01/a-better-javascript-memoizer/

• programming optimization techniques

• http://blog.stevenlevithan.com/archives/timed-memoization

• https://github.com/addyosmani/memoize.js

• function arity

• https://philogb.github.io/blog/2008/09/05/memoization-in-javascript/

• https://stackoverflow.com/questions/6184869/what-is-difference-between-memoization-and-dynamic-programming

• http://www.python-course.eu/python3_memoization.php

• https://en.wikipedia.org/wiki/Iteration

• https://en.wikipedia.org/wiki/Iterated_function

• https://www.ics.uci.edu/~eppstein/161/960109.html

• https://classes.soe.ucsc.edu/cmpe012/Summer09/labs/lab8-Recursion-vs-Iteration/

• google: iterative merge sort

• google: maximum call stack size exceeded | avoid maximum recursive

• http://www.python-course.eu/python3_decorators.php

• https://www.cs.cornell.edu/courses/cs3110/2011sp/lectures/lec22-memoization/memo.htm

• dynamic programming

来自：http://taobaofed.org/blog/2016/07/14/performance-optimization-memoization/

作者：云翮

更多深度技术内容，请关注云栖社区yunqiinsight。