2

大きな数の二項係数を大量に計算する必要のある場面において、以下の様に二項係数を計算する関数binomを定義しようと思い、階乗やその逆数を保持するリストfactList,factInvListを定義しました。

しかし、binomが呼び出される場面において、遅延評価のため、毎回このリストが計算されているように思われます。

リストを一回計算したらそれを使いまわすような仕様にするにはどの様に改善すればいいのでしょうか。

法を1000000007として計算しています。

base :: Integer
base = 1000000007

modBase :: Integer -> Integer
modBase n = n `mod` base

timesOnBase :: Integer -> Integer -> Integer
timesOnBase a b = modBase $ a * b

power :: Integer -> Integer -> Integer
power x n
   | n == 0         = 1
   | n `mod` 2 == 0 = power (timesOnBase x x) (n `div` 2)
   | otherwise      = timesOnBase x $ power x $ n-1

inv :: Integer -> Integer
inv n = power n $ base - 2

factList :: [Integer]
factList = makeFactList base
   where
      makeFactList :: Integer -> [Integer]
      makeFactList n = scanl (timesOnBase) 1 [1..n]

factInvList :: [Integer]
factInvList = map inv factList

--binom n m = nCm
binom :: Int -> Int -> Integer
binom n m = (factList !! n) `timesOnBase` (factInvList !! m) `timesOnBase` (factInvList !! (n-m))

2
  • 3
    Debug.Trace を入れて実行してみると、factList は memoize されている様に見えます。repl.it/repls/ApprehensiveLittleStructure
    – user39889
    2020年2月22日 13:02
  • 2
    「毎回このリストが計算されているように思わ」れたのは何故でしょうか?むしろ(線形時間かかる)リストの走査が計算量に悪影響を与えているということはないでしょうか?
    – letrec
    2020年2月22日 13:45

1 件の回答 1

5

しかし、binomが呼び出される場面において、遅延評価のため、毎回このリストが計算されているように思われます。

@metropolis さんのコメントのとおり、実際にはfactListは必要に応じて一度しか計算されていません。

恐らく実行時間が想定より長くかかることから疑われたのかと思いますが、このコードの実行時間を改善するとしたら私ならリストの代わりにvectorパッケージのVector型を使うでしょう。
リストには一応インデックスでアクセスするための演算子 !! が提供されてますが、インデックス(右辺に指定した整数)が大きくなればなるほど時間がかかってしまうので、今回の用途には適していません。

1
  • 1
    仰る通り長い計算時間の原因が遅延評価にあると思い込んでいました。構成を見直してみます。ありがとうございました。
    – user24965
    2020年2月23日 15:28

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。