两个简单的代码可生成数字的除数。为什么递归速度更快？

Question

解决问题时，我必须计算数字的除数。我有两个实现，对于给定的数字，所有除数均大于1。

第一种是使用简单的递归：

divisors :: Int64 -> [Int64]
divisors k = divisors' 2 k
  where
    divisors' n k | n*n > k = [k]
                  | n*n == k = [n, k]
                  | k `mod` n == 0 = (n:(k `div` n):result)
                  | otherwise = result
      where result = divisors' (n+1) k

第二个使用Prelude中的列表处理功能：

divisors2 :: Int64 -> [Int64]
divisors2 k = k : (concatMap (\x -> [x, k `div` x]) $!
                  filter (\x -> k `mod` x == 0) $! 
                  takeWhile (\x -> x*x <= k) [2..])

我发现第一个实现更快（我打印了返回的整个列表，因此由于懒惰，结果的任何部分都不会被评估）。这两个实现产生不同顺序的除数，但这对我来说不是问题。（实际上，如果k是一个完美的平方，则在第二个实现中平方根被输出两次-再次不是问题）。

通常，Haskell中的此类递归实现更快吗？同样，我希望任何使这些代码更快的指针。谢谢！

编辑：

这是我用来比较这两种实现的性能的代码：https : //gist.github.com/3414372

这是我的计时测量：

严格评估使用divisor2（$！）

$ ghc --make -O2 div.hs 
[1 of 1] Compiling Main             ( div.hs, div.o )
Linking div ...
$ time ./div > /tmp/out1

real    0m7.651s
user    0m7.604s
sys 0m0.012s

将divisors2与惰性评估（$）结合使用：

$ ghc --make -O2 div.hs 
[1 of 1] Compiling Main             ( div.hs, div.o )
Linking div ...
$ time ./div > /tmp/out1

real    0m7.461s
user    0m7.444s
sys 0m0.012s

使用函数除数

$ ghc --make -O2 div.hs 
[1 of 1] Compiling Main             ( div.hs, div.o )
Linking div ...
$ time ./div > /tmp/out1

real    0m7.058s
user    0m7.036s
sys 0m0.020s

Answer 1

如您所愿，为了使其更快，应使用其他算法。简单而直接的方法是首先找到素数分解，然后以某种方式构造除数。

按试验划分的标准素因分解为：

factorize :: Integral a => a -> [a]
factorize n = go n (2:[3,5..])    -- or: `go n primes`
   where
     go n ds@(d:t)
        | d*d > n    = [n]
        | r == 0     =  d : go q ds
        | otherwise  =      go n t
            where  (q,r) = quotRem n d

-- factorize 12348  ==>  [2,2,3,3,7,7,7]

可以将相等的素因子分组并计数：

import Data.List (group)

primePowers :: Integral a => a -> [(a, Int)]
primePowers n = [(head x, length x) | x <- group $ factorize n]
-- primePowers = map (head &&& length) . group . factorize

-- primePowers 12348  ==>  [(2,2),(3,2),(7,3)]

除数通常是按以下顺序构造的：

divisors :: Integral a => a -> [a]
divisors n = map product $ sequence 
                    [take (k+1) $ iterate (p*) 1 | (p,k) <- primePowers n]

因此，我们有

numDivisors :: Integral a => a -> Int
numDivisors n = product  [ k+1                   | (_,k) <- primePowers n]

这product来自sequence上面定义中的，因为sequence :: Monad m => [m a] -> m [a]对于列表monad而言，它m ~ []构造了一个列表，其中包含从每个成员列表中选择一个的所有可能元素组合的列表sequence_lists = foldr (\xs rs -> [x:r | x <- xs, r <- rs]) [[]]，从而对length . sequence_lists === product . map length和或length . take n === n表示无穷参数列表。

也可以按顺序生成：

ordDivisors :: Integral a => a -> [a]
ordDivisors n = foldr (\(p,k)-> foldi merge [] . take (k+1) . iterate (map (p*)))
                      [1] $ reverse $ primePowers n

foldi :: (a -> a -> a) -> a -> [a] -> a
foldi f z (x:xs) = f x (foldi f z (pairs xs))  where
         pairs (x:y:xs) = f x y:pairs xs
         pairs xs       = xs
foldi f z []     = z

merge :: Ord a => [a] -> [a] -> [a]
merge (x:xs) (y:ys) = case (compare y x) of 
           LT -> y : merge (x:xs)  ys
           _  -> x : merge  xs  (y:ys)
merge  xs     []    = xs
merge  []     ys    = ys

{- ordDivisors 12348  ==>  
[1,2,3,4,6,7,9,12,14,18,21,28,36,42,49,63,84,98,126,147,196,252,294,343,441,588,
686,882,1029,1372,1764,2058,3087,4116,6174,12348] -}

这个定义也很有用，即它立即开始产生除数，而没有明显的延迟：

{- take 20 $ ordDivisors $ product $ concat $ replicate 5 $ take 11 primes
==> [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20]
(0.00 secs, 525068 bytes)

numDivisors $ product $ concat $ replicate 5 $ take 11 primes
==> 362797056  -}

Answer 2

递归版本通常并不比基于列表的版本快。这是因为当计算遵循某种模式时，GHC 编译器会采用列表融合优化。这意味着列表生成器和“列表转换器”可能会融合成一个大生成器。

但是，当您使用 时$!，您基本上告诉编译器“在执行下一步之前请生成此列表的第一个缺点。” 这意味着 GHC 被迫至少计算一个中间列表元素，从而完全禁用整个融合优化。

因此，第二种算法速度较慢，因为您生成必须构造和销毁的中间列表，而递归算法只是立即生成单个列表。