4

今日、私は高階関数の書き方がわからないという考えを持っていました。私はいくつかのまばらで怠惰な無限のシーケンスを持っています、そして私は与えられた数がこれらの怠惰なシーケンスのいずれかにあるかどうかをチェックできる抽象化を作成したいと思います。パフォーマンスを向上させるために、スパースシーケンスの値をハッシュマップ（またはセット）にプッシュし、必要に応じてハッシュマップの値の数を動的に増やしたいと思いました。怠惰なシーケンスが少ないため、自動メモ化はここでは答えではありません。

おそらくコードは最も理解しやすいので、これが私がこれまでに持っているものです。述語がクローズドオーバーハッシュマップを使用するように次のコードを変更するにはどうすればよいですか？ただし、必要に応じてハッシュマップのサイズを増やし、新しいハッシュマップを使用するように自身を再定義しますか？

(defn make-lazy-predicate [coll]
  "Returns a predicate that returns true or false if a number is in
  coll. Coll must be an ordered, increasing lazy seq of numbers."
  (let [in-lazy-list? (fn [n coll top cache]
                        (if (> top n)
                          (not (nil? (cache n)))
                          (recur n (next coll) (first coll) 
                                 (conj cache (first coll)))]
    (fn [n] (in-lazy-list? n coll (first coll) (sorted-set)))))

(def my-lazy-list (iterate #(+ % 100) 1))

(let [in-my-list? (make-lazy-predicate my-lazy-list)]
  (doall (filter in-my-list? (range 10000))))

命令型に戻らずにこの問題を解決するにはどうすればよいですか？

4

2 に答える 2

2

これは、Adam のソリューションのスレッドセーフな変形です。

(defn make-lazy-predicate
  [coll]
  (let [state        (atom {:mem #{} :unknown coll})
        update-state (fn [{:keys [mem unknown] :as state} item]
                       (let [[just-checked remainder]
                             (split-with #(<= % item) unknown)]
                         (if (seq just-checked)
                           (-> state
                             (assoc :mem (apply conj mem just-checked))
                             (assoc :unknown remainder))
                           state)))]
    (fn [item]
      (get-in (if (< item (first (:unknown @state)))
                @state
                (swap! state update-state item))
              [:mem item]))))

ref の使用を検討することもできますが、述語検索よりも、囲んでいるトランザクションによってロールバックされる可能性があります。これは、あなたが望むものかもしれませんし、そうでないかもしれません。

于 2010-07-19T07:26:06.640 に答える
1

この機能は、コアのメモ化機能がどのように機能するかという考えに基づいています。遅延リストから既に消費された数値のみがセットにキャッシュされます。手動で検索を行う代わりに、組み込みの take-while を使用します。

(defn make-lazy-predicate [coll]
  (let [mem (atom #{})
        unknown (atom coll)]
    (fn [item]
      (if (< item (first @unknown))
        (@mem item)
        (let [just-checked (take-while #(>= item %) @unknown)]
          (swap! mem #(apply conj % just-checked))
          (swap! unknown #(drop (count just-checked) %))
          (= item (last just-checked)))))))
于 2010-07-18T21:39:17.443 に答える