1

我在 clojure 中写了一个快速排序函数，但运行速度非常慢。有时，如果输入集合变得更大，它甚至可能会溢出堆栈？

我的代码有什么问题吗？

(defn qsort [coll]
  (if (<= (count coll) 1)
    coll
    (let [pivot (last coll)
          head-half (filter #(< % pivot) (drop-last coll))
          tail-half (filter #(>= % pivot) (drop-last coll))]
      (concat (qsort head-half) (vector pivot) (qsort tail-half)))))

我还阅读了 clojure.core 中的排序功能，但它让人感到困惑。

01 (defn sort
02   "Returns a sorted sequence of the items in coll. If no comparator is
03   supplied, uses compare. comparator must
04   implement java.util.Comparator."
05   {:added "1.0"
06    :static true}
07   ([coll]
08    (sort compare coll))
09   ([^java.util.Comparator comp coll]
10    (if (seq coll)
11      (let [a (to-array coll)]
12        (. java.util.Arrays (sort a comp))
13        (seq a))
14      ())))

递归发生的唯一地方是第 12 行。它只是交换两个输入参数！你能解释一下为什么这段代码会运行吗？

4

4 回答 4

2

(. java.util.Arrays (sort a comp))此调用是对数组排序函数的调用，而不是对 clojure.core 排序函数的递归调用。

您的代码很慢，因为快速排序是imperative algorithm基于命令式编程的概念，例如就地数组突变。您的代码很好，但问题是它多次遍历集合，并且创建了许多中间集合。

您可以使用数组和就地数组突变来快速进行快速排序。

于 2012-06-08T07:27:40.387 回答
2

Clojure 的排序功能只是在内部使用了 Java 的标准 java.util.Arrays/sort 方法；它不是 100% 的 clojure 实现。

Quicksort 对于惯用的 clojure 来说并不是一个很好的匹配，因为它依赖于具有快速 O(1) 元素交换的集合类型。另请注意，在您的实现中，您正在执行 (last coll) 和 (count coll) 每次调用，其中 coll 是一个惰性序列，因此两者都是 O(n) - 您应该能够通过采用它来提高性能考虑到 ~ 可能是通过使用 java Array 而不是不可变的 seq 作为中间集合类型。

于 2012-06-08T07:29:32.660 回答
1

堆栈溢出的问题是您将惰性过滤器递归地放在过滤器上。这在这里解释得很好：

递归函数导致堆栈溢出

关于您的另一个问题：在第 12 行，这不是对 clojure 排序函数的调用，而是对数组排序函数的调用。在用户代码中，您通常会编写(java.util.Arrays/sort a comp)而不是点语法。

于 2012-06-08T07:30:03.057 回答
1

您的 qsort 可能大部分时间都在分配对象。

  • 对过滤器的调用为每次传递的每个数字分配一个惰性缺点实例
  • 对连接的调用为每个数字分配另一个对象

虽然我认为你的版本读起来更好

于 2012-06-08T07:31:44.787 回答