7

这是我在网上随机找到的一些关于动态编程的讲座中读到的一个问题。（我毕业了，我已经知道动态规划的基础了）

在解释为什么需要记忆的部分，即

// psuedo code 
int F[100000] = {0};
int fibonacci(int x){
    if(x <= 1) return x;
    if(F[x]>0) return F[x];
    return F[x] = fibonacci(x-1) + fibonacci(x-2);
}

如果不使用 memoization，那么许多子问题将被重新计算很多次，这使得复杂度非常高。

然后在一页上，笔记有一个没有答案的问题，这正是我想问的。在这里，我使用了确切的措辞和它显示的示例：

自动记忆：许多函数式编程语言（例如 Lisp）都内置了对记忆的支持。

为什么不用命令式语言（例如 Java）？

注释提供的 LISP 示例（它声称它是有效的）：

(defun F (n)
    (if
        (<= n 1)
        n
        (+ (F (- n 1)) (F (- n 2)))))

它提供的 Java 示例（它声称它是指数级的）

static int F(int n) {
  if (n <= 1) return n;
  else return F(n-1) + F(n-2);
}

在阅读本文之前，我什至不知道某些编程语言中内置了对记忆的支持。

注释中的说法是否属实？如果是，那么为什么命令式语言不支持它？

4

3 回答 3

5

关于“LISP”的说法非常模糊，他们甚至没有提到他们所指的LISP 方言或实现。我熟悉的所有 LISP 方言都没有自动记忆功能，但是 LISP 可以很容易地编写一个包装函数，将任何现有函数转换为一个记忆函数。

全自动、无条件的记忆将是一种非常危险的做法，并且会导致内存不足错误。在命令式语言中情况会更糟，因为返回值通常是可变的，因此不可重用。命令式语言通常不支持尾递归优化，进一步降低了记忆的适用性。

于 2016-09-07T07:47:34.177 回答
3

对 memoization 的支持无非就是拥有一流的功能。

如果你想记住一个特定情况的 Java 版本，你可以明确地编写它：创建一个哈希表，检查现有值等。不幸的是，你不能轻易地概括这一点来记住任何函数。具有一流函数的语言使编写函数和记忆它们几乎是正交问题。

基本情况很简单，但您必须考虑递归调用。在像 OCaml 这样的静态类型函数式语言中，被记忆的函数不能只是递归地调用自己，因为它会调用非记忆的版本。但是，对现有函数的唯一更改是接受一个函数作为参数，命名为 example self，只要函数想要递归，就应该调用它。然后，通用记忆工具提供适当的功能。此答案中提供了一个完整的示例。

Lisp 版本有两个特性，使记忆现有函数更加简单。

  1. 您可以像操作任何其他值一样操作函数
  2. 您可以在运行时重新定义函数

例如，在 Common Lisp 中，您定义F：

(defun F (n)
  (if (<= n 1)
      n
      (+ (F (- n 1))
         (F (- n 2)))))

然后，你看到你需要记忆这个函数，所以你加载了一个库：

(ql:quickload :memoize)

...然后你记住F：

(org.tfeb.hax.memoize:memoize-function 'F)

该工具接受参数以指定应缓存哪些输入以及使用哪个测试函数。然后，该函数F被一个新函数替换，该函数引入了使用内部哈希表的必要代码。F对inside的递归调用F现在调用的是包装函数，而不是原来的（你甚至不需要重新编译F）。唯一的潜在问题是原件F是否经过尾调用优化。您可能应该声明它notinline或使用DEF-MEMOIZED-FUNCTION.

于 2016-09-07T08:21:34.340 回答
1

尽管我不确定任何广泛使用的 Lisp 是否支持自动记忆，但我认为记忆在函数式语言中更常见的原因有两个，另外一个原因是 Lisp 系列语言。

首先，人们用函数式语言编写函数：其结果仅取决于其参数且不会对环境产生副作用的计算。任何不符合该要求的东西根本不适合记忆。而且，命令式语言就是那些不满足或可能不满足这些要求的语言，因为否则它们就不是命令式的！

当然，即使在像（大多数）Lisp 这样的功能友好的语言中，您也必须小心：您可能不应该记住以下内容，例如：

(defvar *p* 1)

(defun foo (n)
  (if (<= n 0)
      *p*
    (+ (foo (1- n)) (foo (- n *p*)))))

其次是函数式语言通常想谈论不可变的数据结构。这意味着两件事：

  1. 记忆一个返回大型数据结构的函数实际上是安全的
  2. 构建非常大的数据结构的函数通常需要消耗大量垃圾，因为它们不能改变临时结构。

(2) 有一点争议：普遍认为 GC 现在非常好，这不是问题，复制非常便宜，编译器可以做魔术等等。好吧，写过这样的函数的人会知道这只是部分正确：GC很好，复制很便宜（但是通过指针追逐大型结构来复制它们通常对缓存非常不利），但实际上还不够（和编译器几乎从不做他们声称做的魔法）。因此，您要么通过无故诉诸非功能性代码来作弊，要么记忆。如果你记忆这个函数，那么你只构建一次所有的临时结构，一切都变得便宜（除了在记忆中，但记忆中适当的弱点可以处理）。

第三：如果你的语言不支持简单的元语言抽象，那么实现记忆化是一件很痛苦的事情。或者换一种说法：你需要 Lisp 风格的宏。

要记忆一个函数，您至少需要做两件事：

  1. 您需要控制哪些参数是记忆的关键——并非所有函数都只有一个参数，也不是所有具有多个参数的函数都应该在第一个被记忆；
  2. 您需要在函数内部进行干预以禁用任何自尾调用优化，这将完全颠覆记忆。

虽然这样做有点残忍，因为它很容易，但我将通过取笑 Python 来证明这一点。

你可能认为装饰器是你在 Python 中记忆函数所需要的。事实上，你可以使用装饰器编写记忆工具（我已经写了一堆）。这些甚至是某种工作，尽管他们这样做主要是偶然的。

首先，装饰者不能轻易知道它正在装饰的功能。因此，您最终要么尝试基于函数的所有参数的元组进行记忆，要么必须在装饰器中指定要记忆的参数，或者同样令人讨厌的东西。

其次，装饰器将它正在装饰的函数作为参数获取：它不会在其中四处寻找。这实际上没问题，因为 Python 作为其“1956 年之后不发明任何概念”政策的一部分，当然不假设f在定义中的词法调用f（并且没有干预绑定）实际上是自调用。但也许有一天它会，你所有的记忆现在都会被打破。

总而言之：要健壮地记忆函数，您需要 Lisp 风格的宏。可能唯一具有这些的命令式语言是 Lisp。

于 2016-09-07T11:36:37.793 回答