asynchronous - clojure で先物を短絡する

Question

ブール値に解決される 2 つの先物があります。私は基本的に次のようなことをしたい

(if (or @future1 @future2) 
  ...)

しかし、どちらが先に終了するかという最適化により、それが真であれば、残りの未来が終了するのを待ちません。ただ行く。もちろん、値が false の場合は、残りの未来が終了するまで待ちます。これを行う簡単な方法はありますか？

Answer 1

これはcore.async、新しいwith Clojure threading long running processes and comparison their returnsの質問に対する私の回答で説明されているように、 で可能になりました。その答えは定義しthread-andます; この質問には次のことが必要ですthread-or。

(defn thread-or
  "Call each of the fs on a separate thread. Return logical
  disjunction of the results. Short-circuit (and cancel the calls to
  remaining fs) on first truthy value returned."
  [& fs]
  (let [futs-and-cs
        (doall (for [f fs]
                 (let [c (chan)]
                   [(future (>!! c (f))) c])))]
    (loop [futs-and-cs futs-and-cs]
      (let [[result c] (alts!! (map peek futs-and-cs))]
        (if result
          (do (doseq [fut (map first futs-and-cs)]
                (future-cancel fut))
              result)
          (let [new-futs-and-cs (remove #(identical? (peek %) c)
                                        futs-and-cs)]
            (if (next new-futs-and-cs)
              (recur new-futs-and-cs)
              (<!! (peek (first new-futs-and-cs))))))))))

(常に false) および (常に true) でテストします。

(thread-or (constantly true) (constantly true))
;;= true

(thread-or (constantly true) (constantly false))
;;= true

(thread-or (constantly false) (constantly false))
;;= false

また、短絡が実際に機能することにも注意してください。

;; prints :foo before returning true
(thread-or #(do (Thread/sleep 3000) true)
           #(do (Thread/sleep 1000) (println :foo)))

;; does not print :foo
(thread-or #(do (Thread/sleep 3000) true)
           #(do (Thread/sleep 7000) (println :foo)))

Answer 2

私はこの質問が大好きです。こんなに単純な斬新な質問を見て驚いたのかもしれません。とにかく、よだれはさておき、私はあなたのために働く何かを持っていると思います.

代わりに：

(if (or @future1 @future2)
  ...)

行う：

(if (or (and (realized? future1) @future1)
        (and (realized? future2) @future2))
  ...)

トリックは、それが実現されているかどうかをテストしてから、それが実現されているかどうかを確認することtrueですfalse。

これは、次のようなマクロに一般化できます。

(defmacro future-or [& futures]
  `(or ~@(for [f futures]
          `(and (realized? ~f)
                (deref ~f)))))

そして、次のように使用されます：

(if (future-or future1 future2)
  ...)

一瞬待って。多分私はあなたの問題を間違って理解しています。おそらく、future の 1 つが完了して が返されるまで実行をブロックしたい場合があります。この場合、truethen 節を実行します。それは別の話です。iftrueif

私が思いついた最も簡潔な方法は、まったくきれいではありませんが、恐ろしく長くもありません。

(if (loop []
        (cond (or (and (realized? future1) @future1)
                  (and (realized? future2) @future2)) true
              (and (realized? future1) (realized? future2)
                   (not @future1) (not @future2)) false
              :else (recur)))
    ...)

さて、これはloop次の 2 つのいずれかが起こるまで繰り返しループするために使用されtrueますtrue。またはすべての先物が実現され、それらすべてがfalseである場合、ループは で戻りますfalse。(not ...)式を親の式の最後に置くことが重要(and ...)です。これにより、先物が存在するかどうか、trueまたはfalseすべてが実現されるまでチェックするのに行き詰まることはありません。

この新しいソリューションは、次のように一般化できます。

