21

パラメータを受け取って結果を生成する関数があります。残念ながら、関数が結果を生成するのにかなりの時間がかかります。この関数は同じ入力で頻繁に呼び出されるため、結果をキャッシュできれば便利です。何かのようなもの

let cachedFunction = createCache slowFunction
in (cachedFunction 3.1) + (cachedFunction 4.2) + (cachedFunction 3.1)

私はData.Arrayを調べていましたが、配列は怠惰ですが、ペアのリストで初期化する必要があります（listArrayを使用）-これは実用的ではありません。'key'が'Double'タイプなどの場合、初期化することはできません。理論的にはすべての可能な入力に整数を割り当てることができても、数万の可能な入力があり、実際にはほんの一握りしか使用しません。リストの代わりに関数を使用して、配列（または、少数の結果のみが使用されるため、ハッシュテーブルが望ましい）を初期化する必要があります。

更新：私はメモ化の記事を読んでいますが、私が理解している限り、MemoTrieは私が望むように機能する可能性があります。多分。誰かが「cachedFunction」を作成しようとすることができますか？できれば、2つのDouble引数を取る遅い関数の場合はどうでしょうか。または、代わりに、すべてのメモリを消費しない〜[0.1億]のドメインで1つのInt引数を取りますか？

4

7 に答える 7

20

さて、ありData.HashTableます。ただし、ハッシュテーブルは、不変のデータや参照透過性とうまく連携しない傾向があるため、あまり使用されていないと思います。

値の数が少ない場合は、検索ツリー（などData.Map）にそれらを格納するのがおそらく十分に高速です。のマングリングを我慢できる場合Double、より堅牢な解決策は、次のようなトライのような構造を使用することData.IntMapです。これらのルックアップ時間は主にキーの長さに比例し、コレクションサイズはほぼ一定です。制限が大きすぎる場合Intは、Hackageを調べて、使用するキーのタイプがより柔軟なトライライブラリを見つけることができます。

結果をキャッシュする方法については、通常「メモ化」と呼ばれるものが欲しいと思います。結果をオンデマンドで計算してメモ化したい場合、テクニックの要点は、特定の結果を要求したときに答えを得るのに必要な計算のみを強制するように、すべての可能な結果を​​含むインデックス付きデータ構造を定義することです。あなたが欲しい。一般的な例には通常、リストへのインデックス作成が含まれますが、厳密でないデータ構造にも同じ原則を適用する必要があります。経験則として、非関数値（無限の再帰データ構造を含む）はランタイムによってキャッシュされることがよくありますが、関数の結果はキャッシュされないため、トリックはすべての計算を、ラップしないトップレベルの定義内にラップすることです。引数に依存します。

編集： MemoTrieの例ahoy！

これは、迅速で汚い概念実証です。より良いアプローチが存在する可能性があります。

{-# LANGUAGE TypeFamilies #-}
{-# LANGUAGE TypeOperators #-}
import Data.MemoTrie
import Data.Binary
import Data.ByteString.Lazy hiding (map)

mangle :: Double -> [Int]
mangle = map fromIntegral . unpack . encode

unmangle :: [Int] -> Double
unmangle = decode . pack . map fromIntegral

instance HasTrie Double where
    data Double :->: a = DoubleTrie ([Int] :->: a)
    trie f = DoubleTrie $ trie $ f . unmangle
    untrie (DoubleTrie t) = untrie t . mangle

slow x 
    | x < 1 = 1
    | otherwise = slow (x / 2) + slow (x / 3)

memoSlow :: Double -> Integer
memoSlow = memo slow

MemoTrieパッケージで使用されるGHC拡張機能に注意してください。うまくいけば、それは問題ではありません。それをGHCiにロードし、（10 ^ 6）や（10 ^ 7）のようなものでslowvs.を呼び出してみて、動作を確認してください。memoSlow

これを複数の引数を取る関数に一般化するなど、かなり簡単なはずです。MemoTrieの使用の詳細については、作成者によるこのブログ投稿が役立つ場合があります。

于 2010-02-07T16:32:43.613 に答える
5

メモ化を参照してください

于 2010-02-07T16:20:45.003 に答える
4

GHCのランタイムシステムには、メモ化を明示的にサポートするためのツールがいくつかあります。

残念ながら、メモ化は実際には万能ではないため、さまざまなユーザーのニーズに対応するためにサポートする必要のあるさまざまなアプローチがいくつかあります。

例としていくつかの実装が含まれているため、元の1999年の記事が役立つ場合があります。

ストレージマネージャーの拡張： Simon Peyton Jones、Simon Marlow、およびConalElliottによるHaskellの弱いポインターと安定した名前

于 2010-02-12T20:44:41.797 に答える
3

独自のソリューションを追加しますが、これもかなり遅いようです。最初のパラメーターは、パラメーターの一意の識別子であるInt32を返す関数です。別の方法（たとえば、「id」）で一意に識別したい場合は、H.newの2番目のパラメーターを別のハッシュ関数に変更する必要があります。Data.Mapの使用方法を調べて、より高速な結果が得られるかどうかをテストします。

import qualified Data.HashTable as H
import Data.Int
import System.IO.Unsafe

cache :: (a -> Int32) -> (a -> b) -> (a -> b)
cache ident f = unsafePerformIO $ createfunc
    where 
        createfunc = do
            storage <- H.new (==) id
            return (doit storage)

        doit storage = unsafePerformIO . comp
            where 
                comp x = do
                    look <- H.lookup storage (ident x)

                    case look of
                        Just res -> return res
                        Nothing -> do
                            result <- return (f x)
                            H.insert storage (ident x) result
                            return result
于 2010-02-09T21:09:11.340 に答える
2

遅い関数を高階関数として記述し、関数自体を返すことができます。したがって、slow関数内のすべての前処理と、返された（できれば高速の）関数の各計算で異なる部分を実行できます。例は次のようになります:(SMLコードですが、アイデアは明確である必要があります）

fun computeComplicatedThing (x:float) (y:float) = (* ... some very complicated computation *)
fun computeComplicatedThingFast = computeComplicatedThing 3.14 (* provide x, do computation that needs only x *)
val result1 = computeComplicatedThingFast 2.71 (* provide y, do computation that needs x and y *)
val result2 = computeComplicatedThingFast 2.81
val result3 = computeComplicatedThingFast 2.91
于 2010-02-07T17:04:36.880 に答える
1

私には数万の可能な入力があり、実際にはほんの一握りしか使用していません。リストの代わりに関数を使用して配列を初期化する必要があります。

私は一緒に行きますlistArray (start, end) (map func [start..end])

  • func上記では実際には呼び出されません。Haskellは怠惰で、値が実際に必要になったときに評価されるサンクを作成します。
  • 通常の配列を使用する場合は、常にその値を初期化する必要があります。したがって、これらのサンクを作成するために必要な作業はとにかく必要です。
  • 数万人はそれほど多くはありません。何兆もあるなら、ハッシュテーブルyadayadaを使うことをお勧めします
于 2010-02-07T19:48:37.357 に答える
0

特にhaskellはわかりませんが、既存の回答をハッシュデータ構造（辞書またはハッシュマップと呼ばれる場合があります）に保持するのはどうですか？スロー関数を別の関数でラップして、最初にマップをチェックし、答えが見つからない場合にのみスロー関数を呼び出すことができます。

マップのサイズを特定のサイズに制限し、それに達すると、最も使用頻度の低いエントリを破棄することで、それを凝ったものにすることができます。このためには、キーからタイムスタンプへのマッピングのマップを追加で保持する必要があります。

于 2010-02-07T16:36:20.830 に答える