Clojure中的并行笛卡尔积算法

Question

Clojure中的并行笛卡尔积算法

algorithmconcurrencyclojureparallel-processingcartesian-product

7

有没有一种好的算法可以在Clojure中同时计算三个seq的笛卡尔积？

我正在使用Clojure进行一个小型业余项目，主要是为了学习这门语言及其并发特性。在我的项目中，我需要计算三个seq的笛卡尔积（并对结果执行某些操作）。

我发现clojure.contrib.combinatorics中的cartesian-product函数效果不错。然而，计算笛卡尔积竟成为程序的瓶颈。因此，我想并行执行计算。

现在，对于map函数，有一个方便的pmap替代品，可以神奇地实现并发。这很酷 : )。不幸的是，对于cartesian-product这样的函数，没有类似的东西。我已经查看了源代码，但我找不到自己轻松实现并发的方法。

此外，我尝试使用map实现算法，但我想我的算法技能已经退化了。我成功地为两个seq想出了一个丑陋的算法，但对于三个seq来说，这绝对是太难了。

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

编辑

换句话说，我真正想实现的是，实现类似于这段Java代码的功能：

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

- jqno

你能记忆化你的昂贵计算吗？ - Brian Carper

2个回答

-3

'clojure.contrib.combinatorics有一个cartesian-product函数。它返回一个lazy序列，可以跨越任何数量的序列。

- Sathish

原帖作者提到这个函数对他的需求来说太慢了... - Ben Mabey

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Michał Marczyk · Accepted Answer

如果你用来处理笛卡尔积的逻辑不是固有的顺序逻辑，那么也许你可以把输入数据一分为二（也许是将每个输入序列都分成两部分），计算8个独立的笛卡尔积（第一部分×第一部分×第一部分，第一部分×第一部分×第二部分，...），然后处理它们并合并结果。我相信这已经会给你带来很大的提升了。至于调整笛卡尔积构建本身的性能，我不是专家，但我有一些想法和观察（在项目欧拉中有时需要计算叉积），所以我尝试在下面总结一下。

首先，我发现c.c.combinatorics函数在性能方面有点奇怪。评论中说它是从Knuth那里得来的，我相信以下其中之一：（1）使用向量非常高效，但向量化输入序列的成本使其对其他序列类型的性能产生负面影响；（2）这种编程风格通常在Clojure中表现不佳；（3）由于某些设计选择（例如该本地函数）引起的累计开销很大；（4）我错过了什么重要的东西。因此，虽然我不想排除它可能是用于某些用例的绝佳函数的可能性（这些用例由涉及的序列总数、每个序列中的元素数量等决定），但在我所有的（非科学的）测量中，一个简单的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可以扩展以处理更多序列或更复杂地拆分其工作量，但这是我作为第一个近似解想出来的...如果您使用您的程序进行测试（当然，可能需要根据您的需求进行调整），我会非常好奇知道结果。