4

在解决问题时，我必须计算一个数字的除数。我有两个实现可以为给定数字生成所有除数 > 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

这是我的计时测量：

使用严格评估的除数 ($!)

$ 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

使用带有惰性求值 ($) 的除数 2：

$ 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
4

2 回答 2

5

既然你问了，为了让它更快，应该使用不同的算法。简单直接的是首先找到一个素数分解，然后以某种方式从中构造除数。

试除法的标准素数分解是：

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]for list monadm ~ []构造了由一个从每个成员列表中选择的元素的所有可能组合的列表sequence_lists = foldr (\xs rs -> [x:r | x <- xs, r <- rs]) [[]]，因此length . sequence_lists === product . map length, and or courselength . 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  -}
于 2012-08-21T10:05:52.667 回答
5

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

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

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

于 2012-08-21T10:19:40.883 回答