惹巴性能與列表

Question

在數字哈斯克爾惹巴教程Wiki，有一個通道讀取（上下文）：

10.1融合，以及爲什麼需要它

惹巴主要取決於陣列的融合實現快速代碼。融合是 GHC執行的內聯和代碼轉換的組合，當 它編譯您的程序時，它是一個奇特的名字。融合過程將在Repa庫中定義的數組填充 循環與您在自己的模塊中編寫的「工作」函數合併。如果融合過程失敗，那麼生成的程序將比需要的慢得多，通常使用普通Haskell列表的等效程序的速度要慢10倍。另一方面，如果提供融合工作，則所產生的代碼將運行得如同完全寫入的C程序一樣快。一旦你瞭解到底發生了什麼，製作融合作品並不難 。

，我不明白的部分是這樣的：

「如果這種融合過程中出現故障，那麼 產生的程序會比實際需要的要慢得多，經常10倍 的慢等價的程序使用普通的Haskell列表。「

我明白爲什麼它會運行較慢，如果流融合失敗，但爲什麼它比列表慢得多？

謝謝！

Answer 1

編輯：這是不正確的 - 請參閱Don Nelson的評論（和他的回答 - 他知道更多關於圖書館的信息）。

不可變陣列不能共享組件;無視融合，對不可變數組的任何修改都必須重新分配整個數組。相比之下，雖然列表操作是非破壞性的，但它們可以共享部分：例如，通過創建一個新的列表（其中第一個單元格指向原始列表的第二個單元格），以恆定時間替換列表的頭部。此外，因爲列表可以逐步構建，所以通過重複調用函數來構建列表的生成器的函數仍然可以在O（n）時間內運行，而不帶融合的不可變數組上的等價函數將需要重新分配數組每次調用該函數，需要O（n^2）次。

Answer 2

通常，因爲列表是懶惰的，並且Repa數組是嚴格的。

如果您無法融合懶惰列表遍歷，例如

map f . map g 

你付出O（1）每值成本留下中間（懶惰）cons單元存在。

如果您未按照嚴格的順序對相同的遍歷進行融合，您至少需要支付每個值O（n）以分配嚴格的中間數組。另外，由於融合將你的代碼壓縮到一個無法識別的數據類型Stream中，爲了改善分析，你可以留下代碼，這些代碼只有太多的構造函數和其他開銷。