スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

[Haskell]バブルソート(ArrayIO)

ArrayIOでバブルソートを作ってみた。
以前作ったバブルソート
バブルソート、挿入ソート
と比べると10倍以上遅い。
うーん。なんでだー、遅延評価か。それともモナドを使っていることが理由なのか、
これはボトルネックを調べてみる必要がありますね。

-- バブルソートArrayIO
bubbleSortArray :: [Int] -> IO [Int]
bubbleSortArray ls = do an <- newListArray (0::Int,length ls) ls :: IO (IOUArray Int Int)
bubble' 0 an >>= getElems

where
bubble' :: Int -> IOUArray Int Int -> IO(IOUArray Int Int)
bubble'':: Int -> IOUArray Int Int -> IO(IOUArray Int Int)
swap :: Int -> IOUArray Int Int -> IO(IOUArray Int Int)
--

bubble' m ls = do (mini,max) <- getBounds ls
a <- bubble'' 0 ls
if m + 1 >= max then
return ls
else
bubble' (m+1) a >>= return
--

bubble'' m ls = do (mini,max) <- getBounds ls
a <- swap m ls
if m + 1 >= max then
return ls
else
bubble'' (m+1) a >>= return
--
swap m ls = do x <- readArray ls m
y <- readArray ls $ m+1
if x <= y then
return ls
else
do
writeArray ls m y
writeArray ls (m+1) x
return ls
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

bubbleSortArray ls = do
a <- newListArray (1,s) ls :: IO (IOUArray Int Int)
sequence_ [swap a j | i<-[s-1,s-2..1], j<-[1..i]]
getElems a
where s = length ls

swap a m = do
x <- readArray a m
y <- readArray a (m+1)
when (x > y) $ do
writeArray a m y
writeArray a (m+1) x

私の環境では-Oでコンパイルすると配列版のほうが速かったです。
リストに比べて配列を使って速くなるのは、
要素にランダムアクセスする場合などであって、
この場合は特に配列のほうが速い理由は無いですよね。
遅いのはモナドや遅延評価のせいではなく、
インタプリタだと配列のほうがオーバーヘッドが大きかったのでしょう。

あ、when は Control.Monad にあります。蛇足

>私の環境では-Oでコンパイルすると配列版のほうが速かったです。

多分私のコードの組み方が悪かっただけかと。


実行環境は
GHC V.6.8.2コンパイルオプションなし。
Windows Vista
でコンパイル実行しています。
プロフィール

かみさまみならい

Author:かみさまみならい
FC2ブログへようこそ!

最近の記事
最近のコメント
最近のトラックバック
月別アーカイブ
カテゴリー
ブロとも申請フォーム

この人とブロともになる

ブログ内検索
RSSフィード
リンク
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。