Clojure中的并发笛卡尔积算法

Question

seq在Clojure中是否有一个很好的算法来同时计算三个笛卡尔积？

我正在Clojure开展一个小型业余爱好项目,主要是作为学习语言及其并发功能的一种手段.在我的项目中,我需要计算三个笛卡尔乘积seq(并对结果做一些事情).

我找到了cartesian-product函数clojure.contrib.combinatorics,效果很好.然而,笛卡尔积的计算结果证明是该程序的瓶颈.因此,我想同时进行计算.

现在,对于该map功能,有一个方便的pmap替代方案,神奇地使事物并发.哪个很酷:).不幸的是,这样的事情不存在cartesian-product.我查看了源代码,但我找不到一个简单的方法来让它自己并发.

此外,我尝试使用自己实现的算法map,但我想我的算法技能不再像过去那样.我设法拿出了两个丑陋的东西seq,但是三个绝对是一座太过分的桥梁.

那么,有没有人知道一个已经并发的算法,或者我可以自己并行化的算法？

---

编辑

换句话说,我真正想要实现的是实现与此Java代码类似的东西:

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

Answer 1

如果您用来处理笛卡尔积的逻辑不是以某种方式固有顺序,那么也许您可以将输入分成两半(可能将每个输入seq分成两部分),计算8个独立的笛卡尔积(前半部分x第一个) -half x上半场,上半场x上半场x下半场......),处理它们然后合并结果.我希望这会给你带来很大的推动力.至于调整笛卡尔积产品本身的性能,我不是专家,但我确实有一些想法和观察(有时需要计算Euler项目的交叉产品),所以我试着在下面总结它们.

首先,我发现这个c.c.combinatorics功能在演奏部门有点奇怪.评论说它取自Knuth,我相信,所以也许下面的一个得到:(1)它对矢量非常有效,但是输入序列的矢量化成本会影响其他序列类型的性能; (2)这种编程风格一般不一定在Clojure中表现良好; (3)由于某些设计选择(如具有本地功能)而产生的累积开销很大; (4)我遗漏了一些非常重要的东西.所以,虽然我不想忽略它可能是一个很好的功能,用于一些用例(由所涉及的seqs的总数,每个seq中的元素数等等),在我的所有(不科学的)测量简单for似乎更好.

然后有两个我的功能,其中一个可比较for(在更有趣的测试中稍微慢一点,我认为,虽然在其他人看来实际上有点快...但不能说我觉得我准备充分受过教育的比较),另一个显然更快,具有较长的初始输入序列,因为它是第一个的限制功能并行版本.(详情如下.)所以,先定时((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可以扩展到处理更多的序列,或者在分割工作量的方式上更加复杂,但这就是我作为第一个近似值得出的......如果你用你的程序测试它(可能根据你的需要调整它,当然),我很想知道结果.