#78 アルゴリズムたいそう!

この記事は F# Advent Calendar jp: 20101315回目です。

F#の事について書こうと思い、そういえば私のブログで一番取り上げてきたトピックは何だろうと振り返ってみました。
そこで浮かんできたのが、次の2点でした。
・アルゴリズムの実装
・処理時間の性能評価

書くならやっぱり自分の書きやすいものだろうと言うことで、今回は
F#でソートアルゴリズムを実装し、処理時間を測定してみる
ことにします(`・ω・´)

なお処理時間の測定には、これまで実績のある以下のコードを利用します。
open System
let beginTime = DateTime.Now;;
let result = "hoge";;  (* ここに処理を書きます *)
let ts = DateTime.Now.Subtract(beginTime);;
printfn "経過時間:%A[ms]" ts.TotalMilliseconds;;

また、統一した仕様としては、int listへの昇順整列操作であることとして、測定には以下のリストを使用します。
let lsSmall = [1;3;5;7;9;2;4;6;8];;
let lsMidAndDup = [10;3;14;13;5;1;11;9;2;5;15;10;4;12;6;8;16;7];;
let rm = new Random(DateTime.Now.Millisecond);;
let lsLarge = List.init 1000 (fun x -> rm.Next());;
let lsLarger = List.init 10000 (fun x -> rm.Next());;
let lsLargest = List.init 100000 (fun x -> rm.Next());;



1. バブルソート


今から20年前に日本で流行った整列アルゴリズム、ではありません。
(く、くるしい!?)

バブルソート - Wikipedia
(以下、横着をして書くソートの説明はWikipediaにお任せしますw)

これをF#で次のように書いてみました。
let bubblesort (ls: int list) =
    let rec countBS lis rest =
        let rec innerBubbleSort lst =
            match lst with
            | x::xs ->
                match xs with
                | y::ys ->
                    if x > y
                        then [y] @ (innerBubbleSort ([x] @ ys))
                        else [x] @ (innerBubbleSort xs)
                | [] -> lst
            | [] -> lst
        in
        if rest > 0
            then countBS (innerBubbleSort lis) (rest-1)
            else lis
    in
    countBS ls (ls.Length-1);;
とりあえず、動きを見てみましょう。
> let ls = lsSmall;;

val ls = [1; 3; 5; 7; 9; 2; 4; 6; 8]

> let beginTime = DateTime.Now;;

val beginTime :  = 2010/12/20 16:14:50

> let bubbleSorted = bubblesort ls;;

val bubbleSorted : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]

> let ts = DateTime.Now.Subtract(beginTime);;

val ts : TimeSpan = 00:00:00.0468750

> printfn "経過時間:%A[ms]" ts.TotalMilliseconds;;
経過時間:46.875[ms]
val it : unit = ()
>
まぁ、こんなものでしょうか。



2. 選択ソート


選択ソート - Wikipedia

2番目は選択ソートです。
以下のように書いてみました。
let rec selectionsort ls =
    match ls with
    | [] -> ls
    | _ ->
        let min = List.min ls
        in
        (List.filter (fun x -> x = min) ls) @ (selectionsort (List.filter (fun x -> x > min) ls));;
実行してみます。
> let ls = lsSmall;;

val ls = [1; 3; 5; 7; 9; 2; 4; 6; 8]

> let beginTime = DateTime.Now;;

val beginTime :  = 2010/12/20 16:24:42

> let selectionSorted = selectionsort ls;;

val selectionSorted : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]

> let ts = DateTime.Now.Subtract(beginTime);;

val ts : TimeSpan = 00:00:00.0312500

> printfn "経過時間:%A[ms]" ts.TotalMilliseconds;;
経過時間:31.25[ms]
val it : unit = ()
>
これも、まぁこんなものかと言う結果ですね。
ここまで、ソートは正しくできているので、ひとまず良しでしょうか。



3. 挿入ソート


挿入ソートの説明はこちら↓
挿入ソート - Wikipedia

私が書いたコードはこちら↓(だんだんやっつけになってきたw)
let insertionsort ls =
    let rec insertionMain sls nls =
        match nls with
        | x::xs ->
            let rec insert_into_index ix e =
                match ix with
                | h::tl ->
                    if e <= h
                        then e::h::tl
                        else h::(insert_into_index tl e)
                | _ -> [e]
            in
            insertionMain (insert_into_index sls x) xs
        | _ -> sls @ []
    in
    insertionMain [] ls;;
よくよくコードを見渡すと、パターンマッチのdefaultに指定しているものが空のリスト([])だったり、任意(_)だったりしますね。
このあたりに、作者の思想に対する一貫性が問われそうですw

動きを確認します。
> let ls = lsSmall;;

val ls = [1; 3; 5; 7; 9; 2; 4; 6; 8]

> let beginTime = DateTime.Now;;

val beginTime :  = 2010/12/20 16:39:44

> let insertionSorted = insertionsort ls;;

val insertionSorted : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]

> let ts = DateTime.Now.Subtract(beginTime);;

val ts : TimeSpan = 00:00:00.0468750

> printfn "経過時間:%A[ms]" ts.TotalMilliseconds;;
経過時間:46.875[ms]
val it : unit = ()
>
まぁ、コメントに困ると言いますかw
まぁ、気にせず行きましょう。

4. クイックソート


クイックソート - Wikipedia

本トピックの真打ちです(`・ω・´)
2種類のコードを見てみます。
let rec quicksort ls =
    match ls with
    | x::xs -> quicksort (List.filter (fun a -> (a < x)) xs) @ (x::(quicksort (List.filter (fun a -> (a >= x)) xs)))
    | _ -> [];;

