スポンサーサイト

上記の広告は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'


続きを読む

スポンサーサイト

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

[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

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

[Haskell]選択ソート、クイックソート

ソートの練習の続き、
クイックソートはそこらへんのを書き写しだだけですけども。
実装見るとHaskellだと分かりやすいと思う。
選択ソートはHaskellだと分かりにくいです、もっと分かりやすい実装があるかも知れませんが、
私の能力ではこのへんが限界です。

-- 選択ソート
selectSort :: [Int] ->[Int]
selectSort [] = []
selectSort ls = minimum ls : (selectSort $ fill (minimum ls) ls)
where
fill:: Int -> [Int] -> [Int]
fill mini (x:ys) = if mini == x then ys
else x:fill mini ys

-- クイックソート
qsort [] = []
qsort(p:xs) = qsort lt ++ [p] ++ qsort gteq
where
lt = [x | x <- xs, x

gteq = [x | x <- xs, x>=p]

続きを読む

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

バブルソート、挿入ソート

ソートの練習中。
手続き型言語では簡単なのに、Haskellでは、結構組むのが大変です。


import System.Random

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)


incertSort :: [Int] -> [Int]
incertSort is = foldl f [] is
where
f :: [Int] -> Int -> [Int]
f [] x = x:[]
f (i:ys) j | i>= j = j:i:ys
| otherwise = i:(f ys j)

f ::[Int] -> IO()
f ln = do print ln
print $ incertSort ln

main = do a <- getStdGen
f $ take 10 $ randomRs (1,100) a
putChar '\n'

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

プロフィール

かみさまみならい

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

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

この人とブロともになる

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