在clojure缓慢'快速排序'

我在clojure写了一个快速排序函数，但它运行速度非常慢。有时，如果输入集合变大，甚至可能溢出堆栈？在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行。它只是交换两个输入参数！您能否向我解释为什么这段代码是运行的？

来源

2012-06-08 qiuxiafei

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

你的代码很慢，因为快速排序是一个imperative algorithm，即它是基于命令式编程的概念，如地方阵列变异。你的代码很好，但问题是它遍历集合很多次，并且还创建了许多中间集合。

您可以使用数组和位置数组变异来快速排序。

来源

2012-06-08 07:27:40 Ankur

//clojure.org/java_interop#dot （实例EXPR（方法符号ARGS *））和（实例EXPR方法符号ARGS *）是等效的。我想知道为什么有这么多不同的形式为同一件事 – qiuxiafei

可能是遗留行李的结果:) – Ankur

Clojure的排序函数内部使用Java的标准java.util.Arrays/sort方法;这不是100％的clojure实现。

快速排序并不是一个很好的习惯clojure匹配，因为它取决于具有快速O（1）元素交换的集合类型。还要注意，在你的实现中，你在做每个调用（最后一个coll）和（count coll），其中coll是一个懒序列，所以两者都是O（n） - 你应该能够通过考虑考虑到〜可能通过使用java数组而不是不可变的seq作为中间集合类型。

来源

2012-06-08 07:29:32

@qiuxiafel - 我想合并排序会更有意义 - 你可能想尝试。 –

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

Recursive function causing a stack overflow

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

来源

2012-06-08 07:30:03

你的qsort可能花费大部分时间分配对象。