3

解決したい最適化問題があります。ある種のデータ構造があります。

data Foo =
  { fooA :: Int
  , fooB :: Int
  , fooC :: Int
  , fooD :: Int
  , fooE :: Int
}

および評価関数：

rateFoo :: myFoo -> Int

rateFoo構造体の値を変更して、結果を最適化する必要があります。この特定のケースでは、問題を解決するために反復深化探索を使用することにしました。最適化を最適化するための（無限の）検索ツリーは、別の関数によって作成されます。この関数は、考えられるすべての変更をツリーに再帰的に適用します。

fooTree :: Foo -> Tree

私の検索機能は次のようになります。

optimize :: Int -> Foo -> Foo
optimize threshold foo = undefined

私が始める前に私が持っていた質問はこれです：

ツリーは各ポイントのデータによって生成できるので、現在アルゴリズムで必要とされているツリーの部分のみを生成することは可能ですか？メモリを節約するために、必要に応じてメモリを解放し、ツリーを再生成することは可能ですか（レベルnのリーブを生成できO(n)、nは小さいままですが、ツリー全体をメモリに保持するのに十分な小ささではありません）。

これは私がランタイムから期待できるものですか？ランタイムは式を未評価にすることができますか（評価された式を未評価の式に変換します）？または、これのために私がしなければならない汚いハックは何ですか？

4

2 に答える 2

4

ランタイムは式を評価解除しません。

ただし、必要なものを取得する簡単な方法があります。

木のジッパーのような構造を考えてみましょう。各ノードは、下、上などを表す値とサンクを保持します。次のノードに移動するときは、通常どおりに移動する（前のノードの値を対応するスロットに配置する）か、忘れて（前のノードに評価される式を配置する）ことができます。右スロットのノード）。次に、どのくらいの「履歴」を保持するかを制御できます。

于 2010-09-21T14:56:24.210 に答える
3

これが私のアドバイスです：

  1. 可能な限り最も簡単な方法でアルゴリズムを実装するだけです。
  2. プロフィール。
  3. 必要に応じて、速度またはメモリの使用を最適化します。

私は、GHCが何をするのか、またはガベージコレクションがどのように機能するのかについて推論するのに十分な賢さや経験がないことをすぐに知りました。時には、悲惨なほどメモリ効率が悪いと確信していることは、最初はスムーズに機能します。また、それほど頻繁ではありませんが、単純に見えるものは、厳密性の注釈などで多くの手間をかける必要があります。

ステップ2と3に進むと、プロファイリングと最適化に関するRealWorldHaskellの章が非常に役立ちます。

たとえば、これはIDDFSの非常に単純な実装であり、f子を展開pし、検索述語でありx、開始点です。

search :: (a -> [a]) -> (a -> Bool) -> a -> Bool
search f p x = any (\d -> searchTo f p d x) [1..]
  where
    searchTo f p d x
      | d == 0    = False
      | p x       = True
      | otherwise = any (searchTo f p $ d - 1) (f x)

asで検索してテストし"abbaaaaaacccaaaaabbaaccc"ました。それは適度に速いようで、メモリをほとんど必要としません（深さに比例すると思います）。最初にこのようなことを試してから、それが十分でない場合は、より複雑なデータ構造に移動してみませんか？children x = [x ++ "a", x ++ "bb", x ++ "ccc"]f

于 2010-09-21T12:43:35.097 に答える