algorithm - 为什么clojure中的并行qsort比common的实现慢？

Question

我正在编写一个并行 qsort 算法，但他的工作速度比普通实现慢。我认为问题出在函数“concat”中。如何加快算法速度？

(defn qsort-orig [L]
  (if  (empty? L)
    '()
    (let [[pivot & l] L]
      (concat (qsort-orig (for [y l :when (<  y pivot)] y))
              (list pivot)
              (qsort-orig (for [y l :when (>= y pivot)] y))))))

(defn qsort [L]  
(if (empty? L)
  '()
  (let [ [pivot & l] L 
        Left  (for [y l :when (<  y pivot)] y)
        Right (for [y l :when (>= y pivot)] y)]
    (concat (apply concat (pmap qsort 
                            (if (list? Left) 
                              Left 
                              (list Left))))
            (list pivot)
            (apply concat (pmap qsort 
                            (if (list? Right) 
                              Right 
                              (list Right))))))))
# for test
(time (qsort (repeatedly 10000 #(rand-int 10000))))
(time (qsort-orig (repeatedly 10000 #(rand-int 10000))))

Answer 1

这两者的内存分配时间很可能正在消除它们之间的实时差异。

• 如果你使用recurinqsort-orig那么它不会很快破坏堆栈并且应该运行得更快，因为它会花费更少的时间分配内存。
• 使用 apply 和 concat allocates 将为左侧和右侧的每个调用创建一个长序列，因为它构建了对 concat 的调用，这将需要为每个调用分配内存
• pmap 为数组中的每个条目分配一个小结构（未来调用）。