Haskell - 探索とソート(線形検索と二分探索、Data.Listモジュール(sort関数))

すごいHaskellたのしく学ぼう!
(オーム社)
Miran Lipovača (著)
田中 英行 村主 崇行 (翻訳)
[Kindle版]

開発環境

• OS X Mavericks - Apple(OS)
• BBEdit - Bare Bones Software, Inc., Emacs (Text Editor)
• Haskell (純粋関数型プログラミング言語)
• GHC (The Glasgow Haskell Compiler) (処理系)
• The Haskell Platform (インストール方法、モジュール等)

初めてのコンピュータサイエンス(Jennifer Campbell、Paul Gries、Jason Montojo、Greg Wilson(著)長尾 高弘(翻訳))の11章(探索とソート)、11.7(練習問題)、11-1.をHaskellで解いてみる。

その他参考書籍

• プログラミングHaskell (オーム社) Graham Hutton(著) 山本 和彦(翻訳)
• Real World Haskell―実戦で学ぶ関数型言語プログラミング (オライリージャパン) Bryan O'Sullivan John Goerzen Don Stewart(著) 山下 伸夫 伊東 勝利 株式会社タイムインターメディア(翻訳)

11.7(練習問題)、11-1.

線形検索と二分検索を比較。

線形探索(linear search)

コード(BBEdit)

Sample.hs

{-# OPTIONS -Wall -Werror #-}
import System.Random

main :: IO ()
main = loop 40

loop :: Int -> IO ()
loop 0 = putChar '\n'
loop m = do
    putStr $ show $ mySearch m ns
    putChar ' '
    loop (m - 1)

num :: Int
num = 1000000

ns :: [Int]
ns = take num $ randomRs (0, num) $ mkStdGen 1

mySearch :: (Ord a) => a -> [a] -> Int
mySearch = inner 0

inner :: (Ord a) => Int -> a -> [a] -> Int
inner _ _ [] = -1
inner a x (y:ys) = if x == y then a else inner (a + 1) x ys

二分探索(binary search)

コード(BBEdit)

Binsearch.hs

{-# OPTIONS -Wall -Werror #-}
import System.Random
import qualified Data.List as List

main :: IO ()
main = loop 40

loop :: Int -> IO ()
loop 0 = putChar '\n'
loop m = do
    putStr $ show $ binSearch m ns
    putChar ' '
    loop (m - 1)

num :: Int
num = 1000000

ns :: [Int]
ns = List.sort $ take num $ randomRs (0, num) $ mkStdGen 1

binSearch :: (Ord a) => a -> [a] -> Int
binSearch x xs = inner 0 (length xs - 1) x xs

inner :: (Ord a) => Int -> Int -> a -> [a]  -> Int
inner n m x xs | n /= m + 1 = let i = div (m + n) 2
                             in if xs !! i < x then
                                    inner (i + 1) m x xs
                                else
                                    inner n (i -1) x xs
               | otherwise = if 0 <= n && n < length xs && xs !! n == x then
                                  n
                              else
                                  -1

入出力結果(Terminal, runghc)

$ time runghc Sample.hs
512595 594325 -1 55221 -1 -1 -1 -1 241463 109789 -1 -1 -1 94947 -1 997239 -1 525806 -1 925200 577379 349597 -1 892952 -1 -1 189654 -1 924978 327928 101678 24363 -1 414671 -1 124187 -1 -1 542774 129474 

real 0m49.137s
user 0m47.843s
sys 0m0.545s
$ time runghc Binsearch.hs
32 31 -1 29 -1 -1 -1 -1 28 25 -1 -1 -1 24 -1 23 -1 22 -1 21 20 18 -1 16 -1 -1 15 -1 14 13 11 10 -1 8 -1 4 -1 -1 2 1 

real 0m7.680s
user 0m7.323s
sys 0m0.254s
$

慣れるまでは{-# OPTIONS -Wall -Werror #-}の記述を消さずに細かく型を指定していくことに。