如何为递归函数实现多线程

Question

考虑一个简单的2人游戏，如下所示：偶数枚硬币排成一行。每个玩家轮流在一行的一端移除硬币。目标是当所有硬币都被拿走时，硬币的价值最高。

玩家1找到所有偶数硬币和所有奇数硬币的总和。如果奇数硬币的总和较高，玩家1拿最左边的硬币；否则他拿最右边的。

玩家2现在有一个选择，有奇数个硬币。选择第一个硬币或最后一个硬币将导致玩家1的硬币列表略有不同。玩家2使用递归搜索的结果来确定是选择第一个还是最后一个硬币。

我希望能够以某种方式实现多线程上的p2-helper递归函数，现在确定如何。任何建议或想法将不胜感激，谢谢！

(ns game.core
  (:gen-class))

; function that returns the vector of a string (split up by spaces)
(defn vector-from-string [s]
  (drop 1 (map read-string (clojure.string/split (clojure.string/trim-newline s) #" "))))

; function that returns the slurped string of a read-in file
(defn string-from-file [f]
  (slurp f))

; function that returns the sum of all the odd-indexed items in a vector
(defn sum-of-evens [v]
  (reduce + (take-nth 2 (rest v))))

; function that returns the sum of all the odd-indexed items in a vector
(defn sum-of-odds [v]
  (reduce + (take-nth 2 v)))

; function that returns the vector that is left after player one moves, and then the coin that player one took
(defn p1 [v]
  (if (> (sum-of-odds v) (sum-of-evens v))
    [(drop 1 v) (first v)]
    [(drop-last v) (last v)]))

; nearly identical to 'p1' but this function only returns the affected vector after player 1 has moved
(defn p2-p1 [v]
  (if (even? (count v))
    (if (> (sum-of-odds v) (sum-of-evens v))
      (drop 1 v)
      (drop-last v))
    (drop 0 v)))

; recursive search for player two
(defn p2-helper [v]
  (if (or (= (count v) 1) (= (count v) 0))
    (reduce + v)
    (max (+ (p2-helper (drop 1 (p2-p1 v))) (first (p2-p1 v))) (+ (p2-helper (drop-last (p2-p1 v))) (last (p2-p1 v))))))

; function that returns the vector that is left after player two moves, and then the coin that player two took
(defn p2 [v]
  (if (> (+ (p2-helper (drop 1 (p2-p1 v))) (first (p2-p1 v))) (+ (p2-helper (drop-last (p2-p1 v))) (last (p2-p1 v))))
    [(drop 1 v) (first v)]
    [(drop-last v) (last v)]))

; function to play the game out until no coins are left
(defn play-game [v]
  (def coins v)
  (def p1score 0)
  (def p2score 0)
  (while (not (empty? coins))
    (do
      (let [[new-vec score] (p1 coins)]
        (def coins new-vec)
        (def p1score (+ p1score score)))
      (let [[new-vec score] (p2 coins)]
        (def coins new-vec)
        (def p2score (+ p2score score)))))
  (println "player 1 score:" p1score)
  (println "player 2 score:" p2score))

; main
(defn -main [& args]
  (let [v (vector-from-string (string-from-file "10.txt")) ]
    (play-game v)))

Answer 1

最初的方法是在每个递归调用周围添加@（future）（p2 helpet…），这可能会运行太多线程，运行速度较慢。

第二种方法可能是更改助手，将工作放入任务队列，并使一些线程处理它们。这会更好，尽管速度可能会更慢。

我将继续改进它，通过调用trampoline来展开递归，以阻止它破坏堆栈。然后试着让顶层平行，或者只让两个顶层平行。