Clojure中的并发笛卡儿乘积算法
是否有一个很好的算法同时计算三个seqs的笛卡儿乘积？
我在Clojure上做一个小爱好项目，主要是为了学习语言，以及它的并发特性。在我的项目中，我需要计算三个seqs的笛卡尔乘积(并对结果做一些事情)。
我在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
}
}
}回答 2
Stack Overflow用户
发布于 2010-04-03 00:34:44
如果你用来处理笛卡儿积的逻辑不是内在顺序的，那么也许你可以把你的输入分成两半(也许把每个输入集分成两部分)，计算出8个独立的笛卡儿积(上半x上半x上半x下半部，.)，对它们进行处理，然后将结果组合起来。我希望这会给你带来很大的刺激。至于调整笛卡儿产品构建本身的性能，我不是专家，但我确实有一些想法和观察(有时需要计算项目Euler的交叉乘积)，所以我尝试在下面对它们进行总结。
首先，在性能部门，我发现c.c.combinatorics函数有点奇怪。这些评论说，它来自Knuth，我相信，所以可能有以下一个结论：(1)它对向量的性能非常好，但是将输入序列向量化的成本会降低它对于其他序列类型的性能；(2)这种编程风格在Clojure中并不一定表现得很好；(3)由于某些设计选择(比如具有这个局部函数)而产生的累积开销是很大的；(4)我遗漏了一些非常重要的东西。因此，虽然我不想否认在某些用例中使用它可能是一个很好的功能(由所涉及的seq总数、每个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可以扩展到处理更多的序列，或者在分配工作负载的方式上更加复杂，但这正是我提出的第一次近似.如果你用你的程序来测试这个结果(当然，也许可以根据你的需要进行调整)，我很想知道结果。
Stack Overflow用户
发布于 2011-04-15 04:38:05
“clojure.contrib.combinatorics有一个笛卡儿乘积函数，它返回一个惰性序列，可以跨越任意数量的序列。
https://stackoverflow.com/questions/2569569
复制相似问题
腾讯云开发者
