4

問題を解いている間、私は数の約数を計算しなければなりませんでした。特定の数値に対してすべての約数 > 1 を生成する 2 つの実装があります。

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

2 つ目は 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..])

最初の実装の方が高速であることがわかりました (返されたリスト全体を出力したので、怠惰のために結果のどの部分も評価されずに残りません)。2 つの実装では異なる順序の除数が生成されますが、それは私にとっては問題ではありません。(実際、k が完全平方の場合、2 番目の実装では平方根が 2 回出力されますが、これも問題ではありません)。

一般に、このような再帰的な実装は Haskell の方が高速ですか? また、これらのコードのいずれかを高速化するための指針をいただければ幸いです。ありがとう！

編集：

これら2つの実装のパフォーマンスを比較するために使用しているコードは次のとおりです: 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
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のに由来します。これは、リストモナドの場合、各メンバーリストから1つが選択した要素のすべての可能な組み合わせのリストを作成するため、、、および/または無限引数リストの場合はもちろんです。sequencesequence :: Monad m => [m a] -> m [a]m ~ []sequence_lists = foldr (\xs rs -> [x:r | x <- xs, r <- rs]) [[]]length . sequence_lists === product . map lengthlength . 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 コンパイラがリスト融合の最適化を採用するためです。これは、代わりに、リスト ジェネレーターと「リスト トランスフォーマー」が 1 つの大きなジェネレーターに融合される可能性があることを意味します。

ただし、 を使用する場合は$!、基本的に「次のステップを実行する前に、このリストの最初のコンスを作成してください」とコンパイラに指示します。これは、GHC が少なくとも 1 つの中間リスト要素を計算することを強制されることを意味し、融合最適化全体を完全に無効にします。

したがって、2 番目のアルゴリズムは、構築および破棄する必要がある中間リストを生成するため、処理が遅くなります。一方、再帰アルゴリズムはただ 1 つのリストをただちに生成します。

于 2012-08-21T10:19:40.883 に答える