clojure - Clojure 中的快速排序

Question

我试图证明 Clojure 的性能可以与 Java 平起平坐。我发现的一个重要用例是快速排序。我写了一个实现如下:

(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 功能吗？我认为性能下降的主要根源是当我需要从循环返回多个值并且必须为此分配一个向量时。这可以避免吗？

_{顺便说一句，运行 Clojure 1.4。另请注意，我已多次运行基准测试以预热 HotSpot。这是他们安定下来的时候。}

更新

我的代码中最可怕的弱点不仅仅是向量的分配，而是它们强制装箱并破坏原始链的事实。另一个弱点是使用循环的结果，因为它们也会破坏链条。是的，Clojure 中的性能仍然是一个雷区。

Answer 1

这个版本基于@mikera，速度同样快，并且不需要使用丑陋的宏。在我的机器上，这需要约 12 毫秒，而 java.util.Arrays/sort 则需要约 9 毫秒:

(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 内联带来问题，因为循环/递归(目前)不支持返回原语。所以你必须将你的代码分解成单独的 fns。这是最好的，因为无论如何，嵌套循环/递归在 Clojure 中变得非常难看。

要更详细地了解如何一致地实现 Java 性能(当您实际需要时)，请检查并理解 test.benchmark .