performance - Haskell:映射长度。组比显式递归慢得多吗？

Question

考虑这个整数素数分解的简单算法 n : 让 d'是 n 的除数最后找到。最初，设置 d'=1 .找到最小的除数 d>d'的 n , 并找到最大值 e这样 d<sup>e</sup>划分 n .追加d<sup>e</sup>找到答案并在 n/d<sup>e</sup> 上重复该过程.最后在n时停止变为 1。为简单起见，让我们忽略数学优化，例如停在 sqrt n。等

我用两种方式实现了它。第一个生成除法“尝试”列表，然后按除数对成功的进行分组。例如，对于 n=20 , 我们首先生成 [(2,20),(2,10),(2,5),(3,5),(4,5),(5,5),(5,1)] ，然后我们将其转换为所需的 [(2,2),(5,1)]使用 group和其他库函数。

第二个实现是一个显式递归，它跟踪指数 e一路上，追加d<sup>e</sup>一次最大的答案 e到达，继续寻找“下一个”d , 等等。

问题 1:为什么第一个实现的运行速度比第二个慢，尽管存在以下问题:

• 两个实现都执行div ，算法的核心步骤，次数大致相同。
• 惰性求值(和融合？)的效果是，从一开始就不必具体化上面说明的长列表。正如您在下面的代码中看到的那样，divTrials n ，我正在谈论的列表，是由一系列高阶函数转换的。在那，我认为这部分 map (\xs-> (head xs,length xs)) ... group应该告诉编译器列表只是中间的:

{-# OPTIONS_GHC -O2 #-}
module GroupCheck where
import Data.List
import Data.Maybe

implement1 :: Integral t=> t -> [(t,Int)]                    -- IMPLEMENTATION 1
implement1  = map (\xs-> (head xs,length xs)).factorGroups where
  tryDiv (d,n)
    | n `mod` d == 0 = (d,n `div` d)
    | n == 1 = (1,1) -- hack
    | otherwise = (d+1,n)
  divTrials n = takeWhile (/=(1,1)) $ (2,n): map tryDiv (divTrials n)
  factorGroups = filter (not.null).map tail.group.map fst.divTrials

implement2 :: Show t => Integral t => t -> [(t,Int)]         -- IMPLEMENTATION 2
implement2 num = keep2 $ tail $ go (1,0,1,num) where
  range d n = [d+1..n]
  nextd d n = fromMaybe n $ find ((0==).(n`mod`)) (range d n)
  update (d,e,de,n)
    | n `mod` d == 0 = update (d,e+1,de*d,n`div`d)
    | otherwise      = (d,e,de,n)
  go (d,e,de,1) = [(d,e,de,1)]
  go (d,e,de,n) = (d,e,de,n) : go (update (nextd d n,0,1,n))
  keep2 = map (\(d,e,_,_)->(d,e))

main :: IO ()
main = do
  let n = 293872
  let ans1 = implement1 n 
  let ans2 = implement2 n
  print ans1
  print ans2

分析告诉我们 tryDiv和 divTrials一起吃掉整个执行时间的 >99%:

> stack ghc -- -main-is GroupCheck.main -prof -fprof-auto -rtsopts GroupCheck 
> ./GroupCheck +RTS -p >/dev/null && cat GroupCheck.prof


           GroupCheck +RTS -p -RTS

        total time  =       18.34 secs   (18338 ticks @ 1000 us, 1 processor)
        total alloc = 17,561,404,568 bytes  (excludes profiling overheads)

COST CENTRE          MODULE     SRC                          %time %alloc

implement1.divTrials GroupCheck GroupCheck.hs:12:3-69         52.6   69.2
implement1.tryDiv    GroupCheck GroupCheck.hs:(8,3)-(11,25)   47.2   30.8

问题 1.5:那么..这些函数有什么不好的地方？还有，

问题 2:在更一般的情况下，必须聚合来自非递减序列的相同元素的连续 block ，我们是否应该使用庞大的 implement2如果我们想要速度呢？ (同样，忽略特定领域的优化。)

还是我完全错过了一些明显的东西？谢谢!

Answer 1

为了建立基线，我在稍大的起始数字上运行了您的程序(这样 time 就不会打印出 0.00s)。我选择 n = 2938722345623 没有特别的原因。以下是开始调整之前的时间安排:

ans1: 和infinity没有区别(我写完了整个答案，还在跑，一共大概26分钟)
ans2:2.78s

首先要尝试调整这一行:

divTrials n = takeWhile (/=(1,1)) $ (2,n): map tryDiv (divTrials n)

这看起来是一个很自然的定义，但事实证明 GHC 从不内存函数调用。因此，如果您想创建一个根据自身递归定义的列表，则不得在递归中进行函数调用。方法如下:

divTrials n = xs where xs = takeWhile (/=(1,1)) $ (2,n): map tryDiv xs

仅此一项更改便可将时间缩短至 7.85 秒。仍然相差约 3 倍，但好得多。

不太明显的问题在于:

factorGroups = filter (not.null).map tail.group.map fst.divTrials

将 group 放得太早会破坏融合，导致中间列表实际上被具体化。这意味着分配和释放大量的 cons 单元和元组。这是一个具有相同精神的实现，但在 group 之前做了更多工作:

  tryDiv d n
    | n `mod` d == 0 = d : tryDiv d (n `div` d)
    | n == 1 = []
    | otherwise = tryDiv (d+1) n
  factorGroups = group . tryDiv 2

这样一来，我们就降到了 2.65 秒——比 ans2 稍微快一点，不过我只对每个测试进行了一次测试，所以很可能只是测量噪声。