与查表

Question

更换功能我一直在看this MSDN video with Brian Beckman，我想更好地了解的东西，他说：

每imperitive程序员经过得知 功能可以通过查表来代替这一阶段

现在，我是一个从未上过大学的C＃程序员，所以也许我错过了其他人学会理解的东西。

是什么布赖恩意思：

功能可以通过查表来代替

是否有正在做的这个实际例子和它适用于所有的功能呢？他给出了我可以理解的罪恶功能的例子，但是我如何从更一般的角度理解这一点呢？

Answer 1

布赖恩刚刚表明，功能也是数据。函数通常只是一个集合到另一个集合的映射：y = f(x)是集合{x}到集合{y}的映射：f:X->Y。这些表格也是映射：[x1, x2, ..., xn] -> [y1, y2, ..., yn]。

如果函数对有限集进行操作（在编程中就是这种情况），那么它可以替换为表示该映射的表。正如Brian所提到的，每个命令程序员都要经历这一阶段的理解，即为了性能原因，函数可以替换为表查找。

但这并不意味着所有的功能都可以轻松地或应该被表格替换。这只意味着你理论上可以为每个功能做到这一点。所以结论是，函数是数据，因为表是（当然是编程的上下文中）。

Answer 2

在函数式编程中，有参照透明的概念。对于任何给定的参数（或一组参数），可以用一个函数替代它的值，而不改变程序的行为。

Referential Transparency

例如，考虑一个函数˚F即需要1个参数，Ñ。 F是引用透明的，所以F（n）可以替换为值F在n评估。这对程序没有任何影响。

在C＃中，这将是这样的：

public class Square 
{ 
    public static int apply(int n) 
    { 
     return n * n; 
    } 

    public static void Main() 
    { 
     //Should print 4 
     Console.WriteLine(Square.apply(2)); 
    } 
} 

（我不是很熟悉C＃，从Java背景的，所以你必须原谅我，如果这个例子是不是很语法正确）。

很明显在这里函数apply当用参数2调用时不能有任何其他的值，因为它只是返回它的参数的平方。函数的值只有取决于它的参数n;换句话说，就是参照透明度。

那我问你，Console.WriteLine(Square.apply(2))和Console.WriteLine(4)之间有什么区别。答案是，没有什么区别，因为所有意图都是目的。我们可以通过整个程序，将Square.apply(n)的所有实例替换为由Square.apply(n)返回的值，结果将完全相同。

那么Brian Beckman用他的关于用查表替换函数调用的表述意味着什么？他指的是这种引用透明功能的属性。如果Square.apply(2)可以替换为4而不影响程序行为，那么为什么不在第一次调用时缓存这些值，并将其放入由函数的参数索引的表中。为Square.apply(n)值的查找表看起来有点像这样：

   n: 0 1 2 3 4 5 ... 
Square.apply(n): 0 1 4 9 16 25 ... 

以及为Square.apply(n)任何电话，而无需调用该函数，我们可以简单地找到ñ在表中的缓存值，并替换函数调用这个值。很明显，这很可能会导致程序的大幅提速。

Answer 3

在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-1] + fib[n-2]替换发生的实际参数的模式变量n_，替代任何发生的fib[n_]”。重写器将迭代此过程，并在指数重写次数后最终生成fib[n]的值。这就像递归函数调用的形式，我们在JavaScript中获得与

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

注意它首先检查表，我们做递归调用之前已经明确地存储在两个值。 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事先定义更快。

这就是所谓的“automemoization”[原创 - 不是“记忆”，而是“为自己创造一份备忘录”的“memoization”]。

当然，在现实世界中，您必须管理创建的表的大小。要检查在数学表，做

DownValues[fib] 

要检查它们在JavaScript中，做到这

fibTable 

在REPL

如由Node.js的支持