性能优化：memoization

2021-12-18 23:50:51

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

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

性能优化：memoization

处理多个参数

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

例如：

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

性能优化：memoization

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

性能优化：memoization

性能优化：memoization

自动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的版本效率还是差了很多。

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

对比结果：

性能优化：memoization

可以看到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);
};

性能优化：memoization

科普下：function arity指的是一个函数接受的参数个数，这是一个被废弃的属性，现在应使用Function.prototype.length。
https://*.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);

性能优化：memoization

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

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

性能优化：memoization

解决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/
作者：云翮
上一篇：检法司行业 | “区块链+法治”


下一篇：【SQL 学习】表连接--natural join 的一个bug