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]

が素数の 2 乗であるときに除数が繰り返されたため、filter最終的に を追加しました。これは、この問題を解決するには非常に非効率的な方法のようです。secondHalfn

質問が 2 つあります。これが本当にアルゴリズムのボトルネックかどうかを測定するにはどうすればよいでしょうか。nもしそうなら、 が素数の 2 乗であるときに、繰り返しを避けるためのより良い方法を見つけるにはどうすればよいでしょうか?

4

2 に答える 2

2

ボトルネックがどこにあるかを測定するには、3 つの補助的な定義 (firstHalf、secondHalf、候補) を最上位に配置し、プロファイラーをオンにしてコードを実行します。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 を割り切ることを数学的に 1 回だけチェックする必要があります。それ以外の場合は、 b) の除数の表に 3 があるかどうかを確認してください。

于 2012-09-06T02:28:26.320 に答える
1

反転した後半のすべての要素をテストする必要はありません。平方根が存在する場合、それが head 要素であることがわかります。

          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上記の因数は試されませんが、数値 12348 は から までのすべての数値で除算されます。7divs 123482110

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 に答える