一方、Haskell でベクトルを使用してインプレース クイックソートを実装することは可能です。
2 番目のアルゴリズムは最初のアルゴリズムよりもどれくらい高速ですか?
もちろん、それは実装に依存します。以下に見られるように、リストが短すぎない場合、変更可能なベクトルまたは配列での適切なインプレース ソートは、リストからの変換とリストへの変換の時間が含まれていても、リストのソートよりもはるかに高速です (そして、その変換が補われます)。時間の大部分）。
ただし、リスト アルゴリズムはインクリメンタルな出力を生成しますが、配列/ベクトル アルゴリズムは完了する前に結果を生成しないため、リストの並べ替えが依然として望ましい場合があります。
リンクされた可変配列/ベクトルアルゴリズムが何を間違っていたのか正確にはわかりません。しかし、彼らはかなり間違ったことをしました。
可変ベクトル コードの場合、ボックス化されたベクトルを使用しているようで、ポリモーフィックであり、どちらもパフォーマンスに大きな影響を与える可能性がありますが、関数が{-# INLINABLE #-}.
コードについてはIOUArray、まあ、楽しそうに見えますが、遅いです。を使用しIORef、明確な厳密さはありませんreadArray。writeArrayそれなら、それがかかるひどい時間はそれほど驚くべきことではありません.
を使用して（モノモーフィック）Cコードをより直接的に翻訳STUArrayし、ラッパーを使用してリストで動作させる¹、
{-# LANGUAGE BangPatterns #-}
module STUQuickSort (stuquick) where
import Data.Array.Base (unsafeRead, unsafeWrite)
import Data.Array.ST
import Control.Monad.ST
stuquick :: [Int] -> [Int]
stuquick [] = []
stuquick xs = runST (do
let !len = length xs
arr <- newListArray (0,len-1) xs
myqsort arr 0 (len-1)
-- Can't use getElems for large arrays, that overflows the stack, wth?
let pick acc i
| i < 0 = return acc
| otherwise = do
!v <- unsafeRead arr i
pick (v:acc) (i-1)
pick [] (len-1))
myqsort :: STUArray s Int Int -> Int -> Int -> ST s ()
myqsort a lo hi
| lo < hi = do
let lscan p h i
| i < h = do
v <- unsafeRead a i
if p < v then return i else lscan p h (i+1)
| otherwise = return i
rscan p l i
| l < i = do
v <- unsafeRead a i
if v < p then return i else rscan p l (i-1)
| otherwise = return i
swap i j = do
v <- unsafeRead a i
unsafeRead a j >>= unsafeWrite a i
unsafeWrite a j v
sloop p l h
| l < h = do
l1 <- lscan p h l
h1 <- rscan p l1 h
if (l1 < h1) then (swap l1 h1 >> sloop p l1 h1) else return l1
| otherwise = return l
piv <- unsafeRead a hi
i <- sloop piv lo hi
swap i hi
myqsort a lo (i-1)
myqsort a (i+1) hi
| otherwise = return ()
ボックス化されていないベクトルの適切な並べ替え (クイック並べ替えではなくイントロ並べ替え) のラッパー、
module VSort where
import Data.Vector.Algorithms.Intro
import qualified Data.Vector.Unboxed as U
import Control.Monad.ST
vsort :: [Int] -> [Int]
vsort xs = runST (do
v <- U.unsafeThaw $ U.fromList xs
sort v
s <- U.unsafeFreeze v
return $ U.toList s)
私は予想に沿って何倍も得ます（注：deepseqこれらのタイミングでは、ソートアルゴリズムを呼び出す前にランダムリストが編集されています。それがないSTUArrayと、サンクの長いリストを最初に評価するため、への変換ははるかに遅くなります長さを決定します. vectorfromListパッケージの変換はこの問題に悩まされません.を への変換に移すと, 他のソート [およびvectorの場合は変換] アルゴリズムは少し時間がかかります. -algorithms ' イントロソートとクイックソートが少し大きくなります。):deepseqSTUArraySTUArray
list size: 200000 -O2 -fllvm -fllvm-O2
──────── ──────── ──────── ──────── ────────
Data.List.sort 0.663501s 0.665482s 0.652461s 0.792005s
Naive.quicksort 0.587091s 0.577796s 0.585754s 0.667573s
STUArray.quicksort 1.58023s 0.142626s 1.597479s 0.156411s
VSort.vsort 0.820639s 0.139967s 0.888566s 0.143918s
最適化されていない時間は、STUArray. 高速にするためにインライン化する必要がありますunsafeRead。unsafeWriteインライン化されていない場合は、呼び出しごとに辞書検索が行われます。したがって、大規模なデータセットの場合、最適化されていない方法は省略します。
list size: 3000000 -O2 -fllvm-O2
──────── ──────── ────────
Data.List.sort 16.728576s 16.442377s
Naive.quicksort 14.297534s 12.253071s
STUArray.quicksort 2.307203s 2.200807s
VSort.vsort 2.069749s 1.921943s
可変ボックス化されていない配列のインプレース ソートは、正しく行われた場合、リストベースのソートよりもはるかに高速であることがわかります。ボックス化されていない変更可能なベクターの並べ替えと並べ替えの違いは、STUArrayアルゴリズムの違いによるものなのか、それともベクターの方が実際に高速なのかはわかりません。ベクトルがSTUArrays よりも速い² ことを観察したことがないので、前者を信じる傾向があります。
クイックソートとイントロソートの違いは、ベクトルパッケージが提供STUArrayするリストとの間の変換が優れていることと、アルゴリズムが異なることです。
Louis Wassermanの提案で、あまり大きくないデータセットを使用して、vector-algorithms パッケージの他の並べ替えアルゴリズムを使用して簡単なベンチマークを実行しました。結果は驚くべきことではなく、優れた汎用アルゴリズムのヒープソート、イントロソート、およびマージソートはすべてうまく機能し、ボックス化されていない可変配列のクイックソートに近い時間です (ただし、もちろん、クイックソートはほとんどソートされた入力で二次動作に低下しますが、これらはO(n*log n) の最悪のケースが保証されています)。特殊用途のソートアルゴリズムAmericanFlag入力が目的にうまく適合しないため、基数ソートはうまく機能しません（基数ソートは、データに必要な数よりも多くのパスを実行するため、範囲が広い大きな入力でうまく機能します）。挿入ソートは、その 2 次動作のために、断然最悪です。
AmericanFlag:
list size: 300000 -O2 -fllvm-O2
──────── ──────── ────────
Data.List.sort 1.083845s 1.084699s
Naive.quicksort 0.981276s 1.05532s
STUArray.quicksort 0.218407s 0.215564s
VSort.vsort 2.566838s 2.618817s
Heap:
list size: 300000 -O2 -fllvm-O2
──────── ──────── ────────
Data.List.sort 1.084252s 1.07894s
Naive.quicksort 0.915984s 0.887354s
STUArray.quicksort 0.219786s 0.225748s
VSort.vsort 0.213507s 0.20152s
Insertion:
list size: 300000 -O2 -fllvm-O2
──────── ──────── ────────
Data.List.sort 1.168837s 1.066058s
Naive.quicksort 1.081806s 0.879439s
STUArray.quicksort 0.241958s 0.209631s
VSort.vsort 36.21295s 27.564993s
Intro:
list size: 300000 -O2 -fllvm-O2
──────── ──────── ────────
Data.List.sort 1.09189s 1.112415s
Naive.quicksort 0.891161s 0.989799s
STUArray.quicksort 0.236596s 0.227348s
VSort.vsort 0.221742s 0.20815s
Merge:
list size: 300000 -O2 -fllvm-O2
──────── ──────── ────────
Data.List.sort 1.087929s 1.074926s
Naive.quicksort 0.875477s 1.019984s
STUArray.quicksort 0.215551s 0.221301s
VSort.vsort 0.236661s 0.230287s
Radix:
list size: 300000 -O2 -fllvm-O2
──────── ──────── ────────
Data.List.sort 1.085658s 1.085726s
Naive.quicksort 1.002067s 0.900985s
STUArray.quicksort 0.217371s 0.228973s
VSort.vsort 1.958216s 1.970619s
結論: 特に理由がない限り、 vector-algorithmsの優れた汎用ソート アルゴリズムの 1 つを使用し、必要に応じてリストとの間で変換するラッパーを使用することが、大きなリストをソートするための推奨される方法です。(これらのアルゴリズムは、ボックス化されたベクトルでもうまく機能します。私の測定では、ボックス化されていないものよりも約 50% 遅くなります。) 短いリストの場合、変換のオーバーヘッドが非常に大きくなるため、コストがかかりません。
さて、@applicative の提案で、vector-algorithmsのイントロソート、ボックス化されていないベクトルのクイックソート、s の改良された (恥知らずに の実装を盗むunstablePartition) クイックソートのソート時間を見てみましょうSTUArray。
改良されたSTUArrayクイックソート:
{-# LANGUAGE BangPatterns #-}
module NQuick (stuqsort) where
import Data.Array.Base (unsafeRead, unsafeWrite, getNumElements)
import Data.Array.ST
import Control.Monad.ST
import Control.Monad (when)
stuqsort :: STUArray s Int Int -> ST s ()
stuqsort arr = do
n <- getNumElements arr
when (n > 1) (myqsort arr 0 (n-1))
myqsort :: STUArray s Int Int -> Int -> Int -> ST s ()
myqsort a lo hi = do
p <- unsafeRead a hi
j <- unstablePartition (< p) lo hi a
h <- unsafeRead a j
unsafeWrite a j p
unsafeWrite a hi h
when (j > lo+1) (myqsort a lo (j-1))
when (j+1 < hi) (myqsort a (j+1) hi)
unstablePartition :: (Int -> Bool) -> Int -> Int -> STUArray s Int Int -> ST s Int
{-# INLINE unstablePartition #-}
unstablePartition f !lf !rg !v = from_left lf rg
where
from_left i j
| i == j = return i
| otherwise = do
x <- unsafeRead v i
if f x
then from_left (i+1) j
else from_right i (j-1)
from_right i j
| i == j = return i
| otherwise = do
x <- unsafeRead v j
if f x
then do
y <- unsafeRead v i
unsafeWrite v i x
unsafeWrite v j y
from_left (i+1) j
else from_right i (j-1)
ベクトルのクイックソート:
module VectorQuick (vquicksort) where
import qualified Data.Vector.Unboxed.Mutable as UM
import qualified Data.Vector.Generic.Mutable as GM
import Control.Monad.ST
import Control.Monad (when)
vquicksort :: UM.STVector s Int -> ST s ()
vquicksort uv = do
let li = UM.length uv - 1
ui = UM.unsafeSlice 0 li uv
p <- UM.unsafeRead uv li
j <- GM.unstablePartition (< p) ui
h <- UM.unsafeRead uv j
UM.unsafeWrite uv j p
UM.unsafeWrite uv li h
when (j > 1) (vquicksort (UM.unsafeSlice 0 j uv))
when (j + 1 < li) (vquicksort (UM.unsafeSlice (j+1) (li-j) uv))
タイミングコード:
{-# LANGUAGE BangPatterns #-}
module Main (main) where
import System.Environment (getArgs)
import System.CPUTime
import System.Random
import Text.Printf
import Data.Array.Unboxed
import Data.Array.ST hiding (unsafeThaw)
import Data.Array.Unsafe (unsafeThaw)
import Data.Array.Base (unsafeAt, unsafeNewArray_, unsafeWrite)
import Control.Monad.ST
import Control.Monad
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Mutable as UM
import NQuick
import VectorQuick
import qualified Data.Vector.Algorithms.Intro as I
nextR :: StdGen -> (Int, StdGen)
nextR = randomR (minBound, maxBound)
buildArray :: StdGen -> Int -> UArray Int Int
buildArray sg size = runSTUArray (do
arr <- unsafeNewArray_ (0, size-1)
let fill i g
| i < size = do
let (r, g') = nextR g
unsafeWrite arr i r
fill (i+1) g'
| otherwise = return arr
fill 0 sg)
buildVector :: StdGen -> Int -> U.Vector Int
buildVector sg size = U.fromList $ take size (randoms sg)
time :: IO a -> IO ()
time action = do
t0 <- getCPUTime
action
t1 <- getCPUTime
let tm :: Double
tm = fromInteger (t1 - t0) * 1e-9
printf "%.3f ms\n" tm
stu :: UArray Int Int -> Int -> IO ()
stu ua sz = do
let !sa = runSTUArray (do
st <- unsafeThaw ua
stuqsort st
return st)
forM_ [0, sz `quot` 2, sz-1] (print . (sa `unsafeAt`))
intro :: U.Vector Int -> Int -> IO ()
intro uv sz = do
let !sv = runST (do
st <- U.unsafeThaw uv
I.sort st
U.unsafeFreeze st)
forM_ [0, sz `quot` 2, sz-1] (print . U.unsafeIndex sv)
vquick :: U.Vector Int -> Int -> IO ()
vquick uv sz = do
let !sv = runST (do
st <- U.unsafeThaw uv
vquicksort st
U.unsafeFreeze st)
forM_ [0, sz `quot` 2, sz-1] (print . U.unsafeIndex sv)
main :: IO ()
main = do
args <- getArgs
let !num = case args of
(a:_) -> read a
_ -> 1000000
!sg <- getStdGen
let !ar = buildArray sg num
!vc = buildVector sg num
!v2 = buildVector sg (foo num)
algos = [ ("Intro", intro v2), ("STUArray", stu ar), ("Vquick", vquick vc) ]
printf "Created data to be sorted, last elements %d %d %d\n" (ar ! (num-1)) (vc U.! (num-1)) (v2 U.! (num-1))
forM_ algos $ \(name, act) -> do
putStrLn name
time (act num)
-- For the prevention of sharing
foo :: Int -> Int
foo n
| n < 0 = -n
| n > 0 = n
| otherwise = 3
結果（回のみ）：
$ ./timeSorts 3000000
Intro
587.911 ms
STUArray
402.939 ms
Vquick
414.936 ms
$ ./timeSorts 1000000
Intro
193.970 ms
STUArray
131.980 ms
Vquick
134.979 ms
およびボックス化されていないベクトルでの実質的に同一のクイックソートは、STUArray予想どおり、実質的に同じ時間がかかります。(古いクイックソートの実装は、イントロソートよりも約 15% 遅くなりました。上記の時間と比較すると、リストから/への変換に約 70-75% が費やされました。)
ランダムな入力では、クイックソートはイントロソートよりもはるかに優れたパフォーマンスを発揮しますが、ほぼソートされた入力では、イントロソートではパフォーマンスが低下しますが、パフォーマンスは低下しません。
¹ s でコードをポリモーフィックにするSTUArrayのはせいぜい面倒です。IOUArray{-# INLINABLE #-}
² 同じアルゴリズムを使用して比較した場合、どちらも測定精度の範囲内で常に同等に高速でした (それほど頻繁ではありません)。