1

私は並列qsortアルゴリズムを書いていますが、彼は一般的な実装よりも遅く動作しています。問題は関数「concat」にあると思います。アルゴリズムを高速化するには？

(defn qsort-orig [L]
  (if  (empty? L)
    '()
    (let [[pivot & l] L]
      (concat (qsort-orig (for [y l :when (<  y pivot)] y))
              (list pivot)
              (qsort-orig (for [y l :when (>= y pivot)] y))))))

(defn qsort [L]  
(if (empty? L)
  '()
  (let [ [pivot & l] L 
        Left  (for [y l :when (<  y pivot)] y)
        Right (for [y l :when (>= y pivot)] y)]
    (concat (apply concat (pmap qsort 
                            (if (list? Left) 
                              Left 
                              (list Left))))
            (list pivot)
            (apply concat (pmap qsort 
                            (if (list? Right) 
                              Right 
                              (list Right))))))))
# for test
(time (qsort (repeatedly 10000 #(rand-int 10000))))
(time (qsort-orig (repeatedly 10000 #(rand-int 10000))))
4

1 に答える 1

1

これらの両方のメモリ割り当て時間により、それらの間のリアルタイムの違いが洗い流されている可能性があります。

  • recurinを使用するqsort-origと、スタックがすぐに壊れることはなく、メモリの割り当てに費やす時間が短縮されるため、実行速度が大幅に向上します。
  • apply と concat の割り当てを使用すると、呼び出しごとにメモリを割り当てる必要がある concat への呼び出しが構築されるため、左右の呼び出しごとに 1 つの長いシーケンスが作成されます。
  • pmap は、配列内の各エントリに小さな構造体 (将来の呼び出し) を割り当てます。
于 2012-05-24T22:32:00.327 に答える