performance - 列表性能中长度为n的子序列

我实现了这个答案的版本https://stackoverflow.com/a/9920425/1261166(我不知道回答者的意图是什么)

sublistofsize 0 _        = [[]]
sublistofsize _ []       = []
sublistofsize n (x : xs) = sublistsThatStartWithX ++ sublistsThatDontStartWithX
  where sublistsThatStartWithX = map (x:) $ sublistofsize (n-1) xs
        sublistsThatDontStartWithX = sublistofsize n xs

我不确定的是sublistsThatStartWithX = map (x:) $ sublistofsize (n-1) xs
我认为map(x :)给出了问题性能的明智选择，但不确定如何解决。我已经完成了print $ length $ sublistofsize 5 $ primesToTakeFrom 50的分析

COST CENTRE                                  MODULE                                        no.     entries  %time %alloc   %time %alloc
sublistofsize                             Main                                          112     4739871   46.9   39.9    96.9  100.0
 sublistofsize.sublistsThatDontStartWithX Main                                          124     2369935    2.2    0.0     2.2    0.0
 sublistofsize.sublistsThatStartWithX     Main                                          116     2369935   47.8   60.1    47.8   60.1

我实施得很好吗？
有更快的方法吗？

最佳答案

我认为map(x :)给出了问题表现的明智选择

不能。map编码高效，可以线性运行，这里没有问题。

但是，您的递归可能是个问题。您都在调用sublistofsize (n-1) xs和sublistofsize n xs，它们给定了一个起始列表sublistofsize m (_:_:ys)，但确实对术语sublistofsize (m-1) ys进行了两次评估，因为在不同的递归步骤中它们之间没有共享。

所以我将应用动态编程来获得

subsequencesOfSize :: Int -> [a] -> [[a]]
subsequencesOfSize n xs = let l = length xs
                          in if n>l then [] else subsequencesBySize xs !! (l-n)
 where
   subsequencesBySize [] = [[[]]]
   subsequencesBySize (x:xs) = let next = subsequencesBySize xs
                             in zipWith (++) ([]:next) (map (map (x:)) next ++ [[]])

并不是说添加空列表是最漂亮的解决方案，但是您可以看到我如何将zipWith与置换列表一起使用，以便next的结果被使用两次-一次直接在长度为n的子序列列表中，一次在列表中长度为n + 1的子序列。

使用:set +s在GHCI中对其进行测试，您可以看到它比天真的解决方案快得多:

*Main> length $ subsequencesOfSize 7 [1..25]
480700
(0.25 secs, 74132648 bytes)
(0.28 secs, 73524928 bytes)
(0.30 secs, 73529004 bytes)
*Main> length $ sublistofsize 7 [1..25] -- @Vixen (question)
480700
(3.03 secs, 470779436 bytes)
(3.35 secs, 470602932 bytes)
(3.14 secs, 470747656 bytes)
*Main> length $ sublistofsize' 7 [1..25] -- @Ganesh
480700
(2.00 secs, 193610388 bytes)
(2.00 secs, 193681472 bytes)
*Main> length $ subseq 7 [1..25] -- @user5402
480700
(3.07 secs, 485941092 bytes)
(3.07 secs, 486279608 bytes)