10

私はベクトルxとyユニークなアイテムのペアを持っており、それぞれがソートされていることがわかっています。ソート順を維持しながら、2つの交差点が欲しいです。結果は、高速ランダムアクセスのための別のベクトルになるのが理想的です。

以下の世代は、単なる例のためであり、x事前yに分類され、事前に区別されます（実際には時間サンプルです）。

(defn gen-example [c] (-> (repeatedly c #(-> c rand int)) distinct sort vec))

user=> (def x (gen-example 100000)) (count x)
#'user/x
63161
user=> (def y (gen-example 100000)) (count y)
#'user/y
63224

私はClojureがclojure.set/intersectionで動作することができることを知っていますsorted-set。私xとyは同じプロパティ（ソートされた個別の要素）を持っていますが、同じタイプではありません。

質問1：すでに区別されてソートされている場合よりもx、sに変換yするためのより良い/より速い方法はありますか？sorted-set(apply sorted-set x)

user=> (time (def ssx (apply sorted-set x)))
"Elapsed time: 607.642592 msecs"
user=> (time (def ssy (apply sorted-set y)))
"Elapsed time: 617.046022 msecs"

これで交差点を実行する準備ができました

user=> (time (count (clojure.set/intersection ssx ssy)))
"Elapsed time: 355.42534 msecs"
39992

これはやや期待外れのパフォーマンスであり、ざっと見てみると、(source clojure.set/intersection)これらのセットがソートされているという事実に対する特別な扱いは示されていないようです。

質問2：sorted-setsの共通部分を実行するためのより良い/より速い方法はありclojure.set/intersectionますか？

(defn intersect-sorted-vector [x y] 
  (loop [x (seq x) y (seq y) acc []] 
    (if (and x y)
      (let [x1 (first x) 
            y1 (first y)] 
      (cond 
        ( < x1 y1) (recur (next x) y acc) 
        ( > x1 y1) (recur x (next y) acc) 
        :else (recur (next x) (next y) (conj acc x1))))
    acc)))

これはかなり（ほぼ10倍）高速であることがわかります。

user=> (time (count (intersect-sorted-vector x y)))
"Elapsed time: 40.142532 msecs"
39992

しかし、私のコードが過度に手続き的/反復的であると感じずにはいられません。

質問3：Clojureでベクトルのペアを処理するためのより慣用的な方法を誰かが親切に提案できますか？

4

1 に答える 1

8

高速なClojureコードが少し必須に見えることがよくあります。関数型コードは多くの場合エレガントですが、それに伴うパフォーマンスコストが発生します（怠惰、破棄された不変オブジェクトからの余分なGCプレッシャーなど）。

また、セットへの変換は常により高価になります。セットの構築はO(n log n)それ自体が操作ですが、ベクトルがすでにサポートされているという事実を利用して、O(n)時間内に交差操作を実装できます。

あなたのコードはすでにかなり良いですが、あなたができるいくつかの最適化がまだあります：

  • 過渡ベクトルを使用して結果を収集します。これらは、多くの順次接続詞操作の通常の永続ベクトルよりも少し高速です。
  • 最初/次のシーケンスをトラバースするのではなく、プリミティブを使用してベクトルへのインデックス付きアクセスを使用しました。これにより、一時的なseqオブジェクト（および関連するGC）の作成が回避されます。

結果のコードは次のようになります。

(defn intersect-sorted-vector [x y]
  (loop [i (long 0), j (long 0), r (transient [])]
    (let [xi (nth x i nil), yj (nth y j nil)]
      (cond 
        (not (and xi yj)) (persistent! r)
        (< xi yj) (recur (inc i) j r)
        (> xi yj) (recur i (inc j) r)
        :else (recur (inc i) (inc j) (conj! r xi))))))

(time (count (intersect-sorted-vector x y)))
=> "Elapsed time: 5.143687 msecs"
=> 40258

ご覧のとおり、これにより、おそらく6〜8倍のスピードアップが得られます。

于 2013-01-04T17:24:49.640 に答える