3

あるプロセスで特定の整数のペアが発生する回数をカウントする必要があります (局所性に敏感なハッシュを使用して類似の画像を検出するヒューリスティック - 整数は画像を表し、以下の「隣人」は同じハッシュ値を持つ画像であるため、カウントは指定された画像のペアを接続する異なるハッシュの数)。

カウントは、(順序付けられた) ペアからカウント (matches以下) へのマップとして格納されます。

入力 (nbrs-list以下) は、近隣と見なされる整数のリストのリストであり、内部リスト (「近隣」) 内のすべての個別の (順序付けられた) ペアをカウントする必要があります。したがって、たとえば が の場合nbrs-list、[[1,2,3],[10,8,9]]ペアは[1,2],[1,3],[2,3],[8,9],[8,10],[9,10]です。

ルーチンcollectは複数回呼び出されます。matchesパラメータは結果を蓄積し、nbrs-list呼び出しごとに新しくなります。近隣の最小数 (内部リストのサイズ) は 1 で、最大は ~1000 です。の各整数はnbrs-listへの呼び出しで 1 回だけ発生しcollect(これは、各呼び出しでペアが 2 回以上発生しないことを意味します)、整数は 0 から 1,000,000 の範囲をカバーします (つまり、 のサイズはnbrs-list1,000,000 未満です。グループで発生することもありますが、ほとんどの画像には隣接画像がないため、通常は 100,000 を超えます)。

コードの大部分からルーチンを取り出したので、小さな編集エラーが含まれている可能性があります。申し訳ありません。

(defn- flatten-1
  [list]
  (apply concat list))

(defn- pairs
  ([nbrs]
    (let [nbrs (seq nbrs)]
      (if nbrs (pairs (rest nbrs) (first nbrs) (rest nbrs)))))
  ([nbrs a bs]
    (lazy-seq
      (let [bs (seq bs)]
        (if bs
          (let [b (first bs)]
            (cons (if (> a b) [[b a] 1] [[a b] 1]) (pairs nbrs a (rest bs))))
          (pairs nbrs))))))

(defn- pairs-map
  [nbrs]
  (println (count nbrs))
  (let [pairs-list (flatten-1 (pairs nbrs))]
    (apply hash-map pairs-list)))

(defn- collect
  [matches nbrs-list]
  (let [to-add (map pairs-map nbrs-list)]
    (merge-with + matches (apply (partial merge-with +) to-add))))

したがって、上記のコードは、隣接する各セットを順序付けられたペアに展開します。ペアから へのマップを作成し1ます。次に、値の加算を使用してマップを結合します。

これをもっと速く走らせたい。ペアの O(n^2) 展開を回避する方法はわかりませんが、非常に多くの中間構造を回避することで、少なくとも一定のオーバーヘッドを削減できると思います。同時に、コードはかなりコンパクトで読みやすいものにしたい...

ああ、今、「GC オーバーヘッド制限」を超えています。したがって、メモリの使用/チャーンを減らすことも優先事項です:o)

【これは具体的すぎるかも？レッスンが一般的なものであり、「実際の」clojure コードの最適化に関する投稿があまりないように思われることを願っています。また、プロファイリングなどを行うこともできますが、私のコードは非常に醜く見えます。特にペアの展開については、明白でクリーンなアプローチがあることを願っています。]

4

4 に答える 4

3

各ペアが発生する頻度が必要だと思いますか?

関数周波数を試してください。内部でトランジェントを使用するため、GC のオーバーヘッドを回避できます。

于 2012-05-29T13:11:12.210 に答える
1 
=>(require '[clojure.math.combinatorics :as c])

=>(map #(c/combinations % 2) [[1 2 3] [8 9 10]])

(((1 2) (1 3) (2 3)) ((8 9) (8 10) (9 10)))

これはかなり小さなライブラリです。ソースを見てください。

パフォーマンスに関しては、1M 未満の 1K の一意の値のユースケースについて、次の数値の周りを見ています。

=> (time (doseq
           [i (c/combinations (take 1000 (shuffle (range 1000000))) 2)]))

"Elapsed time: 270.99675 msecs"

これには、私のマシンで約 100 ミリ秒かかるターゲット セットの生成が含まれます。

于 2012-05-29T15:11:02.957 に答える
1

（あなたの質問を誤解していないことを願っています）

このようにリスト内のペアを数えたいだけなら、 [[1,2,3],[8,9,10]] は

(defn count-nbr-pairs [n]
   (/ (* n (dec n))
      2))

(defn count-pairs [nbrs-list]
   (apply + (map #(count-nbr-pairs (count %)) nbrs-list)))

(count-pairs [[1 2 3 4] [8 9 10]])
; => 9

もちろん、これは重複したペアを削除する必要がないことを前提としています。

于 2012-05-29T13:57:01.490 に答える
0

上記の提案は役に立ったようですが、不十分でした。私はついに次のようにしてまともなパフォーマンスを得ました：

  • ペアをlong値にパッキングします。これはMAX_LONG > 1e12、longインスタンスが同等であるために機能します（したがって、とは異なり、ハッシュキーとしても機能しますlong[2]）。これは、と比較してメモリ使用量の削減に大きな影響を及ぼしました[n1 n2]。

  • TLongByteHashMapプリミティブ型のハッシュマップを使用して変更します。

  • doseqネストされたループ（またはfor不変のデータ構造を使用する場合はネストされたループ）を使用してペアコードを処理します。

  • 局所性鋭敏型ハッシュを改善します。問題の大部分はそれが弱すぎることでした、それであまりにも多くの隣人を見つけること-百万の画像の隣人が不適切に制約されているなら、あなたは百万のペアを手に入れます、それは少し多すぎるメモリを消費します...

内側のループは次のようになります。

(doseq [i (range 1 (count nbrs))]
  (doseq [j (range i)]
    (let [pair (pack size (nth nbrs i) (nth nbrs j))]
      (if-let [value (.get matches pair)]
        (.put matches pair (byte (inc value)))
        (.put matches pair (byte 0))))))

どこ

(defn- pack
  [size n1 n2]
  (+ (* size n1) n2))

(defn- unpack
  [size pair]
  [(int (/ pair size)) (mod pair size)])
于 2012-05-29T23:24:55.050 に答える