(defmacro future-or [& futures]
  `(loop []
     (cond (or ~@(for [f futures]
                   `(and (realized? ~f)
                         (deref ~f)))) true
           (and ~@(for [f futures]
                    `(realized? ~f))
                ~@(for [f futures]
                    `(not (deref ~f)))) false
           :else (recur))))

future-or上記の例と同じように使用します。

今、私は最適化についてほとんど何も知りません。しかし、私が知る限り、これは確かに理論的に可能なほど効率的ではありません。なぜなら、特定の未来が実現されると、その価値を何度もテストする必要がないからです。さて、ここに私がタイトルを付けた2つの解決策がありfuture-someます. テストされる先物は、ループの反復ごとに動的に変更される可能性があるため、関数にする必要がありました。someその意味で、この新しいメソッドはではなくに類似していorます。some同様に、先物のコレクションを取るように動作を変更しました (可変数の単一引数とは対照的に、との間のもう 1 つの違いorです)。1つの解決策は二重チェックを行いません（私は思います）：

(defn future-some [futures]
  (if (empty? futures)
    false
    (let [res (reduce (fn [unrealized f]
                        (if (realized? f)
                          (if @f
                            (reduced true)
                            unrealized)
                          (cons f unrealized)))
                      ()
                      futures)]
      (if (true? res)
        true
        (recur res)))))

ここには詳細がたくさんありますが、要点は次のとおりです。テストする先物がない場合は を返しますfalse。future が実現され、さらに への逆参照が行われたtrue場合、反復は中断して を返しtrueます。future が実現されたが を逆参照しないtrue場合、反復は次の項目に進みます。未来が実現されていない場合、次の再帰で使用されるリストに追加されますfuture-some。

もう 1 つの解決策はより簡潔ですが、やや最適ではありません。

(defn future-some [futures]
  (if (empty? futures)
    false
    (let [realized (filter realized? futures)]
      (if (some deref realized)
        true
        (recur (remove (set realized) futures))))))

他のものと似ていますが、最初に実現されたものを除外し、次にテストし、再発する必要がある場合は再度フィルタリングします (今回は逆に、実現されていないものを取得します)。この 2 番目のフィルタリングは非効率的なステップです。

私が提案するすべての解決策の問題は、将来のキャンセルが逆参照時にエラーになることです。これは、逆参照の前に、(not (future-cancelled? ...))すべての単一の式の中に式を配置することで解決できます。(and ...)または、関数の場合、述語を、または気弱なfuture-some人に置き換える必要があります。realized?(some-fn (comp not future-cancelled?) realized?)#(and (not (future-cancelled %)) (realized? %))

繰り返しますが、真剣に、その質問に感謝します。

Answer 3

X ミリ秒ごとに先物をポーリングしたくなく、先物/スレッドまたはそれらが実行している fn の作成を制御できないと仮定すると、解決策は、さらに多くのスレッドを作成し、各スレッドが先物を待機することです。 :

(defn wait-for-any [& futures]
  (let [how-many-left (atom (count futures))
        p (promise)
        wait-and-notify (fn [f]
                         (fn []
                           (if @f
                             (deliver p true)
                             (when (zero? (swap! how-many-left dec))
                               (deliver p false)))))]
    (dorun (map (comp future-call wait-and-notify) futures))
    @p))

 (defn sleep-and-return [what-to-return sleep-time]
  (future
    (Thread/sleep sleep-time)
    what-to-return))


(time (println (wait-for-any
                (sleep-and-return false 1000)
                (sleep-and-return false 2000)
                (sleep-and-return false 3000)
                (sleep-and-return false 4000)
                (sleep-and-return false 5000))))

>>>false
>>>"Elapsed time: 5000.933906 msecs"

(time (println (wait-for-any
                (sleep-and-return false 1000)
                (sleep-and-return true 2900)
                (sleep-and-return true 3000)
                (sleep-and-return false 4000)
                (sleep-and-return false 5000))))
>>>true
>>>"Elapsed time: 2901.309695 msecs"