如何提高这个Haskell代码的性能？

Question

我面临以下问题:

从初始集[1,2,3,4]计算所有可能的子集,即[[1],[2],[3],[4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4],[1,2,3],[1,2,4],[1,3,4],[2,3,4],[1,2,3,4]]

我编写了以下Haskell程序generate.hs,这是正确的.

generateSets :: Eq a => [a] -> [[a]] -> [[a]] -> [[a]]
generateSets []  _  _  = []
generateSets src [] _  = let isets = growthup [] src in generateSets src iset iset
generateSets src sets rsets = if null sets' then rsets else generateSets src sets' (rsets++sets')
  where sets' = concatMap (flip growthup src) sets

growthup :: (Eq a) => [a] -> [a] -> [[a]]
growthup ps ss = map (\suf -> ps++[suf]) ss'
  where ss' = nextoccurence ps ss

nextoccurence :: (Eq a) => [a] -> [a] -> [a]
nextoccurence [] ys = ys
nextoccurence xs ys = tail ys'
  where ys' = dropWhile (/= last xs) ys

在GHC解释器执行时ghci ...

ghci> generate [1,2,3,4] [] []
ghci> [[1],[2],[3],[4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4],[1,2,3],[1,2,4],[1,3,4],[2,3,4],[1,2,3,4]]

一切都很顺利,但程序花费的时间太长,例如只需要30个小尺寸.

我的问题是:有可能改进我的代码,以便从haskell懒惰,或garbagge收藏家或其他东西获得更多？

我的代码是并行性的良好候选者吗？

谢谢你的回复!

Answer 1

集合有很多子集.实际上,一组n个元素具有2 ⁿ个子集,因此一组30个元素具有超过十亿个子集.无论您使用哪种方法生成它们,即使迭代结果也需要很长时间.对于较大的套装,你几乎可以忘记在宇宙热死之前经历它们.

因此,只有在性能方面才能做到这么多,因为即使将算法的速度提高一倍,也只能让你同时处理一个元素的列表.对于大多数应用程序,真正的解决方案是避免必须首先枚举所有子集.

也就是说,有一种简单的归纳式思考子集的方法,这使得定义一个合适的子集函数变得容易,而无需进行任何相等的比较,这解决了实现的一些问题.

对于基本情况,空集有一个子集:空集.

subsets [] = [[]]

对于具有至少一个元素(x:xs)的集合,我们有包含该元素的子集,而不包含该元素的子集.我们可以x通过递归调用subsets xs来获取不包含的子集,我们可以通过预先x设置它们来获得其余的子集.

subsets (x:xs) = subsets xs ++ map (x:) (subsets xs)

subsequencesin 的定义Data.List以相同的原理工作,但采用稍微优化的方式,也以不同的顺序返回子集,更好地利用共享.但是,正如我所说,无论如何,列举长度为30的列表的子集都会很慢,最好的办法就是尽量避免必须先做到这一点.