在搜索不断增长的解决方案空间时使用哪种clojure并行技术？

Question

在Clojure中,当处理的每个作业完全隔离并且可能生成需要评估的其他作业列表时,进行并行处理的正确方法是什么？

我的实际问题是一个营养计算问题,但我会把它放在象棋的形式,它与我的计算共享相同的问题空间特征.

例如,假设我试图在国际象棋游戏中找到Checkmate的所有动作.在搜索电路板状态时,我会从20个可能的状态开始,每个状态代表不同的可能开启动作.每个都需要进行评估,接受或拒绝,然后对于每个接受的移动,将创建一个新的工作列表,代表所有可能的下一步行动.这些工作看起来像这样:

initial: '([] proposed-move)
accepted: '([move] proposed-response)
          '([move move] proposed-response)

作为每次计算的结果,要评估的状态的数量增加,并且可以完全隔离所有其他状态来评估每个状态.

我正在玩的解决方案如下:

; a list of all final solutions, each of which is a sequence of moves
(def solutions (agent []))
; a list of all jobs pending evaluation
(def jobs (agent []))

鉴于这些定义,我将拥有一个java线程池,每个线程都会从作业代理请求一个作业(并等待该请求得到满足).然后它将运行计算,生成解决方案列表和可能的解决方案.最后,它会将解决方案发送给解决方案代理,以及作业代理的可能解决方案.

在这种情况下,使用代理和线程的组合是最惯用的方式吗？我可以按照我提议的方式从作业队列中获取数据吗？

或者我的工作应该是java.util.concurrent.LinkedBlockingQueue,如具有资格的Producer consumer中所述？

Answer 1

您可以通过以下方法来完成此操作：

• 重复应用pmap（它提供集合中所有元素的并行处理）
• pmap 中使用的函数返回元素列表。可以是零个、一个或多个元素，然后将在下一次迭代中处理
• 结果通过concat重新组合
• 您可以根据需要重复处理列表多次，也许将结果存储在原子中。

示例代码可能类似于以下内容

(def jobs (atom '(1 10 100)))

(defn process-element [value]
  (if (< (rand) 0.8)
    [(inc value)]
    []))

(defn do-processing []
  (swap! jobs 
         (fn [job-list] (apply concat (pmap process-element job-list)))))

(while (seq @jobs)
  (prn @jobs)
  (do-processing))

Whick 可以产生如下输出：

(1 10 100)
(2 11 101)
(3 12 102)
(4 13 103)
(5 14 104)
(6 15 105)
(7 106)
(107)
(108)
(109)
nil

请注意，您需要小心一点以确保您的算法终止！在示例中，这是通过元素随着时间的推移而消失来保证的，但是如果您的搜索空间正在增长，那么您可能需要应用时间限制，而不是仅仅使用 ( while ... ) 循环。