哈斯克爾算法之間的漸近差異

這裏我們需要得到給定長度的所有子序列。如何計算給定函數的漸近複雜度？哈斯克爾算法之間的漸近差異

import Data.List 

subsequencesOfSize l n = [x | x <- subsequences l, length x == n]

它會是多少「迭代」？我們可以談論「迭代」嗎？任何優化？ GHC 7.10.2。編譯器或程序員如何改進這一點？

來源

2015-11-03 SDmitry

您是否有興趣在理論的複雜性或專門編譯輸出？ – sinelaw

生成一個巨大的列表，然後從中篩選出一些可能的小部分，效率很低。可能有更好的方法，即一種不同的算法，它將盡可能早地修剪較長的子序列。 – chi

@SDmitry：顛倒參數的順序（即'subsequencesOfSize n l'）會使更多的慣用設計，只爲記錄。 –

這裏有一個相關的SO問題，其中討論的subsequencesOfSize各種實現方式：

Haskell: comparison of techniques for generating combinations

和表現最好的一個，它使用記憶化：

Haskell: comparison of techniques for generating combinations

更新

另外在評論認爲這個版本@ user3237465提到：

subsequencesOfSize :: Int -> [a] -> [[a]] 
subsequencesOfSize n xs | n > length xs = [] 
subsequencesOfSize n xs = subsequencesBySize xs !! n where 
    subsequencesBySize [] = [[[]]] 
    subsequencesBySize (x:xs) = zipWith (++) ([] : map (map (x:)) next) (next ++ [[]]) 
     where next = subsequencesBySize xs

來源

2015-11-03 13:41:25 ErikR

還有一個更懶的版本：比較[this]（http://ideone.com/LrpZMh）和[this]（http://ideone.com/ZubdHR）。 – user3237465

此外，我認爲「分享」是比「memoization」更準確的術語。 – user3237465

@ user3237465 - 添加了您的版本 – ErikR

我認爲你的問題至少包含兩個不同的問題，但無論是（當前版本）GHC可以優化該

subsequencesOfSize l n = [x | x <- subsequences l, length x == n]

成類似

subsequencesOfSize l n = [x | x <- subsequences l, lengthIsGt n x, length x == n]

是非常值得懷疑的 - 我遠不是一個優化，超級編譯等方面的專家，但推斷需要使用length之類的東西，如lengthIsGt，這裏看起來非常不平凡，不太可能成爲編譯器的一組通用優化的一部分蒸發散。

P.S.實際上lengthIsGt版本將有可能仍然試圖評估無限列表如果包含length的條件包含lengthIsGt條件之前評估（不過這是僞代碼反正）

來源

2015-11-03 11:15:40

哈斯克爾算法之間的漸近差異

回答

相關問題