用表查找替换函数

Question

我一直在和Brian Beckman一起观看这个MSDN视频,我想更好地理解他说的话:

每个不完美的程序员都经历了这个学习阶段,可以用表查找替换函数

现在,我是一名从未上过大学的C#程序员,所以也许在某个地方,我错过了其他人学会理解的东西.

Brian的意思是:

函数可以用表查找替换

是否有这方面的实际例子,是否适用于所有功能？他给出了我能理解的sin函数的例子,但是我如何用更一般的术语来理解它？

Answer 1

Brian刚刚表明函数也是数据.一般来说,函数只是一个集合到另一个集合的映射:y = f(x)是集合{x}到集合{y}的映射:f:X->Y.表格也是映射:[x1, x2, ..., xn] -> [y1, y2, ..., yn].

如果函数在有限集上运行(这是编程中的情况)那么它可以用表示该映射的表替换.正如Brian所说,每个命令式程序员都经历了这个理解阶段,只是出于性能原因,可以用表查找替换这些函数.

但这并不意味着所有功能都可以或者应该用表替换.这只意味着你理论上可以为每个功能做到这一点.因此结论是函数是数据,因为表是(在编程的上下文中).

Answer 2

在Mathematica中有一个可爱的技巧,它创建一个表作为评估函数调用为重写规则的副作用.考虑一下经典的慢纤维蛋白酶

fib[1] = 1
fib[2] = 1
fib[n_] := fib[n-1] + fib[n-2]

前两行为输入1和2创建表条目.这与说明完全相同

fibTable = {};
fibTable[1] = 1;
fibTable[2] = 1;

在JavaScript中.Mathematica的第三行说"请安装一个重写规则fib[n_],在用模式变量替换事件n_的实际参数后,将替换任何出现的事件fib[n-1] + fib[n-2]." 重写器将迭代此过程,并最终生成fib[n]指数重写后的值.这就像我们在JavaScript中使用的递归函数调用形式一样

function fib(n) {
  var result = fibTable[n] || ( fib(n-1) + fib(n-2) );
  return result;
}

请注意,在进行递归调用之前,它首先检查表中我们已经显式存储的两个值.Mathematica评估器自动执行此检查,因为规则的呈现顺序很重要 - Mathematica首先检查更具体的规则,然后检查更一般的规则.这就是为什么Mathematica有两种赋值形式,=并且:=:前者用于特定规则,其右侧可以在规则定义时进行评估; 后者适用于一般规则,在适用规则时必须评估其右侧.

现在,在Mathematica,如果我们说

fib[4]

它被重写为

fib[3] + fib[2]

然后到

fib[2] + fib[1] + 1

然后到

1 + 1 + 1

最后到3,在下次重写时不会改变.你可以想象,如果我们说fib[35],我们将生成巨大的表达式,填满内存,并融化CPU.但诀窍是用以下内容替换最终的重写规则:

fib[n_] := fib[n] = fib[n-1] + fib[n-2]

这表示"请用fib[n_]表达式替换每个出现的表达式,该表达式将为值安装新的特定规则,fib[n]并且还会生成值." 这个运行得快得多,因为它扩展了规则库 - 值表! - 在运行时.

我们也可以用JavaScript做同样的事情

function fib(n) {
  var result = fibTable[n] || ( fib(n-1) + fib(n-2) );
  fibTable[n] = result;
  return result;
}

这比先前的fib定义快得多.

这被称为"自动化"[原文如此 - 不是"记忆",而是"记忆",就像为自己创建备忘录一样].

当然,在现实世界中,您必须管理创建的表的大小.要检查Mathematica中的表,请执行

DownValues[fib]

要在JavaScript中检查它们,请执行此操作

fibTable

在诸如Node.JS支持的REPL中.