3

我找到了诸如阶乘计算之类的例子来解释memoization。这些很有帮助，但我正在寻找更深入的理解。

我想知道是否有人可以描述这种技术在现实世界中的应用，以及为什么他们使用它而不是递归或者他们认为使用记忆化可能有助于他们优化的任何其他方法。

4

3 回答 3

7

记忆比缓存更具体一点。

考虑使用选择器在 DOM 中搜索元素，就像使用 jQuery 一样。说，$('.some-selector')。在这种情况下，我调用函数$，告诉它为我找到所有具有 CSS 选择器“.some-selector”的元素。假设文档很大，我需要调用$('.some-selector')很多次。

您可以假设每次调用$('.some-selector')都将返回相同的结果，因此，每次调用时执行实际处理都是浪费精力。因此，$可以使用参数（在这种情况下为“.some-selector”）作为某个查找表或字典中的键。第一次使用该参数调用函数时，它会正常处理，使用参数作为键将结果放入字典中，然后返回结果。后续调用会发现该键在字典中有一个值，表示已经计算过的结果，所以它只是返回那些之前的结果。最终效果是您不会浪费时间寻找您已经知道的结果。

一个粗略的 JavaScript 示例：

var _dictionary = {};

function $(selector) {
   if (_dictionary[selector]) return _dictionary[selector]; // lookup the results of the selector and return them if they exist

   // otherwise, execute the function's logic normally
   // TODO: search logic
   var results = doSearch();

   _dictionary[selector] = results;

   return results;

}

此链接更详细，甚至包括memoize可用于任何其他功能的通用 JS 函数。

于 2012-05-16T02:34:22.750 回答
2

您可以使用 memoization 进行各种缓存。例如，您可以缓存一些 ajax 调用的结果。

例子：

var cache = new Array()

function memoized_ajax(url, callback) (
  if (cache[url]) {      
    callback(cache[url]);  // we already know the result for this url
  }
  else {
    $.ajax({
      url: url,
      success: function(data) {
        cache[url] = data;   // we will remember result for this url
        callback(data);
    });
  }
}
于 2012-05-16T02:26:42.047 回答
1

如果你愿意，你可以删除它，因为我不能真正回答你的问题（即给你一个使用记忆的例子），但我想指出记忆是为了解决与递归完全不同类型的问题。记忆化存储方法调用的输出，以便派生未来相同方法调用（相同参数和对象绑定）的结果是查找而不是计算。递归是一种函数算法。这意味着它们并不反对，因为您可以记住递归函数的输出。

于 2012-05-16T02:31:11.263 回答