47

私はHaskellでUCTアルゴリズムの実装に取り​​組んでいますが、これにはかなりの量のデータジャグリングが必要です。詳細に立ち入ることなく、これはシミュレーションアルゴリズムであり、各「ステップ」で、検索ツリーのリーフノードがいくつかの統計プロパティに基づいて選択され、そのリーフに新しい子ノードが構築され、それに対応する統計情報が表示されます。新しいリーフとそのすべての祖先が更新されます。

そのすべてのジャグリングを考えると、私は検索ツリー全体を岡崎のような不変のデータ構造にする方法を理解するのに十分なほど鋭敏ではありません。代わりに、私はSTモナドを少しいじって、可変STRefのsで構成される構造を作成してきました。不自然な例（UCTとは無関係）：

import Control.Monad
import Control.Monad.ST
import Data.STRef

data STRefPair s a b = STRefPair { left :: STRef s a, right :: STRef s b }

mkStRefPair :: a -> b -> ST s (STRefPair s a b)
mkStRefPair a b = do
    a' <- newSTRef a
    b' <- newSTRef b
    return $ STRefPair a' b'

derp :: (Num a, Num b) => STRefPair s a b -> ST s ()
derp p = do
    modifySTRef (left p) (\x -> x + 1)
    modifySTRef (right p) (\x -> x - 1)

herp :: (Num a, Num b) => (a, b)
herp = runST $ do
    p <- mkStRefPair 0 0
    replicateM_ 10 $ derp p
    a <- readSTRef $ left p
    b <- readSTRef $ right p
    return (a, b)

main = print herp -- should print (10, -10)

明らかに、この特定の例は、を使用せずに作成する方がはるかに簡単ですSTが、うまくいけば、これをどこに使用するかが明確になります...この種のスタイルをUCTのユースケースに適用する場合、それは間違っていますか？

数年前に誰かがここで同様の質問をしましたが、私の質問は少し違うと思います...必要に応じてモナドを使用して可変状態をカプセル化することに問題はありませんが、それが「適切な場合」の句です。ゲッターとセッターを備えたオブジェクトがたくさんあるオブジェクト指向の考え方に時期尚早に戻ってしまうのではないかと心配しています。正確には慣用的なHaskellではありません...

一方、それがいくつかの問題の合理的なコーディングスタイルである場合、私の質問は次のようになると思います：この種のコードを読みやすく保守しやすくするためのよく知られた方法はありますか？私はすべての明示的な読み取りと書き込みにうんざりしていて、特にモナドSTRef内の私のベースの構造からST外の同形であるが不変の構造に変換する必要があることによってうんざりしています。

4

5 に答える 5

42

私はSTをあまり使用しませんが、それが最善の解決策である場合もあります。これは多くのシナリオで発生する可能性があります。

  • 問題を解決するためのよく知られた効率的な方法はすでにあります。クイックソートはこの完璧な例です。速度とインプレース動作で知られていますが、純粋なコードではうまく模倣できません。
  • 厳格な時間と空間の境界が必要です。特に遅延評価の場合（そしてHaskellは遅延評価があるかどうかさえ指定せず、厳密ではないというだけです）、プログラムの動作は非常に予測できない可能性があります。メモリリークがあるかどうかは、特定の最適化が有効になっているかどうかによって異なります。これは、変数の固定セット（通常）と定義された評価順序を持つ命令型コードとは大きく異なります。
  • 締め切りがあります。ほとんどの場合、純粋なスタイルの方がより適切でクリーンなコードですが、命令型の記述に慣れていて、すぐにコードが必要な場合は、命令型から始めて後で機能に移行するのが完全に合理的な選択です。

ST（および他のモナド）を使用するときは、次の一般的なガイドラインに従おうとします。

  • 頻繁に適用スタイルを使用します。これにより、コードが読みやすくなり、不変バージョンに切り替えた場合でも、変換がはるかに簡単になります。それだけでなく、Applicativeスタイルははるかにコンパクトです。
  • STだけを使用しないでください。STのみでプログラムする場合、結果は巨大なCプログラムよりも良くなることはなく、明示的な読み取りと書き込みのためにさらに悪くなる可能性があります。代わりに、それが適用されるところに純粋なHaskellコードを散在させてください。私はよく、のようなものを使用していることに気づきSTRef s (Map k [v])ます。マップ自体は変更されていますが、手間のかかる作業の多くは純粋に行われます。
  • 必要がない場合は、ライブラリを再作成しないでください。IO用に記述された多くのコードは、クリーンに、そしてかなり機械的に、STに変換できます。Data.HashTableで、すべてのIORefsをSTRefsに、IOsをSTsに置き換えることは、手動でコーディングされたハッシュテーブルの実装を作成するよりもはるかに簡単で、おそらく高速でした。

