« Haskell で行列の計算をしてみる | トップページ | Project Euler : Problem 59 ~ 暗号解読 »

2011年2月23日 (水)

基数ソート

 こちらのブログを見て知ったのですが、「基数ソート」というソート法があるんですね。
 面白そうだったので、 Wikipedia を参考に自分でもコードを書いてみました。(基本方針は、Wikipedia に従って、バケットソートと組み合せることにしました。また、ソートする要素は十進数の整数に限定しました)

 バケットソートに関して二通りの実装を思いついたのですが、まずはタイピング量が少いほうから……。

import Data.List (replicate) radixSort1 :: Integral a => [a] -> [a] radixSort1 xs = loop 1 xs where maxData = maximum xs loop d xs | d > maxData = xs | otherwise = loop (d * 10) $ bucketSort d xs $ replicate 10 [] bucketSort _ [] yss = concatMap reverse yss bucketSort d (x : xs) yss = bucketSort d xs $ ass ++ (x : bs) : bss where i = fromIntegral (rem (div x d) 10) (ass, bs : bss) = splitAt i yss
 試しに 0 〜 999 の範囲の数がランダムに 15000 個入っているリストをソートさせてから合計を求めさせたら、「Core2 Quad, 2.83GHz, Windows 7」という環境で
>ghc -O -o radixSort1 radixSort1.hs --make ghc -O -o radixSort1 radixSort1.hs --make Linking radixSort1.exe ... >radixSort1 +RTS -sstderr radixSort1 +RTS -sstderr radixSort1 +RTS -sstderr 7418991 24,968,552 bytes allocated in the heap 5,379,064 bytes copied during GC 695,808 bytes maximum residency (6 sample(s)) 25,708 bytes maximum slop 3 MB total memory in use (0 MB lost due to fragmentation) Generation 0: 40 collections, 0 parallel, 0.02s, 0.02s elapsed Generation 1: 6 collections, 0 parallel, 0.00s, 0.00s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 0.02s ( 0.02s elapsed) GC time 0.02s ( 0.02s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 0.03s ( 0.04s elapsed) %GC time 50.0% (57.9% elapsed) Alloc rate 1,600,548,205 bytes per MUT second Productivity 50.0% of total user, 41.0% of total elapsed
という結果になりました。
 「あまり速くないのでは?」と思っていたのですが、以前書いた記事の「クイックソート」や「マージソート」に迫る速さだったので、ビックリしました。
 ただ、"ass ++ (x : bs) : bss" といったところや、"(ass, bs : bss) = splitAt i yss" といったところで頻繁にリスト操作が行われているので、これをなんとかすればもっと速くなる可能性があります。

 そこで、冗長なバージョンのバケットソートを試してみました。

radixSort2 :: Integral a => [a] -> [a] radixSort2 xs = loop 1 xs where maxData = maximum xs loop d xs | d > maxData = xs | otherwise = loop (d * 10) $ bucketSort d xs [] [] [] [] [] [] [] [] [] [] bucketSort _ [] ys0 ys1 ys2 ys3 ys4 ys5 ys6 ys7 ys8 ys9 = concatMap reverse [ys0, ys1, ys2, ys3, ys4, ys5, ys6, ys7, ys8, ys9] bucketSort d (x : xs) ys0 ys1 ys2 ys3 ys4 ys5 ys6 ys7 ys8 ys9 | y == 0 = bucketSort d xs (x : ys0) ys1 ys2 ys3 ys4 ys5 ys6 ys7 ys8 ys9 | y == 1 = bucketSort d xs ys0 (x : ys1) ys2 ys3 ys4 ys5 ys6 ys7 ys8 ys9 | y == 2 = bucketSort d xs ys0 ys1 (x : ys2) ys3 ys4 ys5 ys6 ys7 ys8 ys9 | y == 3 = bucketSort d xs ys0 ys1 ys2 (x : ys3) ys4 ys5 ys6 ys7 ys8 ys9 | y == 4 = bucketSort d xs ys0 ys1 ys2 ys3 (x : ys4) ys5 ys6 ys7 ys8 ys9 | y == 5 = bucketSort d xs ys0 ys1 ys2 ys3 ys4 (x : ys5) ys6 ys7 ys8 ys9 | y == 6 = bucketSort d xs ys0 ys1 ys2 ys3 ys4 ys5 (x : ys6) ys7 ys8 ys9 | y == 7 = bucketSort d xs ys0 ys1 ys2 ys3 ys4 ys5 ys6 (x : ys7) ys8 ys9 | y == 8 = bucketSort d xs ys0 ys1 ys2 ys3 ys4 ys5 ys6 ys7 (x : ys8) ys9 | y == 9 = bucketSort d xs ys0 ys1 ys2 ys3 ys4 ys5 ys6 ys7 ys8 (x : ys9) where y = rem (div x d) 10
 いや〜ひどいですね。"y == ..." が 10 個も並んでいます。
 こちらも "radixSort1.hs" と同様のテストをしてみました。
>ghc -O -o radixSort2 radixSort2.hs --make ghc -O -o radixSort2 radixSort2.hs --make Linking radixSort2.exe ... >radixSort2 +RTS -sstderr radixSort2 +RTS -sstderr radixSort2 +RTS -sstderr 7418991 3,834,816 bytes allocated in the heap 1,103,176 bytes copied during GC 123,072 bytes maximum residency (1 sample(s)) 19,984 bytes maximum slop 2 MB total memory in use (0 MB lost due to fragmentation) Generation 0: 7 collections, 0 parallel, 0.00s, 0.00s elapsed Generation 1: 1 collections, 0 parallel, 0.00s, 0.00s elapsed INIT time 0.00s ( 0.00s elapsed) MUT time 0.00s ( 0.01s elapsed) GC time 0.00s ( 0.00s elapsed) EXIT time 0.00s ( 0.00s elapsed) Total time 0.00s ( 0.01s elapsed) %GC time 0.0% (11.1% elapsed) Alloc rate 3834,816,000,000 bytes per MUT second Productivity 100.0% of total user, 0.0% of total elapsed
 なんとこちらは、私の書いた「クイックソート」や「マージソート」より速くなってしまいました。

 ソートする要素の桁数が増えれば、その分「基数ソート」は時間がかかります。そのためソートする要素を選ぶソート法かもしれませんが、ツボに嵌れば強力なソート法だということが分りました。

« Haskell で行列の計算をしてみる | トップページ | Project Euler : Problem 59 ~ 暗号解読 »

Haskell」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/50946648

この記事へのトラックバック一覧です: 基数ソート:

« Haskell で行列の計算をしてみる | トップページ | Project Euler : Problem 59 ~ 暗号解読 »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