[解決済み] Haskellでメモ化？

質問

Haskellで以下の関数を効率的に解く方法について、大きな数字に対する指針があれば教えてください。 (n > 108)

f(n) = max(n, f(n/2) + f(n/3) + f(n/4))

Haskellでフィボナッチを解くためにメモ化する例を見たことがあります。 この場合、すべてのフィボナッチ数を計算する必要があります。 しかし、この場合、与えられたnに対して、必要なのは は、ごくわずかな中間結果を計算するのみです。

ありがとうございます。

解決方法は？

サブリニアタイムでインデックスを作成できる構造にすることで、非常に効率的に行うことができるのです。

その前に

{-# LANGUAGE BangPatterns #-}

import Data.Function (fix)

を定義してみましょう。 f しかし、それ自体を直接呼び出すのではなく、「オープンリカージョン」を使用するようにします。

f :: (Int -> Int) -> Int -> Int
f mf 0 = 0
f mf n = max n $ mf (n `div` 2) +
                 mf (n `div` 3) +
                 mf (n `div` 4)

メモされていない f を使うことで fix f

これにより f の小さな値で、あなたが意味することを実行します。 f を呼び出すことで、例えば fix f 123 = 144

定義することで、これをメモすることができる。

f_list :: [Int]
f_list = map (f faster_f) [0..]

faster_f :: Int -> Int
faster_f n = f_list !! n

この方法は、十分にうまく機能し、これまでかかっていた O(n^3) の時間を、中間結果をメモするようなものに変更しました。

しかし、メモされた答えを見つけるためにインデックスを作成するだけでも、まだ線形時間がかかります。 mf . というような結果が出るということです。

*Main Data.List> faster_f 123801
248604

は許容範囲内ですが、結果はそれ以上のスケールにはなりません。もっといいものができるはずです。

まず、無限木を定義しよう。

data Tree a = Tree (Tree a) a (Tree a)
instance Functor Tree where
    fmap f (Tree l m r) = Tree (fmap f l) (f m) (fmap f r)

そして、インデックスを作成する方法を定義して、インデックスを持つノードを見つけることができるようにします。 n で O(log n) の時間を短縮することができます。

index :: Tree a -> Int -> a
index (Tree _ m _) 0 = m
index (Tree l _ r) n = case (n - 1) `divMod` 2 of
    (q,0) -> index l q
    (q,1) -> index r q

...そして、自然数でいっぱいの木は、インデックスをいじくり回さなくて済むので便利だと思うかもしれません。

nats :: Tree Int
nats = go 0 1
    where
        go !n !s = Tree (go l s') n (go r s')
            where
                l = n + s
                r = l + s
                s' = s * 2

インデックスができるのだから、ツリーをリストに変換すればいい。

toList :: Tree a -> [a]
toList as = map (index as) [0..]

ここまでの作業を確認するために toList nats はあなたに [0..]

今すぐ

f_tree :: Tree Int
f_tree = fmap (f fastest_f) nats

fastest_f :: Int -> Int
fastest_f = index f_tree

は、上記のリストと同様に動作しますが、各ノードを見つけるのに線形時間ではなく、対数時間で追いかけることができます。

その結果、かなり速くなりました。

*Main> fastest_f 12380192300
67652175206

*Main> fastest_f 12793129379123
120695231674999

実際、この方法は非常に高速で、次のように置き換えることができます。 Int で Integer 上記のように、ほとんど瞬時にとんでもなく大きな答えを得ることができます。

*Main> fastest_f' 1230891823091823018203123
93721573993600178112200489

*Main> fastest_f' 12308918230918230182031231231293810923
11097012733777002208302545289166620866358

ツリーベースのメモ化を実装した、すぐに使えるライブラリとしては、以下のものがあります。 メモトライ :

$ stack repl --package MemoTrie

Prelude> import Data.MemoTrie
Prelude Data.MemoTrie> :set -XLambdaCase
Prelude Data.MemoTrie> :{
Prelude Data.MemoTrie| fastest_f' :: Integer -> Integer
Prelude Data.MemoTrie| fastest_f' = memo $ \case
Prelude Data.MemoTrie|   0 -> 0
Prelude Data.MemoTrie|   n -> max n (fastest_f'(n `div` 2) + fastest_f'(n `div` 3) + fastest_f'(n `div` 4))
Prelude Data.MemoTrie| :}
Prelude Data.MemoTrie> fastest_f' 12308918230918230182031231231293810923
11097012733777002208302545289166620866358