JavaScript中记忆化的实际应用场景是什么？

Question

我发现像阶乘计算这样的例子来解释记忆化。这些很有帮助，但我正在寻找更深入的理解。

我想知道是否有人可以描述一种实际应用这种技术的场景，以及为什么他们使用它而不是递归或其他他们觉得使用记忆化可能帮助他们优化的方法。

- tim peterson

Answer 1

记忆化比仅仅缓存更具体一些。

考虑使用选择器在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函数，可用于任何其他函数。

- moribvndvs

---

超级/清晰的解释 - Karun

Answer 2

你可以使用记忆化技术来进行各种缓存。例如，你可以缓存一些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);
    });
  }
}

- snies

---

是的，你可以缓存函数调用的结果，但要以一种对函数调用的用户透明的方式进行。请参考我的更新答案或者@HackedByChinese的示例。 - snies

结果如何才能“对函数调用的用户不透明”？ - tim peterson

“记忆化”和“纯缓存”的区别在于缓存发生在函数调用的“幕后”。在这种情况下，“用户”是程序员“使用”函数，他不必编写“缓存”。 - snies

请注意，我的示例对于记忆化来说有点不寻常，因为我还使用了回调函数。但由于在JavaScript中处理回调函数非常普遍，所以我使用了这个示例。 - snies

"幕后运作" 的意思是什么？ - tim peterson

Answer 3

如果您希望，您可以删除此内容，因为我实际上无法回答您的问题（即给您举一个使用备忘录技术的例子），但是我想指出备忘录技术旨在解决与递归完全不同类型的问题。备忘录技术存储方法调用的输出结果，以便将来派生相同方法调用（具有相同参数和对象绑定）的结果是查找，而不是计算。递归是一种函数算法。这意味着它们并不对立，因为您可以备忘录化递归函数的输出。

- Noah Freitas

---

感谢您对如何将记忆化与递归结合使用以及它们不能直接进行比较的澄清。 - tim peterson