ツリー検索の保存実行状態

Question

私は木を持って、リストとして表さ

 A 
    /\ 
    B C 
    /\ \ 
D E F 

、

(A (B (D) (E)) (C (F))) 

それは実際には非常に大きな木が私がやりたいものを検索を開始されています100ミリ秒の状態を保存して戻って家を守ってからもう一度電話をかけて、途中で中断したところで私が探しているものが見つからない場合は続行してください。基本的に私が取り組んでいるシミュレーションでは、検索を完了するのに十分な時間が与えられていません。私はどのようにこれを達成するためのアイデアやテクニックを探していますか？ （Clojure、Java）

Answer 1

スレッドが最も簡単な解決策になりそうですが、スレッド1つで自分で管理することはあまり難しくありません。あなたに100msしか与えない "シミュレーション"環境では、新しいスレッドを許可しないことが多いので、これは別の方法です。

基本的な考え方は、タスクを終了するために実行する必要がある作業を表すクロージャを作成し、終了する時間がない場合は結果の代わりにその作業を戻すことです。ここにスケッチがあります：それは一連の数字を追加し、100msごとではなく10回の操作ごとに中断されます。

(let [timer (atom 9)] 
    (defn keep-going? [] 
    (not= 0 (swap! timer #(mod (inc %) 10))))) 

(defn saving-addition [sum xs] 
    (if-let [[x & more] (seq xs)] 
    (let [next-thunk (fn [] (saving-addition (+ x sum) more))] 
     (if (keep-going?) 
     (next-thunk) 
     next-thunk)) 
    sum)) 

(defn monitor [xs] 
    (loop [thunk (saving-addition 0 xs)] 
    (if (fn? thunk) 
     (do 
     (println "Saving execution state") 
     (recur (thunk))) 
     thunk))) 

user> (monitor (range 25)) 
Saving execution state 
Saving execution state 
Saving execution state 
300 

編集：Clojureにはテールコールの最適化がないため、サンクを作成してからスタックを使用します。割り込みが必要となる前に、数千ステップ以上を実行する可能性がある場合は、スタックオーバーフローが発生します。唯一の現実的な解決策は、あなたが複数のそのような「懸濁」関数を記述しなければならない場合、マクロでアウトこの抽象おそらく可能性

(defn saving-addition [sum xs] 
    (if-let [[x & more] (seq xs)] 
    (let [sum (+ x sum)] 
     (if (keep-going?) 
     (recur sum more) 
     #(saving-addition sum more))) 
    sum)) 

のように、recurの両方にと継続中サンクのボディを複製することです。行うには

Answer 2

スレッドのオーバーヘッドに気にしない場合は、少し作業をしてから随時降伏するスレッドに検索を入れてください。

スレッドの利点は、プログラムで状態を保存する必要がないことです。システムがあなたのためにそれを行います。

検索の結果は非同期になり、何らかの理由で取得する必要があるため、これを支払う必要があります。また、100msタイマーを設定する必要があるかもしれません。多くのコード。 :)

Answer 3

最善のことは、あなたが選択することができ、これらの点で、あなたは簡単に状態を保存し、後で再開することができますポイント（あなたが簡単に最高のポイントを見つけるために、関数、再帰を作ってみることができます）

を作ることです状態を保存する、または続ける