let rec quicksort2 ls =
    match ls with
    | x::xs ->
        let rec pivotSort pivot small large organ =
            match organ with
            | h::tl ->
                if pivot > h
                    then pivotSort pivot (h::small) large tl
                    else pivotSort pivot small (h::large) tl
            | _ -> (quicksort2 small) @ (pivot::(quicksort2 large))
        in
        pivotSort x [] [] xs
    | _ -> ls;;
前者のコードは、次のページに書かれているLispのコードを、F#に書き直したものです。
The Beauty of a Lisp Quicksort - swisspig.net

実は本トピックのモチベーションとして、「このクイックソートのコードをF#に書き直してみようか」というところから始まっているのです。
で、このページ内で『とても簡潔でエレガントな、あるHaskellのコードからモチベーションを得て…』というところがあったのですが、どうやら第6回にてsandinistさんが書いたトピックにも同様の記載がありました。
…こりゃネタが被ったかな、と冷や汗が出ましたw

なお後者のコードは、Wikipediaの説明を詳細設計に見立てて書き上げたものです。
こっちが私のオリジナルというわけですが、さすがに前者のコードと比べると書いてある量が多いですね(^_^;)

では、それぞれ動作確認をしてみましょう。
> let ls = lsSmall;;

val ls = [1; 3; 5; 7; 9; 2; 4; 6; 8]

> let beginTime = DateTime.Now;;

val beginTime :  = 2010/12/20 16:58:27

> let quickSorted = quicksort ls;;

val quickSorted : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]

> let ts = DateTime.Now.Subtract(beginTime);;

val ts : TimeSpan = 00:00:00.0468750

> printfn "経過時間:%A[ms]" ts.TotalMilliseconds;;
経過時間:46.875[ms]
val it : unit = ()
>
> let ls = lsSmall;;

val ls = [1; 3; 5; 7; 9; 2; 4; 6; 8]

> let beginTime = DateTime.Now;;

val beginTime :  = 2010/12/20 17:02:18

> let quickSorted2 = quicksort2 ls;;

val quickSorted2 : int list = [1; 2; 3; 4; 5; 6; 7; 8; 9]

> let ts = DateTime.Now.Subtract(beginTime);;

val ts : TimeSpan = 00:00:00.0468750

> printfn "経過時間:%A[ms]" ts.TotalMilliseconds;;
経過時間:46.875[ms]
val it : unit = ()
>



