F中的緩慢遞歸遞歸＃

我有一個F＃函數，它返回跳轉n的模式中從0開始的數字列表，選擇n，跳過n，選擇n ...直到限制。例如，輸入2的這個函數將返回[2, 3, 6, 7, 10, 11...]。F中的緩慢遞歸遞歸＃

最初我實現此作爲如下面的非尾遞歸函數：

let rec indicesForStep start blockSize maxSize = 
    match start with 
    | i when i > maxSize -> [] 
    | _ -> [for j in start .. ((min (start + blockSize) maxSize) - 1) -> j] @ indicesForStep (start + 2 * blockSize) blockSize maxSize

以爲尾遞歸是可取的，我重新實現它使用的蓄能器列表如下：

let indicesForStepTail start blockSize maxSize = 
    let rec indicesForStepInternal istart accumList = 
     match istart with 
     | i when i > maxSize -> accumList 
     | _ -> indicesForStepInternal (istart + 2 * blockSize) (accumList @ [for j in istart .. ((min (istart + blockSize) maxSize) - 1) -> j]) 
    indicesForStepInternal start []

然而，當我在單聲道下用參數1,1和20,000（即應該返回[1, 3, 5, 7...]高達20,000）時，在fsi下運行它時，尾遞歸版本明顯比第一版本慢（12秒與亞秒相比）。

爲什麼尾遞歸版本較慢？是因爲列表串聯？它是一個編譯器優化？我有沒有實現它尾遞歸？

我也覺得好像我應該使用高階函數來做到這一點，但我不確定如何去做。

來源

2011-03-28 Gnat

不幸的是，我沒有時間來提供替代的代碼，但幾個簡單的觀察：1）它是尾遞歸，2）名單追加爲O（N），因此效率低下。我建議反轉（下移）你的列表理解，把它歸結爲accumList，並在你返回第一個模式匹配之前反轉accumList。 – Daniel 2011-03-28 14:37:52

非常感謝大家;這些答案非常有幫助，信息量大，教育程度也很高。 – Gnat 2011-03-29 14:20:06

正如dave指出的那樣，問題在於您正在使用@運算符來追加列表。這是比尾遞歸更重要的性能問題。事實上，尾遞歸併不會真的加速程序太多（但它使得它在堆棧溢出的大輸入上工作）。

您第二個版本較慢的原因是您要將較短的清單（使用[...]生成的清單）附加到較長的清單（accumList）。這比將較長列表附加到較短列表要慢（因爲操作需要複製第一個列表）。

let indicesForStepTail start blockSize maxSize = 
    let rec indicesForStepInternal istart accumList = 
     match istart with 
     | i when i > maxSize -> accumList |> List.rev 
     | _ -> 
      let acc = 
      [for j in ((min (istart + blockSize) maxSize) - 1) .. -1 .. istart -> j] 
      @ accumList 
      indicesForStepInternal (istart + 2 * blockSize) acc 
    indicesForStepInternal start []

正如你所看到的，這有短名單（使用[...]生成）：

您可以通過收集在蓄電池中的元素以相反的順序，然後返回結果之前扭轉它修復作爲@的第一個參數，並且在我的機器上，它具有與非尾遞歸版本類似的性能。請注意，[ ... ]理解會以相反的順序生成元素 - 以便它們可以在最後逆轉。

你也可以寫了整個事情更加好聽使用F＃seq { .. }語法。您可以完全避免使用@運營商，因爲它可以讓你使用yield!使用yield產生個人elemetns和執行尾遞歸調用：

let rec indicesForStepSeq start blockSize maxSize = seq { 
    match start with 
    | i when i > maxSize ->() 
    | _ -> 
     for j in start .. ((min (start + blockSize) maxSize) - 1) do 
     yield j 
     yield! indicesForStepSeq (start + 2 * blockSize) blockSize maxSize }

這是我怎麼會寫。當調用它時，你只需要添加Seq.toList來評估整個惰性序列。這個版本的性能與第一個類似。

編輯隨着丹尼爾的更正，Seq版本實際上稍微快一點！

來源

2011-03-28 14:43:45

我相信它需要'讓rec'和你的遞歸調用應該是'indicesForStepSeq'。 – Daniel 2011-03-28 14:56:24

@Daniel：謝謝！你是對的，這個錯誤總是發生在我身上:-)。現在，'Seq'版本實際上是一個有點快...... – 2011-03-28 15:50:08

爲了好奇，我改變了最後一個函數使用一個表的表達式，而不是一個序列的表達，併成爲令人難以置信的慢（30秒，'1 20000' ，即比OP的代碼慢得多）。任何人都知道爲什麼發生？ – wmeyer 2011-03-28 16:22:33

這看起來像列表附加是問題。追加基本上是第一個參數大小的O（N）操作。通過累積在左邊，這個操作需要O（N^2）時間。

這種通常在功能代碼中完成的方式似乎是以相反的順序累積列表（通過累積在右側），然後在最後返回列表的反向。

你已經避免了第一個版本的附加問題，但正如你指出的那樣，不是尾遞歸。

在F＃中，解決這個問題的最簡單方法可能是序列。它看起來不是很實用，但你可以很容易地創建一個跟隨你的模式的無限序列，並使用Seq.take來獲得你感興趣的項目。

來源

2011-03-28 14:36:29

在F＃中，列表類型被實現爲單向鏈表。因此，如果x和y的長度不同，那麼x @ y和y @ x會得到不同的性能。這就是爲什麼你看到了性能的差異。（x @ y）的運行時間爲X.length。

// e.g. 
let x = [1;2;3;4] 
let y = [5]

如果你做了X @ y，則X（4元）將被複制到一個新的列表和其下一個內部指針將被設置爲現有ÿ列表。如果你做了y @ x，那麼y（1個元素）將被複制到一個新列表中，並且其下一個指針將被設置爲現有列表x。

我不會使用高階函數來做到這一點。我會用列表理解來代替。

let indicesForStepTail start blockSize maxSize = 
    [ 
     for block in start .. (blockSize * 2) .. (maxSize - 1) do 
      for i in block .. (block + blockSize - 1) do 
       yield i 
    ]

來源

2011-03-28 14:39:56 gradbot

F中的緩慢遞歸遞歸＃

回答

相關問題