从列表中获取长度为n的子序列的性能问题

Question

我实现了这个答案的一个版本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

我不确定的是 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

我实现的方式是否好？有没有更快的方法？

- Viktor Mellgren

---

你有测量过性能问题吗？这个问题在输出大小上基本上是线性的，而map不会改变这一点。 - GS - Apologise to Monica

我的想法是，map（x :) 使 x 挂起并等待递归调用的返回值，或者我错了吗...？ - Viktor Mellgren

它不会这样做，因为Haskell是惰性的，但即使它那么做了，为什么要在意呢？工作总得做完。 - GS - Apologise to Monica

由于我不太擅长Haskell并且正在寻找性能问题，我的猜测是那可能是问题所在的地方，也许与尾递归有关，我不知道。我又写了一个使用列表推导式更快的函数，但我的猜测是这个版本会更快，因为我做了很多其他事情，比如守卫，并且在另一个版本中没有质数的边界（它检查所有(!)组合）。 - Viktor Mellgren

我认为你需要更清晰地表明你的问题实际上是关于什么——例如，它是关于为什么与你的其他代码存在性能差异（如果是这样，请提供该其他代码和测量细节），还是有一种更快的编写上述代码的方法，或者是其他内容？ - GS - Apologise to Monica

@GaneshSittampalam：是的，我写的有什么问题吗？还有更快的方法吗？ - Viktor Mellgren

Answer 1

我认为对 x 使用 map 函数会有性能问题。

不会。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的子序列列表。

在GHCI中使用:set +s进行测试，您可以看到这比朴素的解决方案要快得多：

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

- Bergi

Answer 2

你的实现方式是该问题的自然“Haskell式”解决方法。

如果你最终使用了整个结果，那么在给定输出数据结构（[[a]]）的情况下，没有什么渐进更快的方法可以解决这个问题，因为它在输出长度的时间内是线性的。

使用map（x:）的方式很自然，可以将元素添加到每个列表的开头，鉴于我们正在使用列表，不太可能有任何显著更快的选项。

原则上，重复使用(++)是低效的，因为每次调用时都会遍历左侧参数，但在这种情况下总成本只增加一个额外的常数因子。

你可以通过使用累积参数otherResults来收集结果来改进它，但要进行这种更改，你还需要以相反的顺序传递prefix并在最后重新反转它，这可能会吞掉节省的时间：

sublistofsize' 0 _        prefix otherResults = reverse prefix : otherResults
sublistofsize' _ []       prefix otherResults = otherResults
sublistofsize' n (x : xs) prefix otherResults =
   sublistofsize' (n-1) xs (x:prefix) (sublistofsize' n xs prefix otherResults)

sublistofsize n xs = sublistofsize' n xs [] []

- GS - Apologise to Monica

---

谢谢，使用累加器的代码速度大约快了2倍（我已经修改了代码，不再需要反转前缀）。 - Viktor Mellgren

其实，我突然想到，如果您不关心结果的特定顺序，那么将输入列表先反转而不是每个输出列表都反转会更有效率。 - GS - Apologise to Monica

Answer 3

一个应该有帮助的优化是跟踪列表中是否有足够的元素来形成剩余的子序列。这可以通过保持一个指针跟踪 xs 前面 n-1 个元素并在递归时同时推进它们来非常有效地完成。

实现代码如下：

  nthtail 0 xs = xs
  nthtail _ [] = []
  nthtail n (x:xs) = nthtail (n-1) xs

  subseq 0 _ = [[]]
  subseq n xs =
    if null t
      then []
      else go n xs t
    where
      t = nthtail (n-1) xs  -- n should always be >= 1 here
      go 0 _ _  =  [[]]
      go _ _ [] = []
      go n xs@(x:xt) t = withx ++ withoutx
        where withx = map (x:) $ go (n-1) xt t
              withoutx = go n xt (tail t)

- ErikR

---

nthtail = drop？:-) - Bergi

@Bergi：唯一的区别在于nthtail接受任何(Num a)的n，如果提供一个浮点数是不正确的。 - Viktor Mellgren

支持整数（就像genericDrop一样），并且也匹配x在（x：xs）中，可以是（_：xs）。 - Viktor Mellgren

Answer 4

这是一个六年前的话题，但我相信我有一个值得在这里分享的代码。

@Bergi 的答案非常好，但我认为从以下两个方面来看，这项工作可以做得更好;

1. 虽然规格说明中没有提到，但它以反字典顺序返回组合。大多数情况下，人们希望按字典顺序排列。
2. 当使用 C(n,n/2) 进行测试时，它们的性能类似，但当像 C(100,5) 这样进行测试时，以下代码更快且更节省内存。

.

combinationsOf :: Int -> [a] -> [[a]]
combinationsOf 1 as        = map pure as
combinationsOf k as@(x:xs) = run (l-1) (k-1) as $ combinationsOf (k-1) xs
                             where
                             l = length as

                             run :: Int -> Int -> [a] -> [[a]] -> [[a]]
                             run n k ys cs | n == k    = map (ys ++) cs
                                           | otherwise = map (q:) cs ++ run (n-1) k qs (drop dc cs)
                                           where
                                           (q:qs) = take (n-k+1) ys
                                           dc     = product [(n-k+1)..(n-1)] `div` product [1..(k-1)]

让我们将它们与被接受答案下的测试用例进行比较。

*Main> length $ subsequencesOfSize 7 [1..25]
480700
(0.27 secs, 145,572,672 bytes)

*Main> length $ combinationsOf 7 [1..25]
480700
(0.14 secs, 95,055,360 bytes)

让我们来测试它们，比如对C(100,5)这样更难的内容进行测试。

*Main> length $ subsequencesOfSize 5 [1..100]
75287520
(52.01 secs, 77,942,823,360 bytes)

*Main> length $ combinationsOf 5 [1..100]
75287520
(17.61 secs, 11,406,834,912 bytes)

- Redu