最小自由数とHaskell
「おはよう」
どうも。ゾディアックです。
最近は禁煙しまして、お酒が好きになりました。
やはり、神は二物を与えないということですね。
全く以て欲張りには生きにくい世界であります。
ああ、そういえば最近ドストエフスキーの「賭博者」を読了致しまして、
人の性質というか、破滅に落ちていく其れに抗えない、何か切ないというか、
ジーザスって感じです。おお！神よ！お赦しください...
はい。今はウィリアム・ギブスンの「ニューロマンサー」を読んでいます。
有名なやつです。いろいろ賞とか取ってる。SFのやつ。
ドストエフスキーを読んでから、まあ、悪い気分というわけではなかったんですが、
暗い気持ちになってしまったので、愉快になりたいなと思ったんで、このチョイスです(?)。
そろそろ本題に入りたいネ。
「お前何した」
ついにとうとうやっと「関数プログラミング珠玉のアルゴリズムデザイン」を読み始めたんです。
この本で出てくる関数型言語はHaskellなんです(なにそれ？って聞くのはナシで)。
一年ほど前なんて、Haskell好き好き言っときながら、全く書けなかったし、
この本も、ページをめくっては「ヤバイ」とか言うだけでした。
そう。俺は成長してるのよ。
で、この本の第一章「最小自由数」に関して書く。
「最小自由数」
最小自由数ってのは、簡単に言うと、与えられた自然数の有限集合に含まれない最小の自然数のことです。
[3,5,2,9]だったら"0"が求めるべき最小自由数です。
この集合の中では"2"が最小の自然数でありますが、
この中に含まれない最小の自然数であるところの、
この場合"0"が最小自由数というわけです。
[2,0,4,3]でしたら最小自由数は"1"です。
これをできるだけ速く求めたいんですね。ここではそういうアルゴリズムと実装を考えるんです。
「配列を用いる方法」
もう正直眠いし、めんどくさいんで、本当に軽く説明させて頂きます。
その考えに行き着いた経緯的なのとか省きます。本買って読みましょう。高いけど。
引数はリストですが、リスト受け取ってその長さ分の配列を作ります。
有るor無いをBoolで表します。
配列のFalseで一番小さい数を答え(最小自由数)として出します。
以下がコード。
import Data.Array import Data.Array.ST search = length . takeWhile id . elems checklist xs = runSTArray (do {a <- newArray (0,n) False; sequence [writeArray a x True | x <- xs, x <= n]; return a}) where n = length xs minfree = search . checklist
配列作った後に変えるのでStateモナドでモナります。
配列の長さより大きい数は無視します。あったらTrueで書き込み。
saerch関数はTrueの続く要素を取り出していって、最終的にその取り出した個数を返します(これが最小自由数と一致する)。
minfree [〜〜〜]みたいな感じで使います。ghciとか使ってロードして試してみましょう。
「分割統治法を用いる」
分割統治法っていうのは簡単に言うとアレです。
全部やると面倒い問題を分割して小さくして小さい方を解くみたいな感じではないでしょうか。
以下がコード。
import Data.List minfrom a (n,xs) | n == 0 = a | m == b-a = minfrom b (n-m,vs) | otherwise = minfrom a (m,us) where (us,vs) = partition (<b) xs b = a + 1 + n `div` 2 m = length us minfree xs = minfrom 0 (length xs,xs)
再帰ですね。
ガード記法、惚れ惚れしますね相変わらず。
whereは局所定義っていうんですが、partition (条件) で、
([条件を満たすリスト],[条件を満たさないリスト])で分け、これが(us,vs)に対応して定義されます。
リストを与えられた値よりも小さいものとそうでないものに分割しています。
まぁ、プログラム見ていただければ""削ってる""ってのは分かって頂けると思います。
このプログラムは先程のものより20%速いそうです。本にそう書いてありますし。
なんか適当ですみません。なげやり過ぎますね(時間があったら加筆してもいいなとは思ってる)。
ではありがとうございました。おやすみなさい。
ではでは。
