Taobao FED

性能优化:memoization

性能优化:memoization

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
'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 的代码改写为如下形式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
'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对象有可能造成内存泄露。

处理多个参数

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

例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
'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这个值。下面是另一种处理多个参数的情况(将多个参数组成一个索引):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
'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

1
2
3
4
5
6
7
8
9
10
11
12
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的函数是指:函数的输出完全由其输入决定,且不会有副作用的函数。下面的函数就是一个反例:

1
2
3
4
5
6
7
8
9
10
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的结果并不理想,可以参考underscorelodashmemoize来做优化。

使用lodashmemoize方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
* @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);

对比结果:

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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的版本还快:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
'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)。例如下面这样的归并排序算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
'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的递归式写法为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
'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的形式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#!/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))

参考资料