最後にもう1つ注意してください。明示的な読み取りと書き込みで問題が発生した場合は、それを回避する方法があります。

于 2011-11-01T00:52:58.967 に答える
11

突然変異を利用するアルゴリズムとそうでないアルゴリズムは異なるアルゴリズムです。前者から後者への翻訳を維持するという単純な境界がある場合もあれば、難しいものもあれば、複雑さの境界を保持しないものだけが存在する場合もあります。

論文をざっと見てみると、突然変異を本質的に利用しているとは思わないことがわかります。したがって、潜在的に本当に気の利いた怠惰な機能アルゴリズムを開発できると思います。しかし、それは説明されているものとは異なりますが、関連するアルゴリズムになります。

以下に、そのようなアプローチの1つを説明します。必ずしも最良または最も賢いわけではありませんが、非常に簡単です。

これがセットアップですa私はそれを理解しています-A）分岐ツリーが構築されますB）ペイオフはリーフからルートにプッシュバックされ、任意のステップで最良の選択を示します。しかし、これは費用がかかるため、代わりに、ツリーの一部のみが非決定的な方法で葉まで探索されます。さらに、ツリーをさらに探索するたびに、以前の探索で学んだことによって決定されます。

そこで、「ステージワイズ」ツリーを記述するコードを作成します。次に、部分的な報酬の見積もりとともに部分的に探索されたツリーを定義するための別のデータ構造があります。次にrandseed -> ptree -> ptree、ランダムシードと部分的に探索されたツリーが与えられた場合の関数があり、ツリーのさらなる探索に着手し、ptree構造を更新します。次に、空のシードptreeに対してこの関数を繰り返すだけで、ptree内のますます多くのサンプルスペースのリストを取得できます。次に、指定されたカットオフ条件が満たされるまで、このリストをたどることができます。

これで、すべてがブレンドされる1つのアルゴリズムから、3つの異なるステップに移行しました。1）状態ツリー全体を遅延的に構築し、2）構造のサンプリングを使用して部分的な探索を更新し、3）いつ終了するかを決定します。十分なサンプルを収集しました。

于 2011-10-25T17:43:35.367 に答える
9

STを使用することが適切であるかどうかを判断するのは非常に難しい場合があります。STを使用する場合と使用しない場合をお勧めします（必ずしもこの順序である必要はありません）。非STバージョンはシンプルにしてください。STの使用は最適化と見なされるべきであり、必要であることがわかるまではそれを実行したくありません。

于 2011-10-24T20:58:50.890 に答える
2

Haskellのコードが読めないことを認めなければなりません。ただし、ツリーの変更にSTを使用する場合は、次の理由により、多くを失うことなく、これを不変のツリーに置き換えることができます。

可変および不変ツリーの同じ複雑さ

新しいリーフの上のすべてのノードを変更する必要があります。不変ツリーは、変更されたノードの上のすべてのノードを置き換える必要があります。したがって、どちらの場合も、タッチされたノードは同じであるため、複雑さは何も得られません。

たとえば、Javaオブジェクトの作成はミューテーションよりもコストがかかるため、ミューテーションを使用することで、ここHaskellで少し利益を得ることができるかもしれません。しかし、これは確かにわかりません。しかし、次の点のために、わずかな利益はあなたに多くを買わない。

ツリーの更新はおそらくボトルネックではありません

新しい葉の評価は、おそらくツリーを更新するよりもはるかに費用がかかります。少なくともこれは、コンピューターGoのUCTの場合です。

于 2011-11-18T13:24:08.373 に答える
2

STモナドの使用は、通常（常にではありませんが）最適化として行われます。最適化には、同じ手順を適用します。

  1. それなしでコードを書いてください、
  2. ボトルネックのプロファイルと特定、
  3. ボトルネックを段階的に書き直し、改善/回帰をテストします。

私が知っている他のユースケースは、州のモナドの代替としてです。主な違いは、状態モナドでは保存されるすべてのデータのタイプがトップダウンで指定されるのに対し、STモナドではボトムアップで指定されることです。これが役立つ場合があります。

于 2011-11-25T08:52:14.850 に答える