3

我目前有以下函数来获取整数的除数：

-- All divisors of a number
divisors :: Integer -> [Integer]
divisors 1 = [1]
divisors n = firstHalf ++ secondHalf
    where firstHalf = filter (divides n) (candidates n)
          secondHalf = filter (\d -> n `div` d /= d) (map (n `div`) (reverse firstHalf))
          candidates n = takeWhile (\d -> d * d <= n) [1..n]

我最终添加了filterto，secondHalf因为除数在n素数的平方时重复。这似乎是解决此问题的一种非常低效的方法。

所以我有两个问题：如何衡量这是否真的是我算法的瓶颈？n如果是的话，当素数的平方是多少时，我该如何寻找一种更好的方法来避免重复？

4

2 回答 2

2

要确定瓶颈在哪里，请将三个辅助定义（firstHalf、secondHalf、candidate）放在顶层，并使用探查器运行您的代码：ghc -prof --make divisors.hs ./divisors 100 +RTS -p -RTS

另外，您知道最大的候选者是sqrt n，所以不要做那么多乘法d*d，只需考虑[1..floor (sqrt n)]

要获得更好的算法，您应该阅读数学书，因为这不是与 Haskell 相关的问题……您可以考虑的事情：如果“a 除数 b”，那么对于 a 的所有除数 d，d 也除以 b。如果给定的 d 除以 b，您将需要使用记忆化或动态编程来避免多次检查（例如，如果 15 和 27 除以 b，那么您只需在数学上检查一次 3 除以 b。其他时候，您看看 3 是否在你的 b) 的除数表中。

于 2012-09-06T02:28:26.320 回答
1

您无需测试反转后半部分的所有元素。你知道如果平方根存在，它就是那里的头元素：

          secondHalf = let (r:ds) = [n `div` d | d <- reverse firstHalf]
                       in [r | n `div` r /= r] ++ ds

这假设n是积极的。

以不同方式处理数字的 sqrt 的一种更简单的方法是单独处理它：

divs n = 
  let 
    r = floor $ sqrt $ fromIntegral n 
    (a,b) = unzip $ (1,n) : [(d, q) | d<-[2..r-1], let (q,r)=quotRem n d, r==0]
  in
    if r*r==n
      then a ++ r : reverse b
      else a ++ reverse b

这样我们就可以免费获得下半场，作为制作上半场的一部分。

但这几乎不会成为您应用程序的瓶颈，因为算法本身效率低下。从一个数的素数分解中生成除数通常要快得多。通过试除法进行素数分解可以更快，因为我们在找到每个除数时对其进行除法，从而减少被分解的数量，从而减少尝试的除数的数量（直到减少的数字的平方根）。例如，在因式分解过程中12348 = 2*2*3*3*7*7*7没有7尝试上述因子，而在divs 12348数字 12348 中除以从2到的所有数字110：

factorize n = go n (2:[3,5..])    -- or:  (go n primes)  where
   where                          --  primes = 2 :
     go n ds@(d:t)                --   filter (null.tail.factorize) [3,5..]
        | d*d > n    = [n]
        | r == 0     =  d : go q ds
        | otherwise  =      go n t
            where  (q,r) = quotRem n d
于 2012-09-06T10:54:54.670 回答