5. 処理時間測定


とりあえず、全部ちゃんと動いているようです。
ここから先は、ソート対象をlsSmallから、lsMidAndDup、lsLarge、lsLarger、lsLargestまでそれぞれ5回ずつ実行して、最大、最小、平均時間を求めてみます。
(単位はすべてミリ秒)
lsSmall bubblesort selectionsort insertionsort quicksort quicksort2
max 62.5 46.875 46.875 46.875 46.875
min 31.25 15.625 31.25 31.25 31.25
avg 46.875 31.25 43.75 40.625 43.75


lsMidAndDup bubblesort selectionsort insertionsort quicksort quicksort2
max 62.5 62.5 46.875 62.5 46.875
min 46.875 31.25 46.875 46.875 31.25
avg 53.125 40.625 46.875 53.125 43.75


lsLarge bubblesort selectionsort insertionsort quicksort quicksort2
max 406.25 390.625 156.25 93.75 93.75
min 343.75 375.0 125.0 93.75 93.75
avg 381.25 378.125 140.625 93.75 93.75


lsLarger bubblesort selectionsort insertionsort quicksort quicksort2
max 39234.375 37968.75 6265.625 187.5 140.625
min 38421.875 37906.25 6140.625 156.25 109.375
avg 38787.5 37925.0 6200.0 165.625 125.0


lsLargest bubblesort selectionsort insertionsort quicksort quicksort2
max *** *** *** 1234.375 750.0
min *** *** *** 1156.25 640.625
avg *** *** *** 1181.25 681.25

リストのサイズが小さいウチはドングリの背比べですが、リストが巨大になってくるにつれて差が開いてきました。
バブルソート、選択ソート、挿入ソートでは、最大のリスト(10万件)のソート中にStackOverflowExceptionが発生し、測定さえできない状況。
その中で、クイックソートの2つは強さを見せつける結果となりましたね。

何が嬉しかったかって、ガブ・オリジナルの方が多少速かったことです(*´ー`)


ちなみに、調子に乗って神に唾吐くとこうなります。
lsLargest List.sort
max 109.375
min 93.75
avg 103.125

とても勝負になりませんw



今回のトピックは以上です。
F#は記述の効率化や高速化を進め、ソースコード全体の見通しをよくしやすい言語です。
皆さんも、実現させたいアルゴリズムを短いコードでさっと書けるF#と、もっともっと遊んで上げてください。

トラックバックURL

#78 アルゴリズムたいそう! へのトラックバック

まだトラックバックはありません。

#78 アルゴリズムたいそう! へのコメント一覧

  1. 1.
    • のぶひさ
    • 2010年12月27日 02:12
    • 5
    FsAdventJPご参加ありがとうございました!

    時間の計測ですが、.NETにはStopwatch( http://msdn.microsoft.com/ja-jp/library/system.diagnostics.stopwatch.aspx )クラスなんていうステキなものも用意されています。

    また、F#は末尾再帰関数を最適化してくれるので、末尾再帰で書くとより高速に、そしてオーバーフローを起こさないソートが書けますよ。
    末尾再帰については・・・おっと、実践F#に解説がありますね。グッドタイミングですね。(露骨な宣伝
  2. 2.
    • Gab_km
    • 2010年12月28日 00:19
    >のぶひささん
    コメントありがとうございます^^

    Stopwatchクラスは寡聞にして知りませんでした。
    これがあれば、今後の処理時間トピックの測定も楽になりそうですね。

    末尾再帰は、なるだけそうなるように書こうとはしていたんですが、私の実力不足でソートアルゴリズムに適用しきれませんでした(汗)
    まぁ、そこは「何だ、これなら私がもっと良いの書いてやるぜ!」という次代のF#erに期待しますww

コメントする

#78 アルゴリズムたいそう! にコメントする
絵文字
プロフィール
あわせて読みたい
あわせて読みたい
記事検索
Project Euler
なかのひと
アクセス解析
Coderwall
  • ライブドアブログ

トップに戻る