algorithm - Clojure 中的并发笛卡尔积算法

Question

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

我正在从事 Clojure 的一个小型业余爱好项目，主要是作为学习该语言及其并发功能的一种方式。在我的项目中，我需要计算三个 seq 的笛卡尔积(并对结果进行处理)。

我在 clojure.contrib.combinatorics 中找到了 cartesian-product 函数，它运行良好。然而，笛卡尔积的计算结果是程序的瓶颈。因此，我想并发执行计算。

现在，对于 map 函数，有一个方便的 pmap 替代方案可以神奇地使事情并发。这很酷 :)。不幸的是，笛卡尔积 不存在这样的东西。我查看了源代码，但找不到让自己并发的简单方法。

此外，我曾尝试使用 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

如果您用来处理笛卡尔积的逻辑在某种程度上不是固有顺序的，那么也许您可以将输入分成两半(也许将每个输入序列一分为二)，计算 8 个单独的笛卡尔积(首先 - half x first-half x first-half, first-half x first-half x second-half, ...)，处理它们然后组合结果。我希望这会给你很大的插入力。至于调整笛卡尔积构建本身的性能，我不是专家，但我确实有一些想法和观察(有时需要为欧拉计划计算叉积)，所以我试图在下面总结它们。

首先，我发现性能部门的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 可以扩展以处理更多序列或在拆分工作负载的方式上更复杂，但这就是我想出的第一个近似值……如果你用你的程序测试它(当然，也许可以根据您的需要进行调整)，我非常想知道结果。