スポンサーサイト

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

[Haskell]正格化バブルソート

なぜだか、バブルソートを正格化しただけで、100倍程度のオーダーで効率が上昇しました。
Haskellが細かい高速化に向かない言語だとは知っていますが、
うーん。理由がよくわからないです。
簡約化を手で行って考えて見ようかな。

以下、実行コード

import System.Random
import System.CPUTime
import Data.Array.IO

-- バブルソート
bubbleSort :: [Int] -> [Int]
bubbleSort [] = []
bubbleSort ls = (iterate f ls) !! length ls
where
f [x] = [x]
f (x:y:ys) | x <= y = x:f (y:ys)
| otherwise = y:f (x:ys)

f ::[Int] -> IO()
f ln = do
-- print $ ln
s <- getCPUTime
let a = seq bubbleSort ln
print $ last a
e <- getCPUTime
print $ (e-s)`quot`1000000


f2 :: [Int] -> IO()
f2 ln = do
-- print $ ln
s <- getCPUTime
let a = bubbleSort ln
print $ last a
e <- getCPUTime
print $ (e-s)`quot`1000000


size = 5000 ::Int
main = do
a <- getStdGen
let b = take size $ randomRs (1,size) a
putStrLn "f"
f $ b
putStrLn "f"
f2 $ b

putChar '\n'


正格化しただけで、速くなる理由がよくわからん。
誰か知ってる方教えてくれー。
スポンサーサイト

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

コメントの投稿

非公開コメント

seq bubbleSort ln == ln

ソートしていなかったというオチ。

意図的には
a `seq` print (last a)
(あるいは print . last $! a)
が正しいのでしょうけど、
sortの過程が変わるわけでもないので、
速くなることはないと思います。
プロフィール

かみさまみならい

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

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

この人とブロともになる

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