7

seqClojure中是否有一个很好的算法可以同时计算三个s的笛卡尔积？

我正在从事 Clojure 的一个小型业余项目，主要是作为学习该语言及其并发特性的一种手段。在我的项目中，我需要计算三个seqs 的笛卡尔积（并对结果进行处理）。

我在 中找到了这个cartesian-product功能clojure.contrib.combinatorics，效果很好。然而，笛卡尔积的计算结果证明是程序的瓶颈。因此，我想同时执行计算。

现在，对于这个map函数，有一个方便的pmap替代方法可以神奇地使事情并发。这很酷:)。不幸的是，这样的事情不存在cartesian-product。我已经查看了源代码，但我找不到一种简单的方法让它自己并发。

另外，我尝试自己使用 实现一个算法map，但我想我的算法技能已经不像以前那样了。我设法为两个 s 想出了一些丑陋的东西seq，但三个绝对是一座太远的桥梁。

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

编辑

换句话说，我真正想要实现的是实现类似于以下 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

如果您用于处理笛卡尔积的逻辑不是以某种方式本质上是顺序的，那么也许您可以将输入分成两半（也许将每个输入序列分成两部分），计算 8 个单独的笛卡尔积（前半 x 先-half x first-half, first-half x first-half x second-half, ...)，处理它们然后合并结果。我希望这已经给你很大的推动力。至于调整笛卡尔积本身的性能，我不是专家，但我确实有一些想法和观察（有时需要计算 Project Euler 的叉积），所以我试图在下面总结它们。

首先，我觉得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可以扩展以处理更多序列或更复杂的分配工作量的方式，但这就是我想出的第一个近似值......如果你用你的程序进行测试（也许根据你的需要调整它，当然），我很想知道结果。

于 2010-04-03T00:34:44.153 回答
-3

'clojure.contrib.combinatorics 具有笛卡尔积函数。它返回一个惰性序列，并且可以跨越任意数量的序列。

于 2011-04-15T04:38:05.273 回答