列表性能的长度为n的子序列 [英] subsequences of length n from list performance

问题描述

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

  sublistofsize 0 _ = [[]] 
 sublistofsize _ [ ] = [] 
 sublistofsize n（x：xs）= sublistsThatStartWithX ++ sublistsThatDontStartWithX 
其中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

 成本中心模块编号。条目％时间％分配％时间％分配
 sublistofsize主要112 4739871 46.9 39.9 96.9 100.0 
 sublistofsize.sublistsThatDontStartWithX主要124 2369935 2.2 0.0 2.2 0.0 
 sublistofsize.sublistsThatStartWithX主要116 2369935 47.8 60.1 47.8 60.1 
  

我是否以良好的方式实施它？
有没有更快的方法呢？

解决方案

我假设map x :)给出了一个性能明智的问题

没有。 map 被有效地编码并且以线性时间运行，这里没有问题。

然而，递归可能是一个问题。你们都在调用 sublistofsize（n-1）xs 和 sublistofsize n xs code> 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 !! （ln）
其中
 zipWith（++）（[b]）中的子序列大小（x：xs）= let next = subsequencesBySize xs 
子序列比例[] = [[[]]] 
 ]：next）（map（map（x :)）next ++ [[]]）
  

不是追加空列表是最漂亮的解决方案，但你可以看到我如何在移动列表中使用 zipWith ，以便从 next 被使用两次 - 一次直接在长度为n的子序列列表中，一次在长度为n + 1的子序列列表中。它在GHCI中的：set + s ，你可以看到这是如何比天真的解决方案快得多：

  *主>长度$ subsequencesOfSize 7 [1..25] 
 480700 
（0.25秒，74132648字节）
（0.28秒，73524928字节）
（0.30秒，73529004字节）
 * Main>长度$ sublistofsize 7 [1..25]  -  @Vixen（问题）
 480700 
（3.03秒，470779436字节）
（3.35秒，470602932字节）
（3.14秒，470747656字节）
 * Main>长度$ sublistofsize'7 [1..25]  -  @Ganesh 
 480700 
（2.00秒，193610388字节）
（2.00秒，193681472字节）
 * Main>长度$ subseq 7 [1..25]  -  @ user5402 
 480700 
（3.07秒，485941092字节）
（3.07秒，486279608字节）
  

I implemented a version of this answer https://stackoverflow.com/a/9920425/1261166 (I don't know what was intended by the person answering)

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

what I'm unsure of is sublistsThatStartWithX = map (x:) $ sublistofsize (n-1) xs

I assume that map (x:) gives a problem performance wise, but not sure of how to solve it. I've done profiling on 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

Did I implement it in a good way? Are there any faster ways of doing it?

解决方案

I assume that map (x:) gives a problem performance wise

No. map is coded efficiently and runs in linear time, no problems here.

However, your recursion might be a problem. You're both calling sublistofsize (n-1) xs and sublistofsize n xs, which - given a start list sublistofsize m (_:_:ys) - does evaluate the term sublistofsize (m-1) ys twice, as there is no sharing between them in the different recursive steps.

So I'd apply dynamic programming to get

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 ++ [[]])

Not that appending the empty lists is the most beautiful solution, but you can see how I have used zipWith with the displaced lists so that the results from next are used twice - once directly in the list of subsequences of length n and once in the list of subsequences of length n+1.

Testing it in GHCI with :set +s, you can see how this is drastically faster than the naive solutions:

*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)

这篇关于列表性能的长度为n的子序列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！