Haskell算法之间的渐近差异

Question

这里我们需要得到给定长度的所有子序列。如何计算给定函数的渐近复杂度？

import Data.List

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

会有多少"iterations"？我们能谈谈 "iterations" 吗？有什么优化吗？ GHC 7.10.2。编译器或程序员如何改进这一点？

Answer 1

我认为您的问题至少包含 2 个不同的问题，但是 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 的版本可能仍会尝试求值无限列表（但这无论如何都是伪代码）

Answer 2

这是一个相关的 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

Haskell算法之间的渐近差异

Haskell asymptotic difference between algorithms

optimization

haskell

ghc

asymptotic-complexity