8

私は非常に大きな決定木を持っています。次のように使用されます。

-- once per application start
t :: Tree
t = buildDecisionTree
-- done several times
makeDecision :: Something -> Decision
makeDecision something = search t something

この決定木は大きすぎてメモリに収まりません。しかし、遅延評価のおかげで、部分的にしか評価されません。

問題は、考えられるすべての決定が試行され、ツリー全体が評価されるシナリオがあることです。これは終了しませんが、メモリオーバーフローを引き起こすこともありません。さらに、このプロセスが中止されても、巨大なサブツリーがすでに評価されているため、メモリ使用量は減少しません。

解決策は、呼び出されるたびにツリーを再評価することmakeDecisionですが、これにより、キャッシュ決定の利点が失われ、大幅に速度が低下しmakeDecisionます。

中流に行きたいです。特に、私のアプリケーションでは、ツリー内の共通パスプレフィックスを使用して連続した決定を行うことが非常に一般的です。したがって、最後に使用されたパスをキャッシュしたいのですが、他のパスを削除して、次に使用されるときに再評価するようにします。Haskellでこれを行うにはどうすればよいですか？

4

1 に答える 1

6

純粋なhaskellでは不可能です。質問を参照してください。メモリパフォーマンスを向上させるためにサンクを複製できますか？（@shangによって指摘されたように）。ただし、IOを使用してこれを行うことができます。

モジュールの見出しから始めて、このモジュール（unsafePerformIOを使用する）を安全にする必要があるタイプと関数のみをリストします。unsafePerformIOなしでこれを行うことも可能ですが、それはユーザーが自分のコードの多くをIOに保持する必要があることを意味します。

{-# LANGUAGE ExistentialQuantification #-}
module ReEval (ReEval, newReEval, readReEval, resetReEval) where

import Data.IORef
import System.IO.Unsafe

まず、関数と引数を互いに離して、すべての共有を防ぐ方法で値を格納するデータ型を定義し、値が必要な場合にのみ関数を適用します。によって返される値は共有unsharedValue できますが、他の呼び出しの戻り値とは共有できないことに注意してください（関数が重要なことを実行していると仮定します）。

data Unshared a = forall b. Unshared (b -> a) b

unsharedValue :: Unshared a -> a
unsharedValue (Unshared f x) = f x

次に、リセット可能な計算のデータ型を定義します。計算と現在の値を保存する必要があります。後者は、IORefリセットできるようにするために、に格納されます。

data ReEval a = ReEval {
    calculation :: Unshared a,
    currentValue :: IORef a
    }

ReEvalボックスに値をラップするには、関数と引数が必要です。なぜだけではないのa -> ReEval aですか？その場合、パラメータの共有を防ぐ方法がないためです。

newReEval :: (b -> a) -> b -> ReEval a
newReEval f x = unsafePerformIO $ do
    let c = Unshared f x
    ref <- newIORef (unsharedValue c)
    return $ ReEval c ref

読み取りは簡単です。から値を取得するだけですIORef。この使用は安全です。なぜなら、その「コピー」は異なりますが、 unsafePerformIO常にの値を取得するからです。unsharedValue c

readReEval :: ReEval a -> a
readReEval r = unsafePerformIO $ readIORef (currentValue r)

そして最後にリセット。ラップする他の関数よりも安全性が低いためではなく、リセットが実際にいつunsafePerformIO発生するかをユーザーが制御できる最も簡単な方法であるため、IOモナドに残しました。使用する戻り値がないために、メモリがなくなるか、最適化されるまで、すべての呼び出しが遅延するリスクを冒したくありません。resetReEval

resetReEval :: ReEval a -> IO ()
resetReEval r = writeIORef (currentValue r) (unsharedValue (calculation r))

これでモジュールは終了です。コード例は次のとおりです。

import Debug.Trace
import ReEval
main = do
    let func a = trace ("func " ++ show a) negate a
    let l = [ newReEval func n | n <- [1..5] ]
    print (map readReEval l)
    print (map readReEval l)
    mapM_ resetReEval l
    print (map readReEval l)

そしてここであなたはそれが期待したことをするのを見ることができます：

$ runhaskell test.hs 
func 1
func 2
func 3
func 4
func 5
[-1,-2,-3,-4,-5]
[-1,-2,-3,-4,-5]
func 1
func 2
func 3
func 4
func 5
[-1,-2,-3,-4,-5]
于 2013-01-18T16:32:54.643 に答える