在Clojure的Quicksort

Question

我试图证明Clojure的性能可以与Java平等.我发现的一个重要用例是Quicksort.我写了一个如下实现:

(set! *unchecked-math* true)

(defn qsort [^longs a]
  (let [qs (fn qs [^long low, ^long high]
             (when (< low high)
               (let [pivot (aget a low)
                     [i j]
                     (loop [i low, j high]
                       (let [i (loop [i i] (if (< (aget a i) pivot)
                                             (recur (inc i)) i))
                             j (loop [j j] (if (> (aget a j) pivot)
                                             (recur (dec j)) j))
                             [i j] (if (<= i j)
                                     (let [tmp (aget a i)]
                                       (aset a i (aget a j)) (aset a j tmp)
                                       [(inc i) (dec j)])
                                     [i j])]
                         (if (< i j) (recur i j) [i j])))]
                 (when (< low j) (qs low j))
                 (when (< i high) (qs i high)))))]
    (qs 0 (dec (alength a))))
  a)

此外,这有助于调用Java快速排序:

(defn jqsort [^longs a] (java.util.Arrays/sort a) a))

现在,为基准.

user> (def xs (let [rnd (java.util.Random.)] 
        (long-array (repeatedly 100000 #(.nextLong rnd)))))
#'user/xs
user> (def ys (long-array xs))
#'user/ys
user> (time (qsort ys))
"Elapsed time: 163.33 msecs"
#<long[] [J@3ae34094>
user> (def ys (long-array xs))
user> (time (jqsort ys))
"Elapsed time: 13.895 msecs"
#<long[] [J@1b2b2f7f>

性能是世界分开的(一个数量级,然后是一些).

有什么我想念的,我可能使用过的任何Clojure功能吗？我认为性能下降的主要原因是我需要从循环中返回多个值,并且必须为此分配一个向量.这可以避免吗？

_{BTW运行Clojure 1.4.另请注意,我已多次运行基准测试以热身HotSpot.这些是他们安定下来的时候.}

更新

我的代码中最可怕的弱点不仅仅是向量的分配,而是它们强制装箱并打破原始链的事实.另一个弱点是使用结果,loop因为它们也打破了链条.是的,在Clojure中的表现仍然是一个雷区.

Answer 1

这个版本是基于@ mikera的,同样快,不需要使用丑陋的宏.在我的机器上,java.util.Arrays/sort需要~12ms vs~9ms:

(set! *unchecked-math* true)
(set! *warn-on-reflection* true)

(defn swap [^longs a ^long i ^long j]
  (let [t (aget a i)]
    (aset a i (aget a j))
    (aset a j t)))

(defn ^long apartition [^longs a ^long pivot ^long i ^long j]
  (loop [i i j j]
    (if (<= i j)
      (let [v (aget a i)]
        (if (< v pivot)
          (recur (inc i) j)
          (do 
            (when (< i j) 
              (aset a i (aget a j))
              (aset a j v))
            (recur i (dec j)))))
      i)))

(defn qsort 
  ([^longs a]
     (qsort a 0 (long (alength a))))
  ([^longs a ^long lo ^long hi]    
     (when
         (< (inc lo) hi)
       (let [pivot (aget a lo)
             split (dec (apartition a pivot (inc lo) (dec hi)))]
         (when (> split lo)
           (swap a lo split))
         (qsort a lo split)
         (qsort a (inc split) hi)))
     a))

(defn ^longs rand-long-array []
  (let [rnd (java.util.Random.)] 
    (long-array (repeatedly 100000 #(.nextLong rnd)))))

(comment
  (dotimes [_ 10]
    (let [as (rand-long-array)]
      (time
       (dotimes [_ 1] 
         (qsort as)))))
  )

从Clojure 1.3开始,大多数情况下都不需要手动内联.只有函数参数的几个类型提示,JVM将为您进行内联.没有必要为数组操作转换为int的索引参数 - Clojure为您执行此操作.

需要注意的一点是,嵌套循环/重复确实会给JVM内联带来问题,因为loop/recur不支持(此时)支持返回原语.因此,您必须将代码拆分为单独的fns.这是最好的,因为无论如何嵌套循环/重复在Clojure中变得非常难看.

有关如何始终如一地实现Java性能(当您确实需要它时)的更详细信息,请检查并了解test.benchmark.

Answer 2

由于宏的原因,这有点可怕,但是使用这段代码,我认为你可以匹配Java速度(​​我的基准测试大约需要11ms):

(set! *unchecked-math* true)

(defmacro swap [a i j]
  `(let [a# ~a
         i# ~i
         j# ~j
         t# (aget a# i#)]
     (aset a# i# (aget a# j#))
     (aset a# j# t#)))

(defmacro apartition [a pivot i j]
  `(let [pivot# ~pivot]
     (loop [i# ~i
            j# ~j]
       (if (<= i# j#)
         (let [v# (aget ~a i#)]
           (if (< v# pivot#)
             (recur (inc i#) j#)
             (do 
               (when (< i# j#) 
                 (aset ~a i# (aget ~a j#))
                 (aset ~a j# v#))
               (recur i# (dec j#)))))
         i#))))

(defn qsort 
  ([^longs a]
    (qsort a 0 (alength a)))
  ([^longs a ^long lo ^long hi]    
    (let [lo (int lo)
          hi (int hi)]
      (when
        (< (inc lo) hi)
        (let [pivot (aget a lo)
              split (dec (apartition a pivot (inc lo) (dec hi)))]
          (when (> split lo) (swap a lo split))
          (qsort a lo split)
          (qsort a (inc split) hi)))
      a)))

主要技巧是:

• 用原始算法做一切
• 使用int作为数组索引(这可以避免一些不必要的强制转换,不是很重要,但每一点都有帮助....)
• 使用宏而不是函数来分解代码(避免函数调用开销和参数装箱)
• 使用loop/recur在内循环中获得最大速度(即分区子阵列)
• 避免在堆上构造任何新对象(因此避免使用向量,序列,映射等)

Answer 3

在Clojure的喜悦,第6.4章描述了一个懒懒洋洋快速排序排序algorithm.The妙处在于,它只会做必要尽可能多的工作,以找到第一个x值.所以如果x << n这个算法是O(n).

(ns joy.q)

(defn sort-parts
  "Lazy, tail-recursive, incremental quicksort.  Works against
   and creates partitions based on the pivot, defined as 'work'."
  [work]
  (lazy-seq
   (loop [[part & parts] work]
     (if-let [[pivot & xs] (seq part)]
       (let [smaller? #(< % pivot)]
         (recur (list*
                 (filter smaller? xs)
                 pivot
                 (remove smaller? xs)
                 parts)))
       (when-let [[x & parts] parts]
         (cons x (sort-parts parts)))))))

(defn qsort [xs]
    (sort-parts (list xs))) 

Answer 4

通过检查mikera的答案的要点,你可以看到他们主要集中在消除使用惯用语(而不是调整)Clojure引入的开销,这可能不存在于惯用的Java实现中:

• 原始算术 - 在Java中稍微容易一点,更惯用,你更可能使用ints而不是Integers
• 对于数组索引的整数 - 相同
• 使用宏而不是函数来分解代码(避免函数调用开销和装箱) - 修复了使用该语言引入的问题.Clojure鼓励功能风格,因此函数调用开销(和拳击).
• 在内循环中使用loop/recur来获得最大速度 - 在Java中,你习惯性地使用一个普通循环(就我所知,这是循环/重复编译的东西)

话虽如此,实际上还有另一个微不足道的解决方案.编写(或找到)Quick Sort的高效Java实现,用这样的签名来说:

Sort.quickSort(long[] elems)

然后从Clojure调用它:

(Sort/quickSort elems)

清单:

• 与Java一样高效 - 是的

• Clojure中的惯用语 - 可以说是的,我会说Java-interop是Clojure的核心功能之一.

• 可重用 - 是的,您很有可能轻松找到已经编写的非常有效的Java实现.

_{我不是想要哄骗,我理解你试图通过这些实验找到的东西我只是为了完整而添加这个答案.让我们不要忽视明显的一个!:)}