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 の sort 関数も読みましたが、混乱します。

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 行目です。2 つの入力パラメーターを交換するだけです。このコードが実行される理由を教えてください。

4

4 に答える 4

2

(. java.util.Arrays (sort a comp)) this call is to Arrays sort function and not a recursive call to the clojure.core sort function.

Your code is slow because quick sort is a imperative algorithm i.e it is based on concepts of imperative programming like in place array mutation. Your code is fine but the problem is it traverse the collection many times and also many intermediate collections are created.

You can use array and in place array mutation to make your quick sort fast.

于 2012-06-08T07:27:40.387 に答える
2

Clojure の sort 関数は、Java の標準 java.util.Arrays/sort メソッドを内部で使用するだけです。100% clojure の実装ではありません。

クイックソートは、O(1) 要素の高速スワッピングを行うコレクション型に依存しているため、イディオム的な clojure にはあまり適していません。また、実装では、(last coll) と (count coll) をすべての呼び出しで実行していることにも注意してください。ここで、coll は遅延 seq であるため、両方とも O(n) です。 〜を考慮して、おそらく中間コレクションタイプとして不変のseqの代わりにJava配列を使用します。

于 2012-06-08T07:29:32.660 に答える
1

qsort は、ほとんどの時間をオブジェクトの割り当てに費やしている可能性があります。

  • filter への呼び出しは、各パスの各番号に遅延詐欺インスタンスを割り当てます
  • 連結の呼び出しにより、各数値に別のオブジェクトが割り当てられます

私の意見では、あなたのバージョンの方が読みやすいですが

于 2012-06-08T07:31:44.787 に答える
1

スタック オーバーフローの問題は、フィルターに遅延フィルターを再帰的に配置していることです。それはここでよく説明されています：

スタック オーバーフローを引き起こす再帰関数

あなたの他の質問について: 12 行目では、それは clojure の sort 関数の呼び出しではなく、Arrays-sort 関数の呼び出しです。ユーザーコードでは、通常(java.util.Arrays/sort a comp)、ドット構文の代わりに記述します。

于 2012-06-08T07:30:03.057 に答える