Multithreaded Merge-Sort-Algorithmus in Clojure

Question

Ich muss Implementierung von Merge-Sort-Algorithmus in Clojure in einzelnen Thread schreiben und Parallelität Optionen mit 2, 4, 8, 16 und 32 Threads verwenden.
Das Programm liest eine große Sammlung von ganzen Zahlen (1 Million) aus einer Textdatei und fügt sie in eine Liste zum Sortieren ein.
Ich bin sehr Neuling auf Clojure und funktionale Programmierung überhaupt.
Ich habe geschrieben Code nur zum Lesen Datei ...

(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")) 

... und einzige Thread-Implementierung gefunden.
Aber ich kann parallelen Algorithmus nicht realisieren. Es scheint jenseits von mir zu sein.
Könnte mir jemand helfen?

Answer 1

Wenn jemand sucht ...

(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 ist Single-Thread-Implementierung. Bei parallelen Implementierungen wird die Eingabeliste in 2-32 Chunks unterteilt, die mit Naive-Merge-Sort sortiert werden.

Answer 2

Das klingt viel wie eine Hausaufgabe (wie ein Kommentator sagte), so zögere ich, eine detaillierte Antwort zu geben. Ich kann Ihnen sagen, dass Sie in Clojure verschiedene Arten von Nebenläufigkeit untersuchen wollen. In der Reihenfolge von den einfachsten zu den komplexesten, einige Ansätze, die Sie für dieses Problem möglicherweise berücksichtigen möchten, sind Pmap, Futures und core.async. Ich schlage vor, einen Blick auf die basic docs for pmap nehmen, bei Clojure für die Mutigen und Wahre ‚s Kapitel über concurrency und core.async und bei clojure.org der page about concurrency