multithreading - Clojure 中的多线程合并排序算法

Question

我需要在 Clojure 中以单线程编写合并排序算法的实现，并使用 2、4、8、16 和 32 线程的并行选项。
程序将从文本文件中读取大量整数(100 万)，并将它们放入列表中进行排序。
我是 Clojure 和函数式编程的新手。
我刚刚编写了读取文件的代码 ...

(use 'clojure.java.io)
(defn get-lines [fname]
  (with-open [r (reader fname)]
    (doall (map read-string (line-seq r)))))
(def numbers (get-lines "numbers.dat"))

...并找到了单线程实现。
但是我无法实现并行算法。这似乎超出了我的范围。
谁能帮帮我？

Answer 1

如果有人正在寻找...

(use 'clojure.java.io)

(defn get-lines [fname]
  (with-open [r (reader fname)]
    (doall (map read-string (line-seq r)))))

(def numbers (get-lines "numbers.dat"))

(defn merge-lists [left right]
  (loop [head [] L left R right]
    (if (empty? L) (concat head R)
    (if (empty? R) (concat head L)
    (if (> (first L) (first R))
      (recur (conj head (first R)) L (rest R))
      (recur (conj head (first L)) (rest L) R))))))

(defn naive-merge-sort [list]
  (if (< (count list) 2) list
    (apply merge-lists
      (map naive-merge-sort
        (split-at (/ (count list) 2) list)))))

(defn parallel-merge-sort-2 [list]
  (if (< (count list) 2) list
    (apply merge-lists
      (pmap naive-merge-sort
        (split-at (/ (count list) 2) list)))))

(defn parallel-merge-sort-4 [list]
  (if (< (count list) 2) list
    (apply merge-lists
      (pmap parallel-merge-sort-2
        (split-at (/ (count list) 2) list)))))

(defn parallel-merge-sort-8 [list]
  (if (< (count list) 2) list
    (apply merge-lists
      (pmap parallel-merge-sort-4
        (split-at (/ (count list) 2) list)))))

(defn parallel-merge-sort-16 [list]
  (if (< (count list) 2) list
    (apply merge-lists
      (pmap parallel-merge-sort-8
        (split-at (/ (count list) 2) list)))))

(defn parallel-merge-sort-32 [list]
  (if (< (count list) 2) list
    (apply merge-lists
      (pmap parallel-merge-sort-16
        (split-at (/ (count list) 2) list)))))

naive-merge-sort 是单线程实现。并行实现将输入列表分成 2-32 个 block ，这些 block 使用 naive-merge-sort 进行排序。