與查表

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的支持