7

seqClojureで3つのデカルト積を同時に計算するための優れたアルゴリズムはありますか？

私は主に言語とその並行性機能を学ぶ手段として、Clojureで小さな趣味のプロジェクトに取り組んでいます。私のプロジェクトでは、3seq秒のデカルト積を計算する必要があります（そして結果を使って何かをする必要があります）。

cartesian-productで関数を見つけましたclojure.contrib.combinatorics。これはかなりうまく機能します。ただし、デカルト積の計算がプログラムのボトルネックであることが判明しました。そのため、同時に計算を行いたいと思います。

さて、関数については、魔法のように物事を並行させるmap便利な代替手段があります。pmapかっこいいです:)。残念ながら、そのようなものは存在しませんcartesian-product。ソースコードを見てきましたが、自分で並行させる簡単な方法が見つかりません。

また、自分でアルゴリズムを実装しようとしましたmapが、アルゴリズムのスキルは以前とは違うと思います。私はなんとか2秒間醜いものを思いついたseqが、3つは間違いなく遠すぎる橋だった。

それで、誰かがすでに並行しているアルゴリズム、または私が自分自身を並列化できるアルゴリズムを知っていますか？

編集

別の言い方をすれば、私が実際に達成しようとしているのは、このJavaコードに似たものを達成することです。

for (ClassA a : someExpensiveComputation()) {
    for (ClassB b : someOtherExpensiveComputation()) {
        for (ClassC c : andAnotherOne()) {
            // Do something interesting with a, b and c
        }
    }
}
4

2 に答える 2

5

デカルト積を処理するために使用しているロジックが本質的にシーケンシャルでない場合は、入力を半分に分割し（おそらく、各入力シーケンスを2つに分割し）、8つの別々のデカルト積を計算します（前半x最初） -半分x前半、前半x前半x後半、...）、それらを処理してから、結果を結合します。私はこれがあなたにすでにかなりの後押しを与えることを期待します。デカルト積の構築自体のパフォーマンスを微調整することに関しては、私は専門家ではありませんが、いくつかのアイデアと観察があります（プロジェクトオイラーの外積を計算する必要がある場合があります）ので、以下に要約してみました。

まずc.c.combinatorics、パフォーマンス部門の機能が少しおかしいと思います。コメントは、Knuthから取得したものだと私は信じているので、おそらく次のいずれかが得られます。（1）ベクトルに対して非常にパフォーマンスが高いが、入力シーケンスをベクトル化するコストは、他のシーケンスタイプのパフォーマンスを低下させます。（2）このスタイルのプログラミングは、Clojureでは必ずしもうまく機能するとは限りません。（3）何らかの設計上の選択（そのローカル機能を持​​つなど）によって発生する累積オーバーヘッドが大きい。（4）本当に重要なものが欠けています。したがって、いくつかのユースケース（関連するシーケンスの総数、各シーケンスの要素の数などによって決定される）に使用するのに優れた関数である可能性を否定したくはありませんが、すべての私の（非科学的）測定は単純ですforうまくいくようです。

次に、私の2つの機能があります。そのうちの1つは、for（より興味深いテストではやや遅いと思いますが、他のテストでは実際にはやや速いようです...完全に作成する準備ができているとは言えません）に匹敵します。知識に基づいた比較）、もう1つは、最初のバージョンの機能が制限された並列バージョンであるため、最初の入力シーケンスが長く、明らかに高速です。（詳細は以下のとおりです。）したがって、最初にタイミングを設定します（(System/gc)繰り返したい場合は、ときどきスローインしてください）。

;; a couple warm-up runs ellided
user> (time (last (doall (pcross (range 100) (range 100) (range 100)))))
"Elapsed time: 1130.751258 msecs"
(99 99 99)
user> (time (last (doall (cross (range 100) (range 100) (range 100)))))
"Elapsed time: 2428.642741 msecs"
(99 99 99)
user> (require '[clojure.contrib.combinatorics :as comb])
nil
user> (time (last (doall (comb/cartesian-product (range 100) (range 100) (range 100)))))
"Elapsed time: 7423.131008 msecs"
(99 99 99)
;; a second time, as no warm-up was performed earlier...
user> (time (last (doall (comb/cartesian-product (range 100) (range 100) (range 100)))))
"Elapsed time: 6596.631127 msecs"
(99 99 99)
;; umm... is syntax-quote that expensive?
user> (time (last (doall (for [x (range 100)
                               y (range 100)
                               z (range 100)]
                           `(~x ~x ~x)))))
"Elapsed time: 11029.038047 msecs"
(99 99 99)
user> (time (last (doall (for [x (range 100)
                               y (range 100)
                               z (range 100)]
                           (list x y z)))))
"Elapsed time: 2597.533138 msecs"
(99 99 99)
;; one more time...
user> (time (last (doall (for [x (range 100)
                               y (range 100)
                               z (range 100)]
                           (list x y z)))))
"Elapsed time: 2179.69127 msecs"
(99 99 99)

そして今、関数の定義：

(defn cross [& seqs]
  (when seqs
    (if-let [s (first seqs)]
      (if-let [ss (next seqs)]
        (for [x  s
              ys (apply cross ss)]
          (cons x ys))
        (map list s)))))

(defn pcross [s1 s2 s3]
  (when (and (first s1)
             (first s2)
             (first s3))
    (let [l1 (count s1)
          [half1 half2] (split-at (quot l1 2) s1)
          s2xs3 (cross s2 s3)
          f1 (future (for [x half1 yz s2xs3] (cons x yz)))
          f2 (future (for [x half2 yz s2xs3] (cons x yz)))]
      (concat @f1 @f2))))

すべてのバージョンで同じ結果が得られると思います。pcrossより多くのシーケンスを処理するように拡張したり、ワークロードを分割する方法をより洗練したりすることもできますが、それが最初の概算として思いついたものです...これをプログラムでテストする場合（おそらくニーズに合わせて調整する場合）もちろん）、結果を知りたいと思います。

于 2010-04-03T00:34:44.153 に答える
-3

'clojure.contrib.combinatoricsには、デカルト積関数があります。遅延シーケンスを返し、任意の数のシーケンスを交差させることができます。

于 2011-04-15T04:38:05.273 に答える