热搜词:家常手机

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

作者:利哥 下载:word格式

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

递归计算场景性能优化,优化的三种算法-第1张-生活-醋百科

'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对象有可能造成内存泄露。

递归计算场景性能优化,优化的三种算法-第2张-生活-醋百科

处理多个参数

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

例如:

'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函数,假设执行多次:

递归计算场景性能优化,优化的三种算法-第3张-生活-醋百科

可以看到内存的增长也是有限的,并且最终控制在了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);}

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

递归计算场景性能优化,优化的三种算法-第4张-生活-醋百科

递归计算场景性能优化,优化的三种算法-第5张-生活-醋百科

递归计算场景性能优化,优化的三种算法-第6张-生活-醋百科

自动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前后的两个版本:

递归计算场景性能优化,优化的三种算法-第7张-生活-醋百科

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

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

上面自动memoization的结果并不理想,可以参考underscorelodashmemoize来做优化。

使用lodashmemoize方法:

/*** @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);

对比结果:

递归计算场景性能优化,优化的三种算法-第8张-生活-醋百科

可以看到lodashmemoize方法减少了一半执行时间。进一步优化:

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

递归计算场景性能优化,优化的三种算法-第9张-生活-醋百科

科普下: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);

递归计算场景性能优化,优化的三种算法-第10张-生活-醋百科

但是上面这些函数都存在问题,如果输入数目过大,会引发调用栈超过限制异常: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());

递归计算场景性能优化,优化的三种算法-第11张-生活-醋百科

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

递归计算场景性能优化,优化的三种算法-第12张-生活-醋百科

解决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。

TAG: 多个 参数 多维 递归计算场景性能优化 优化的三种算法

大家都在看