# 性能优化：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);

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

### 处理多个参数

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

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

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

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

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

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

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

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

### 他山之石

 #!/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))

### 参考资料

19 0

20 0

57 0

95 0
C++服务性能优化的道与术-道篇：阿姆达尔定律

76 0

1. 避免使用@important 外部的css文件中使用@important会使得页面在加载时增加额外的延迟。最好使用link   2. 避免使用css表达式（表达式可能会造成极大的计算量）   3. 避免通配选择器 在初期使用*{margin:0;padding:0},以此来消除标签的默认布局和不同浏览器的对同一个标签的不同的渲染。
881 0

920 0
+关注
xiaoqb

AliSQL性能优化与功能突破的演进之路