マルコフ連鎖とビタビアルゴリズム(HMM)を F# で。
元ネタ
昼食時に店で流れていた、大事MANブラザーズバンド「それが大事」の歌詞が、あまりに繰り返しばかりなので、状態遷移図を作りました。どうぞご利用下さい。
http://youkoseki.com/soregadaiji/
「それが大事」にマルコフ連鎖を適用してみる
https://www.evernote.com/shard/s70/sh/71947f67-ee6c-405f-92a2-1d64fd631639/2d9397138827808cbc21c36c9389f642
マルコフ連鎖で「それが大事」っぽい歌詞を自動生成する
http://vilart.sakura.ne.jp/daijiman.html
自動生成された文字列が違和感なく連鎖するのがいいね！ネタのチョイスが面白くってちょっと書いてみたくなった。大事MANブラザーズバンドの大ヒット曲「それが大事」っぽい歌詞をマルコフ連鎖で自動生成。これを F# でやってみる。形態素解析には .NET で MeCabが簡単に使えるNMeCabを利用させてもらう。
open System open System.Collections.Generic open NMeCab open Microsoft.FSharp open Microsoft.FSharp.Core let tagger = MeCabTagger.Create () let parse format s = tagger.OutPutFormatType <- format tagger.Parse s let src = @"負けない事・投げ出さない事・逃げ出さない事・信じ抜く事 駄目になりそうな時 それが一番大事 負けない事・投げ出さない事・逃げ出さない事・信じ抜く事 涙見せてもいいよ それを忘れなければ Oh 高価な墓石を建てるより 安くても生きてる方がすばらしい ここにいるだけで 傷ついてる人はいるけど さんざん我侭言った後 あなたへの想いは 変わらないけど 見えてるやさしさに 時折負けそうになる ここにあなたがいないのが 淋しいのじゃなくて ここにあなたがいないと思う事が淋しい(でも) 負けない事・投げ出さない事・逃げ出さない事・信じ抜く事 駄目になりそうな時 それが一番大事 高価なニットをあげるより 下手でも手で編んだ方が美しい ここに無いものを 信じれるかどうかにある 今は遠くに離れてる それでも生きていれば いつかは逢える でも傷つかぬように 嘘は繰り返される ここにあなたがいないのが せつないのじゃなくて ここにあなたがいないと思う事がせつない でも 負けない事・投げ出さない事・逃げ出さない事・信じ抜く事 駄目になりそうな時 それが一番大事 負けない事・投げ出さない事・逃げ出さない事・信じ抜く事 駄目になりそうな時 それが一番大事 負けない事・投げ出さない事・逃げ出さない事・信じ抜く事 涙見せてもいいよ それを忘れなければ 負けない事・投げ出さない事・逃げ出さない事・信じ抜く事 駄目になりそうな時 それが一番大事 負けない事・投げ出さない事・逃げ出さない事・信じ抜く事 涙見せてもいいよ それを忘れなければ" // NMeCabで分かち書き let wakati s = if s = "" then [||] else let split separators x = (x:string).Split(separators) let wk = parse "wakati" s split [|' '|] wk |> Array.toList |> List.toArray // N階マルコフ let markov n source = let model = new Dictionary<_,_> () let add k (v:string) = if not <| model.ContainsKey k then model.Add(k,[]) model.[k] <- model.[k]@[v] let mutable p = Array.create n "" |> Array.toList for next in source do add (p) next p <- (List.tail p) @[next] let s = (List.tail p) |> List.reduce (fun x y -> x + y) let lst = (s).Replace("\r", "").Replace("\n", "") add (p@[lst]) null model // N階マルコフ連鎖で文章生成 let generateMarkovChain n first source = let random = new Random () let model = markov n source let keyValuePairs = (model.Keys :> seq<_>) let generate p = let sentence = fun p -> if model.ContainsKey(p) then let candidate = model.[p] let next = candidate.[random.Next (candidate.Length)] Some (next,(List.tail p)@[next]) else None Seq.unfold sentence p |> Seq.fold (fun a b -> a + b) "" first (keyValuePairs) |> generate wakati src |> generateMarkovChain 2 (fun keys -> keys |> Seq.head) |> fun s -> s.Replace ("\r","\r\n") |> printfn "%s" Console.ReadKey () |> ignore
元ネタと同じことができた。人工無能や twitter の bot を作る時なんかのたたき台くらいにはなりそう。やる予定ぜんぜんないけど。これといって見どころはありませんが、しいて言うなら単純マルコフ過程固定ではなく、N 階マルコフ過程な連鎖を表す関数にしてるところくらいでしょうか。で、好奇心がわいてきたのでなんとなーく関連情報をいろいろ漁っていく。すると、「マルコフ連鎖モンテカルロ法」、「隠れマルコフモデル」、「ビタビアルゴリズム」、「バウム・ウェルチアルゴリズム」などなどいろいろと面白そうなキーワードが出てくる。
マルコフ連鎖モンテカルロ法については、テラモナギさん(@teramonagi) のスライドがとても面白かった。
マルコフ連鎖モンテカルロ法入門−1
http://d.hatena.ne.jp/teramonagi/20100913/1284387360
マルコフ連鎖モンテカルロ法入門−２
http://d.hatena.ne.jp/teramonagi/20101003/1286079803
統計や機械学習については完全に門外漢であるし、いろいろとわからないことだらけの私だが。面白いものは面白い。
隠れマルコフモデルとビタビアルゴリズム
字が汚くて「尤度」って書こうとしても「犬度」になってしまう件。
2013-04-06 11:06:12 via web
@kos59125 どんな度合いなんだろう…
2013-04-06 11:30:14 via Janetter to @kos59125
@finalfusion わかりませんが対義語はおそらく猫度でしょう。
2013-04-06 11:31:32 via web to @finalfusion
@kos59125 なるほど
2013-04-06 11:37:30 via Janetter to @kos59125
尤度よりも犬度が。犬度よりも猫度が気になる今日このごろ。
遠くに住んでいる友達が、毎日何をしたかを電話で教えてくれます。友達は「散歩」、「買物」、「掃除」の３つのことにしか関心がありません。友達が住んでいるところの天気の明確な情報は持っていないが、友達が何をするかはその日の天気で決める傾向があることは知っている。たとえば「雨」だったら５０％の確率で「掃除」をするとか、「晴れ」だったら６０％の確率で「散歩」をするなどです。また、天気の状態は「雨」、「晴れ」のいずれかで、たとえば今日が雨だったら明日が晴れの確率は３０％、雨の確率は７０％という具合に、天気は離散マルコフ連鎖に従うとします。このとき、天気の状態は友達がする行動に隠れている(hidden)と見なすことができる。友達はその日の天気に従って「散歩」、「買い物」、「掃除」のいずれか１つだけ行動をとって教えてくれるので、これらは観測(observations)できる対象と見なせる。このとき、これは隠れマルコフモデル (HMM：Hidden Markov Model) 的である、と言う。
天気の傾向と、友達はどのような行動をとるかという傾向を知っているとき。言い換えると、隠れマルコフモデルのパラメータについて知っているということを意味していて、たとえば、友達が初日に散歩をして、２日目に買い物を。３日目に掃除を、というような順番に行動とったとき、その観測結果が得られる確率はいくらか？そして、このような観測結果がえられたとき３日間（とその翌日）の天気はどのようであったか？ということを予測したい。前者は前向きアルゴリズムを。後者はビタビアルゴリズム*1を用いることで求めることができる。
という内容の隠れマルコフモデルの例（コードはPython）がWikipediaに出ている。
隠れマルコフモデル - Wikipedia
http://goo.gl/oDu5k
ビタビアルゴリズム - Wikipedia
http://goo.gl/tbpnO
これを F# で書いてみる。
Program.fs
open HMM // 状態（ラベル）：雨 | 晴れ type States = Rainy | Sunny // 観測されたもの：散歩 | 買い物 | 掃除 type Observations = Walk | Shop | Clean // 初期確率 let startingProbs = [Rainy, 0.6; Sunny, 0.4] |> Map.ofList // 状態（ラベル）の遷移確率 let transitionProbs = [(Rainy,Rainy), 0.7; (Rainy,Sunny), 0.3 (Sunny,Rainy), 0.4; (Sunny,Sunny), 0.6] |> Map.ofSeq // それぞれの観測された行動に対する、状態（ラベル）の出力確率 let emissionProbs = [(Rainy, Walk), 0.1; (Rainy, Shop), 0.4; (Rainy, Clean), 0.5 (Sunny, Walk), 0.6; (Sunny, Shop), 0.3; (Sunny, Clean), 0.1] |> Map.ofSeq // 開始確率を取得します。 let startProbability s = startingProbs.[s] // 遷移確率を取得します。 let transitionProbability spair = transitionProbs.[spair] // 出力確率を取得します。 let emissionProbability sopair = emissionProbs.[sopair] let obs = [Walk; Shop; Clean] let states = [Rainy;Sunny] let viterbi = Viterbi(obs, states, startProbability, transitionProbability, emissionProbability) assert (viterbi.TotalProb = 0.0336) viterbi.TotalProb |> printfn "%A" assert (viterbi.ViterbiPath = [Sunny;Rainy;Rainy;Rainy]) viterbi.ViterbiPath |> printfn "%A" assert (viterbi.ViterbiProb = 0.009408) printfn "%A" viterbi.ViterbiProb
Viterbi.fs
namespace HMM open System type dict<'a, 'b> = Collections.Generic.Dictionary<'a,'b> [<AutoOpen>] module HMM = type Viterbi<'o,'s when 's:equality> ( obs : seq<'o>, states : seq<'s>, sp : 's -> float, tp : 's * 's -> float, ep : 's * 'o -> float) as this = let mutable last = dict<'s, float * float>() let mutable current = [dict<'s, float * float>()] let viterbiPath = dict<'s,'s list>() let initialize (o,states) = for state in states do last.[state] <- ((sp state), (sp state) * ep(state,o)) viterbiPath.[state] <- [state] current <- [last] let nextState f states = let next = dict<'s, float * float>() let add = fun (target, state, cp, prob) -> next.[target] <- (cp, prob) viterbiPath.[target] <- target::viterbiPath.[state] let junction = fun target -> states |> Seq.map (fun state -> let _,sp = last.[state] let cp, prob = f state target sp target,state, cp, prob) |> Seq.maxBy (fun (_,_,_,prob) -> prob) states |> Seq.map (junction) |> Seq.iter(add) last <- next current <- next::current let lastViterbiState () = current.Head |> Seq.maxBy (fun kv -> kv.Value) do this.Execute (obs, states) /// ビタビ経路の最後の状態 member x.LastViterbiState = lastViterbiState () /// 実行 member private x.Execute(obs, states) = let f = fun o state target sp -> let cp = ep(target, o) cp, sp * cp * tp(state, target) for i,o in (obs |> Seq.mapi (fun i x -> i,x)) do if i = 0 then initialize (o, states) else nextState (f o) states let g = fun state target sp -> let lastViterbiState = x.LastViterbiState let cp = tp(lastViterbiState.Key, target) cp, sp * cp // 与えられたパラメータから推察される次の状態 nextState g states /// 与えられたパラメータに対する全体確率 member x.TotalProb = x.ViterbiPathProb () |> List.mapi (fun i (state,(ep,vp)) -> if i = 0 then vp else ep) |> Seq.reduce (fun x y -> x * y) member private x.ViterbiPathProb () = let lastViterbiState = x.LastViterbiState viterbiPath.[lastViterbiState.Key] |> List.mapi (fun i state -> state,current.[i].[state] ) |> List.rev /// ビタビ経路(最も尤もらしい並び。尤度が最も高い経路。)を取得します。 member x.ViterbiPath = x.ViterbiPathProb () |> List.map (fun (state,(ep,vp)) -> state) /// ビタビ経路の確率 member x.ViterbiProb = let lastViterbiState = x.LastViterbiState let _,vp = current.Head.[lastViterbiState.Key] vp member x.Path = current
実行結果
0.0336 [Sunny; Rainy; Rainy; Rainy] 0.009408
F#で書いてみましたというだけで、特に面白みはない。
実行結果を見る限りは多分あっているぽい。けど、門外漢が適当に勘で書いたものなので鵜呑みはせぬようよろしくオナシャス。
*1:観測された事象系列を結果として生じる隠された状態の最も尤もらしい並びをビタビ経路と呼ぶ
F# Implementation of BackPropagation Neural Network for Pattern Recognition(LifeGame)
この記事は、F# Advent Calendar 2011の21日目です。
きっかけは、11月19日に札幌で行われた第64回CLR/H勉強会で、愛甲健二さん(@07c00)がお話してくれた「コンピューターに萌えを教えてみたよ」というセッションです。「アダルトサイトの検知」のメカニズムだったり、愛甲さん自身の"萌えの嗜好"をコンピューターに学習させてみるという少しアレゲなテーマでのお話しでしたが、内容はとても真面目で面白かった。見慣れない数式など、その全てを理解することはできませんでしたが、ニューラルネットワークの雰囲気や概要がわかりました。オライリーの「集合知プログラミング」でニューラルネットワークについて少し読んだことがあったり、何となく見聞きしたことはありましたが、基本的な考え方を知ったのはそのときがはじめてです。とても面白くもっと知りたいと思ったので、勉強会の後にモクモクとニューラルネットワークに関する情報を集めて自分なりに勉強してみました。"脳を模してモデル化したアルゴリズムによって、コンピュータに学習能力をもたせる。" なんだか面白かっこいい！じゃないですか。いろいろと調べているうちに、これなら自分にも実装できそう！と思ったので、みんな大好きF#でやってみました。F#の記事というよりも、むしろニューラルネットワーク成分多い目だが、
「大丈夫だ、ゆるふわなので問題ない。」
ニューラルネットワークとは
情報分野におけるニューラルネットワークとは、われわれ人間の脳の神経回路の仕組みを模してモデル化したもので、コンピュータに学習能力を持たせることで、様々な問題を解決しようとするアプローチのひとつで、人工知能の一分野で機械学習というジャンルに属します。もともとニューラルネットワークという研究分野は、人間が自然と行っているパターン認識や経験則を導き出したりする仕組みをモデル化して、ロボットが経験から学習していくことで、正しい反応や行動を獲得していく仕組みを実現することを目的とした側面が強かったようですが、次第に工学寄りにシフトしてきて、「データの中で明らかなものから、明らかではないものを予測する（ことをコンピュータにやらせるための）」技術や理論を指すことがほとんどになってきたようです。近年の自然言語処理や画像のパターン認識、データマイニング、あるいは信用リスク格付け予測など、ビジネス用途での応用分野における成功を要因に、普及と発展が進んでいて現在も広くその研究や応用が進められている。
教師あり学習というアプローチ
機械学習の扱う問題には、大きく分けて教師あり学習 （supervised learning） と、教師なし学習 (unsupervised learning) の２つがある。 単純にその２つに分類することができない、複合的な問題や独自に発展した特殊問題もあるようですが、基本的には、この２つに分類することができる。愛甲さんがお話してくれた、アダルトサイトの検知だったり、「コンピューターに萌えを教えてみたよ」は、ちょうど教師あり学習にあたります。教師あり学習では、入力データ（条件として明らかとなっている情報）が与えられたとき、これに対する出力（答えが明らかではない情報）を正しく予測することが目的です。 もちろん、ただ入力を入れられただけでは、コンピューターは答えとして何を出力したらよいのかわかりません。そこで、訓練データ（あるいは教師データ）と呼ばれる、入出力のペアとしたデータを、あらかじめコンピューター複数与えます。「コレの入力があったら、コレを出力しなさい」というパターンをいくつか与えて機械に学習させます。新しい入力データが来たときに、それに対する正しい出力をするような機械（関数）を作るのが目的です。複雑で広い領域の問題では、すべてのパターンを機械に学習させることは不可能で、当然、あらかじめ学習に用いる訓練データの中には現れない入力データが与えられる場合もあります。そのようなデータに対応するために、与えられた訓練データを一般化して、未知のデータに対処して予測を出力する能力（汎化能力）がなるべく高くなるような、学習アルゴリズムを設計することが、教師あり学習の主要なテーマとなります。ニューラルネットワークは、汎化能力の高い教師あり学習のアプローチのひとつです。
F#でニューラルネットワーク
F#でバックプロパゲーションアルゴリズムを用いた３層パーセプトロンを実装しました。時間がなくて整理しきれなかった部分があり心残りな面もありますが、以下、NNモジュールです。参考になればと思い、普段は書かないような説明的なコメントも多めに書いてみました。
F#
namespace NN open System [<AutoOpen>] module NN = /// 訓練データパターン type Pattern = { Inputs : double list; (* 入力 *) TeachingSignal: double list (* 教師信号 *) } // 層をつくる let createLayer size build = let rec create size acc = if size <= 0 then acc else create ((-) size 1) (acc@[build ()]) create size [] /// シグモイド関数 /// 関数のある点での勾配を求めて誤差Eが少なくなる方向へ結合重みWを変化させていきます。 let sigmoid input bias = /// α(gain)を1.0とするとき標準シグモイド関数と言う let gain : double = 5.0 1.0 / (1.0 + Math.Exp(-gain * (input + bias))) /// ニューロン type Neuron = { mutable bias : double // バイアス mutable error : double // E mutable input : double // 入力 mutable output : double // 出力 learnRate : double // 学習レート weights : Weight list // 重み } /// 出力 member this.Output with get () = if (this.output <> Core.double.MinValue) then this.output else // 判別問題を学習させる場合は階段関数やシグモイド関数を用いる。回帰問題を学習させる場合は線形関数を用いる。 // 今回はシグモイドで sigmoid this.input this.bias and set (v) = this.output <- v // 重み and Weight = { In: Neuron; mutable Value:double } // 層 and Layer = Neuron list /// 活性化 let activate neuron = neuron.input <- 0.0 for w in neuron.weights do neuron.input <- neuron.input + w.Value * w.In.Output /// エラーフィードバック let errorFeedback (neuron:Neuron) (input:Neuron) = neuron.Output * (1.0 - neuron.Output) |> fun derivative -> // より大きな重みで接続された前段のニューロンに対して、局所誤差の責任があると判定する。 let w = neuron.weights |> List.find (fun t -> t.In = input) neuron.error * derivative * w.Value /// 各ニューロンの重みを局所誤差が小さくなるよう調整する。 let adjustWeights (neuron:Neuron) (value:double) = neuron.Output * (1.0 - neuron.Output) |> fun derivative -> neuron.error <- value for i in [0..neuron.weights.Length-1] do // 出力と教師信号が異なれば、出力値を少しだけ教師信号寄りに重みを修正する neuron.weights.[i].Value <- neuron.weights.[i].Value + (neuron.error * neuron.learnRate * derivative * neuron.weights.[i].In.Output) // バイアスの補正 neuron.bias <- neuron.bias + neuron.error * neuron.learnRate * derivative /// 素のニューロンを生成 let createNewron () = { bias = 0.0 error = 0.0 input = 0.0 output = Core.double.MinValue learnRate = 0.5 weights = [] } /// 入力についてランダムな重みを持つニューロンを生成 let createNewron' inputs (rnd:Random) = let createWeights () = inputs |> List.map (fun input -> { In = input; Value = rnd.NextDouble() * 2.0 - 1.0 }) |> List.fold (fun a b -> a@[b]) [] { bias = 0.0 error = 0.0 input = 0.0 output = Core.double.MinValue learnRate = 0.5 weights = createWeights () } /// ネットワーク type Network = { InputSize : int MiddleSize : int OutputSize : int RestartAfter : int TryCount : int Inputs : Layer Middle : Layer Outputs : Layer Patterns : Pattern list } /// 入力層、中間層、出力層のニューロンを生成 let createNeuron inputSize middleSize outputSize = let rnd = new Random() let inputs = createLayer inputSize (fun () -> createNewron ()) let middle = createLayer middleSize (fun () -> createNewron' inputs rnd) let outputs = createLayer outputSize (fun () -> createNewron' middle rnd) inputs, middle, outputs /// ニューラルネットワークの各ニューロンを活性化 let networkActivate (network:Network) (pattern:Pattern) = for i in [0..pattern.Inputs.Length - 1] do network.Inputs.[i].Output <- pattern.Inputs.[i] for neuron in network.Middle do activate neuron for output in network.Outputs do activate output network.Outputs |> List.map (fun output -> output.Output) /// 初期化 let initializeNetwork (network:Network) = let inputs,middle,outputs = createNeuron network.InputSize network.MiddleSize network.OutputSize { network with Inputs = inputs; Middle = middle; Outputs = outputs; TryCount = 0 } /// 訓練データをNetworkに読み込む let loadPatterns (network:Network) (trainingData :(double list * double list) list) = let rec create n acc = if n <= 0 then acc else let inputs,teachingSignal = trainingData.[n] create ((-) n 1) (acc@[{Inputs=inputs; TeachingSignal=teachingSignal}]) { network with Patterns = create (trainingData.Length-1) [] } /// 訓練 let training (network:Network) = /// 重み調整:バックプロパゲーション let adjustWeights (delta:double) = // 個々のニューロンの期待される出力値と倍率(scaling factor)、要求された出力と実際の出力の差を計算する。これを局所誤差と言う。 for output in network.Outputs do adjustWeights output delta for neuron in network.Middle do // そのように判定された前段のニューロンのさらに前段の中間層における隠れニューロン群について同様の処理を行う。 adjustWeights neuron (errorFeedback output neuron) let mutable error = 0.0 for pattern in network.Patterns do // ネットワークの出力とそのサンプルの最適解を比較する。各出力ニューロンについて誤差を計算する。 for i in [0..pattern.TeachingSignal.Length - 1] do let output = (networkActivate network pattern).[i] let delta = pattern.TeachingSignal.[i] - output adjustWeights delta // 二乗誤差でEを求める error <- error + Math.Pow(delta, 2.0) { network with TryCount = network.TryCount + 1}, error /// 三層ネットワークを生成 let createNetwork (inputs:Layer) (middle:Layer) (outputs:Layer) restartAfter = { InputSize = inputs.Length MiddleSize = middle.Length OutputSize = outputs.Length TryCount = 0 RestartAfter = restartAfter Inputs = inputs Middle = middle Outputs = outputs Patterns = [] }
線形分離問題「OR」および「AND」、非線形分離問題 XORを解く
以下、NNモジュールを使って各問題を解くF#
open System open NN open ListExModule [<STAThread>] // 三層分のニューロンを生成 let inputs,middle,outputs = createNeuron 2 3 1 // ニューラルネットワークを構築 let mutable (network:Network,error:float) = createNetwork inputs middle outputs 500 , 1.0 let rec flat = function | [] -> [] | x::_ when x = [] -> [] | x::xs -> x @ flat xs let rec insert v i lst = match i, lst with | 0, xs -> v::xs | i, x::xs -> x::insert v (i - 1) xs | i, [] -> failwith "境界外デス！" let condition = [1..8] let createPattern target ts (source: int list) = let inputs = condition |> List.map (fun i -> if source |> List.exists (fun x -> x = i) then 1.0 else 0.0) |> insert (if target = 1 then 1.0 else 0.0) 4 inputs,[ts] // AND問題 (線形分離可能) let andProblem = [ [0.0; 0.0;], [0.0]; [0.0; 1.0;], [0.0]; [1.0; 0.0;], [0.0]; [1.0; 1.0;], [1.0]; ] // OR問題 (線形分離可能) let orProblem = [ [0.0; 0.0;], [0.0]; [0.0; 1.0;], [1.0]; [1.0; 0.0;], [1.0]; [1.0; 1.0;], [1.0]; ] // XOR問題 (線形分離不可能) let xorProblem = [ [0.0; 0.0;], [0.0]; [0.0; 1.0;], [1.0]; [1.0; 0.0;], [1.0]; [1.0; 1.0;], [0.0]; ] // 訓練データをロード network <- loadPatterns network xorProblem // ここではXORを解く let main () = /// 実行 let run (network:Network) = while true do try Console.Write("Input x, y: ") let values = Console.ReadLine() let line = values.Split(',') let pattern = [0..network.InputSize-1] |> List.map (fun i -> Core.double.Parse(line.[i])) let inputs = List.init(network.InputSize) (fun i-> pattern.[i]) for output in networkActivate network { Inputs=inputs; TeachingSignal = []} do printfn "%d(%f)" <| Convert.ToInt32(output) <| output with | e -> Console.WriteLine(e.Message) // ニューラルネットワークを訓練する while error > 0.1 do let x,y = training network network <- x; error <- y printfn "Try %d\tError %f" x.TryCount y if network.TryCount > network.RestartAfter then network <- initializeNetwork network // 実行 run network main () Console.ReadKey () |> ignore
非線形分離問題も問題なく解けますな。
パターン認識でライフゲーム
バックプロパゲーションアルゴリズムで３層パーセプトロンによって構築したニューラルネットでXOR判定をすることができた。ここで終わってもよかったのですが、せっかくなので欲張って、もう少しだけ複雑な非線形問題のパターン認識もやらせてみました。第64回CLR/H勉強会の、@mentaroさんのセッションの最終デモで「ライフゲーム」が取り上げられていました。勉強会後に、「そういや、ライフゲームのセル生死判定は、判定対象セルとその周囲８つのセルをパターンとして捉えることがきて、セルの生死結果を教師データとするパターンをつくって、多数の訓練データで学習させることで、ニューラルネットワークにライフゲームの生死判定をさせることができるんじゃね？」と思いました。それを実践してみようという。練習にはちょうど良いですね。判定対象セルと周囲の８つのセルを合わせた９つのセルを入力とし、生死の結果を教師データとする訓練データを作成して、ニューラルネットに食わせてシバけばおーけー！
以下、NNモジュールを使って、
F#+XNAで、ニューラルネットのパターン認識でライフゲームなコード
F#
namespace LG open System open Microsoft.Xna.Framework open Microsoft.Xna.Framework.Graphics open Microsoft.Xna.Framework.Input open Microsoft.Xna.Framework.Content open NN open ListExModule [<AutoOpen>] module Assist = // リスト平坦化 let rec flat = function | [] -> [] | x::_ when x = [] -> [] | x::xs -> x @ flat xs // リストへの挿入 let rec insert v i lst = match i, lst with | 0, xs -> v::xs | i, x::xs -> x::insert v (i - 1) xs | i, [] -> failwith "境界外デス！" let condition = [1..8] // パターン生成 let createPattern target ts (source: int list) = let inputs = condition |> List.map (fun i -> if source |> List.exists (fun x -> x = i) then 1.0 else 0.0) |> insert (if target = 1 then 1.0 else 0.0) 4 inputs,[ts] // ライフゲームの教師データ生成 let lifeGameTrainingData = let pattern = [0..8] |> List.map (fun x -> combinations x condition) let survive = List.map (fun x -> x |> createPattern 1 1.0) // 生存 let keep = List.map (fun x -> x |> createPattern 0 0.0) // 維持 let birth = List.map (fun x -> x |> createPattern 0 1.0) // 誕生 let die = List.map (fun x -> x |> createPattern 1 0.0) // 過疎or過密 pattern |> List.mapi (fun i x -> i |> function | 2 -> survive x @ keep x | 3 -> survive x @ birth x | _ -> die x @ keep x) |> flat /// 初期ボード：グライダー銃 let getGliderguns () = [|[|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|]; [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|]; [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;1;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|]; [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;1;0;1;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|]; [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;1;1;0;0;0;0;0;0;1;1;0;0;0;0;0;0;0;0;0;0;0;0;1;1;0;0;0;0;0;0|]; [|0;0;0;0;0;0;0;0;0;0;0;0;0;1;0;0;0;1;0;0;0;0;1;1;0;0;0;0;0;0;0;0;0;0;0;0;1;1;0;0;0;0;0;0|]; [|0;0;1;1;0;0;0;0;0;0;0;0;1;0;0;0;0;0;1;0;0;0;1;1;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|]; [|0;0;1;1;0;0;0;0;0;0;0;0;1;0;0;0;1;0;1;1;0;0;0;0;1;0;1;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|]; [|0;0;0;0;0;0;0;0;0;0;0;0;1;0;0;0;0;0;1;0;0;0;0;0;0;0;1;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|]; [|0;0;0;0;0;0;0;0;0;0;0;0;0;1;0;0;0;1;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|]; [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;1;1;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|]; [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|]; [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|]; [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|]; [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|]; [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|]; [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|]; [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|]; [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|]; [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|]; [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|]; [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|]; [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|]; [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|]; [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|]; [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|]; [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|]; [|0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0|]|] /// 同じ長さを持つジャグ配列を二次元配列へ変換 let convert (source:int [][]) = (source.[0].GetLength(0),Array.length source) ||> fun row col -> Array2D.create row col 0 |> fun array -> seq { for i in 0..row - 1 do for j in 0..col - 1 do yield i,j } |> Seq.iter (fun (i,j) -> array.[i,j] <- source.[j].[i]) array /// ライフゲーム type LifeGame () as this = inherit Game() // ゲームタイトル, GraphicsDeviceManager, SpriteBatch let gametitle, gmanager, spriteBatch = "LifeGame", new GraphicsDeviceManager(this), lazy new SpriteBatch(this.GraphicsDevice) // 三層パーセプトロンの各ニューロンを生成 -> 入力:9 , 隠れ:17 , 出力:1 let inputs,middle,outputs = createNeuron 9 17 1 // ニューラルネットワークを構築, error状態を取得 let mutable (network:Network,error:float) = createNetwork inputs middle outputs 500 , 1.0 // SpriteFont let font = lazy this.Content.Load<SpriteFont>(@"Content\font\SpriteFont1") // セルのテクスチャ let textureCell = lazy this.Content.Load<Texture2D>(@"Content\hagure") // セルエフェクト用マスクテクスチャ let normalmapTextureCell = lazy this.Content.Load<Texture2D>(@"Content\hagure_alpha") // HLSLエフェクト let normalmapEffect = lazy this.Content.Load<Effect>(@"Content\normalmap") // セルとセルの間の間隔 let borderWidth, borderHeight = 0, 0 // セル描画の開始位置 let boardStartX, boardStartY = 0, 0 // セルのサイズ（テクスチャのサイズによりけり） let cellWidth, cellHeight = 18, 17 // ライフゲームの状態を表すボード let board = getGliderguns() |> convert // ボードのサイズ let width, height = Array2D.length1 board , Array2D.length2 board // ライフゲームの状態の更新制御 let mutable runFlg = true let mutable nowRunFlg = false let mutable previousRunFlg = false // ライフゲームの世代交代インターバル let mutable interval = 10.0 // マウスボタンのリリース状態 let mutable mouseButtonReleased = false // 訓練が終了したか否か let mutable trainingEnd = false // マウスクリック位置の取得 let getPos x y = new Vector2(float32(boardStartX + x * cellWidth + x * borderWidth), float32(boardStartY + y * cellHeight + y * borderHeight)) // セル描画 サークル動作 let moveInCircle (gameTime:GameTime) (speed:float) = let time = gameTime.TotalGameTime.TotalSeconds * speed let x = Math.Sin(time) |> float32 let y = Math.Cos(time) |> float32 new Vector2(x, y) // キー操作 let operateKeys () = let mouseState = Mouse.GetState() let keyboardState = Keyboard.GetState() if mouseState.LeftButton = ButtonState.Pressed && mouseButtonReleased && this.IsActive then // マウスボタン押下中 mouseButtonReleased <- false let mouseStateX, mouseStateY = mouseState.X |> float32, mouseState.Y |> float32 let mousePos = new Vector2(mouseStateX, mouseStateY ) for x in [0..width-1] do for y in [0..height-1] do let pos = getPos x y if pos.X < mousePos.X && pos.X + float32(cellWidth) > mousePos.X && pos.Y < mousePos.Y && pos.Y + float32(cellHeight) > mousePos.Y then // マウスでクリックされたところのセルの生死状態のトグル board.[x, y] <- if board.[x, y] = 0 then 1 else 0 else if mouseState.LeftButton <> ButtonState.Pressed then // マウスボタンをリリース mouseButtonReleased <- true // Pキーによる、PAUSE ON/OFF previousRunFlg <- nowRunFlg nowRunFlg <- keyboardState.IsKeyDown(Keys.P) if nowRunFlg && not previousRunFlg then runFlg <- not runFlg // ライフゲーム状態の更新 let updateState = let updateBoard () = let tmp = Array2D.create width height 0 for x in [0..width-1] do for y in [0..height-1] do let inputs = // x7:左上, x8;上, x9:右上, x4:左, x5:評価対象のセル, x6:右, x1:左下, x2:下, x3:右下 let x7 = if x-1 >= 0 && y-1 >= 0 && board.[x-1, y-1] = 1 then 1.0 else 0.0 let x8 = if y-1 >= 0 && board.[x, y-1] = 1 then 1.0 else 0.0 let x9 = if x+1 < width && y-1 >= 0 && board.[x+1, y-1] = 1 then 1.0 else 0.0 let x4 = if x-1 >= 0 && board.[x-1, y] = 1 then 1.0 else 0.0 let x5 = board.[x, y] |> float let x6 = if x+1 < width && board.[x+1, y] = 1 then 1.0 else 0.0 let x1 = if x-1 > 0 && y+1 < height && board.[x-1, y+1] = 1 then 1.0 else 0.0 let x2 = if y+1 < height && board.[x, y+1] = 1 then 1.0 else 0.0 let x3 = if x+1 < width && y+1 < height && board.[x+1, y+1] = 1 then 1.0 else 0.0 // ライフゲームのパターン [x7;x8;x9; x4;x5;x6; x1;x2;x3] // ニューラルネットワークで判定 let outputs = networkActivate network { Inputs=inputs; TeachingSignal = []} // パターンに対する出力を取得 let output = Convert.ToInt32(outputs.[0]) tmp.[x, y] <- output // ボードに状態を反映 for x in [0..width-1] do for y in [0..height-1] do board.[x, y] <- tmp.[x, y] let settim : double ref = ref 0.0 (fun (gameTime:GameTime) -> if runFlg then let nowMillSeconds = gameTime.TotalGameTime.TotalMilliseconds if !settim + interval < nowMillSeconds then settim := nowMillSeconds // インターバルごとに状態を更新 updateBoard()) let update = let lag = 300. let wait = ref 0. // ニューラルネットワークに訓練データを読み込み network <- loadPatterns network lifeGameTrainingData (fun gameTime -> wait := !wait + 60. if !wait > lag then wait := 0. if not trainingEnd then // 訓練データをロード if error > 0.1 then // ニューラルネットワークを訓練する let nw,err = training network network <- nw; error <- err if network.TryCount > network.RestartAfter then // 乱数の具合が悪かったり、ローカルミニマムにハマったりで訓練がなかなか終わらない場合は、最初から訓練しなおしてみる network <- initializeNetwork network else // 訓練おわりやしたー trainingEnd <- true else // ニューラルネットワークの訓練が終了したら、キー入力を受け付けたりライフゲームを開始 operateKeys () updateState gameTime) do // タイトルを設定 this.Window.Title <- gametitle // ゲームループの間隔を設定 (60FPS) this.TargetElapsedTime <- TimeSpan.FromSeconds(1.0 / 60.) // マウスカーソルを表示 this.IsMouseVisible <- true override this.Initialize() = // ゲームウィンドウのサイズを設定 gmanager.PreferredBackBufferWidth <- this.Width gmanager.PreferredBackBufferHeight <- this.Height base.Initialize () /// ウィンドウの幅 member this.Width with get () = cellWidth * width /// ウィンドウの高さ member this.Height with get () = cellHeight * height /// ライフゲームの状態を更新 override this.Update (gameTime:GameTime) = base.Update gameTime if Keyboard.GetState().IsKeyDown(Keys.Escape) then // Escが押されたらおしまい this.Exit() // ライフゲームクラスの状態を更新 update gameTime /// ライフゲームの状態を描画 override this.Draw (gameTime:GameTime) = base.Draw gameTime // テクスチャーデータのサンプリング方法をClampに設定 gmanager.GraphicsDevice.SamplerStates.[1] <- new SamplerState(AddressU = TextureAddressMode.Clamp, AddressV = TextureAddressMode.Clamp, AddressW = TextureAddressMode.Clamp) // 背景を黒で塗りつぶし gmanager.GraphicsDevice.Clear(Color.Black) // ライフゲームクラスの状態を描画 if not trainingEnd then // ニューラルネットワークの訓練が終わるまでは、訓練の進捗を描画 spriteBatch.Force().Begin() spriteBatch.Force().DrawString(font.Force (), String.Format("NeuralNework Training... Try:{0,3:##0}; Error:{1}", network.TryCount, error), Vector2(0.0f,0.0f), Color.White) spriteBatch.Force().End() else // 訓練終了後は、ライフゲームの状態を描画 for x in [0..width-1] do for y in [0..height-1] do let pos = getPos x y if board.[x, y] = 0 then // 死んでるセルは真っ黒くろ助 spriteBatch.Force().Begin() spriteBatch.Force().Draw(textureCell.Force(), pos, Color.Black) spriteBatch.Force().End() else // 生きてるセルは、セルのテクスチャを描画 // テクスチャの描画に使用するエフェクトの設定 let spinningLight = moveInCircle gameTime 5.0 let time = gameTime.TotalGameTime.TotalSeconds let tiltUpAndDown = 0.5f + float32(Math.Cos(time * 0.75)) * 0.1f let lightDirection = new Vector3(spinningLight * tiltUpAndDown / 2.0f, tiltUpAndDown / 2.0f) lightDirection.Normalize() normalmapEffect.Force().Parameters.["LightDirection"].SetValue(lightDirection) gmanager.GraphicsDevice.Textures.[1] <- normalmapTextureCell.Force() // HLSLのエフェクトを使用して、セルのテクスチャを描画 spriteBatch.Force().Begin(SpriteSortMode.Deferred, BlendState.AlphaBlend, null, null, null, normalmapEffect.Force()) spriteBatch.Force().Draw(textureCell.Force(), pos, Color.White) spriteBatch.Force().End()
ライフゲームの生死判定を学習させるための訓練データは、F#で順列(Permutation)と組み合わせ(Combination)。YOU、Listモナドしちゃいなよ。集合モナドもあるよ。で書いた、
組み合わせ(Combination)を用いて全512パターンを作成しています。
セルを表している「はぐれメタル」の描画には、無駄にHLSL(High Level Shader Language)を使用しています。
HLSL
float3 LightDirection; float3 LightColor = 2.0; float3 AmbientColor = 0.1; sampler TextureSampler : register(s0); sampler NormalSampler : register(s1); float4 main(float4 color : COLOR0, float2 texCoord : TEXCOORD0) : COLOR0 { float4 tex = tex2D(TextureSampler, texCoord); float3 normal = tex2D(NormalSampler, texCoord); float lightAmount = max(dot(normal, LightDirection), 0.2); color.rgb *= AmbientColor + lightAmount * LightColor; return tex * color; } technique Normalmap { pass Pass1 { PixelShader = compile ps_2_0 main(); } }
errorが0.1以下になるまで訓練するようにしているので、ローカルミニマムにハマってしまい、なかなか最後まで学習が完了しない。
早く収束させるには、中間層の隠れニューロンの数を調整したり訓練を甘くして学習レベルを下げるとよい。
この実装では運に左右される。ローカルミニマムに陥る問題を避ける方法はいくつかあるようだが、それはまた別のお話。
SkyDriveに、F#でニューラルネットワークなソースコード一式を置いておきます。
SkyDrive - NN.zip
F#でsleep sort
追記しました
元ネタは、以下あたり。
常識を覆すソートアルゴリズム！その名も"sleep sort"！ - Islands in the byte stream
http://d.hatena.ne.jp/gfx/20110519/1305810786
Sleep sortの各言語での実装まとめ – Yuyak
http://www.yuyak.com/1339
ただいま流行っている sleep sort です。
既出かもしれませんが、せっかく書いたので置いておきます。
open System.Collections.Concurrent let sleepSort f s = let q = new ConcurrentQueue<'a> () seq {for x in s -> async { do! Async.Sleep((f:'a -> int) >> ( * ) 100 <| x) q.Enqueue x } } |> Async.Parallel |> Async.RunSynchronously |> ignore q :> seq<'a> ["5";"3";"6";"3";"6";"3";"1";"4";"7"] |> sleepSort int |> Seq.iter (printf "%s,") System.Console.ReadLine () |> ignore
いろんな書き方があると思うけど、一応F#らしさをプンプン匂わせてみたつもり。
追記:シグネチャ ファイルも書こう！
@igeta @kos59125 お。だいたいそうなりますね。それにしても、intだけしかソートできないとか、元仕様をシカトした実装が多すぎる気が。そこは守りましょうよ的に思ったり。
2011-05-20 22:23:19 via web to @igeta
2011-05-20 22:25:44 via web to @zecl
@kos59125 @igeta あ、いえ・・・。別にマジメにやるようなネタでもないですからねｗ こちらこそ、なんかすいません^^;
2011-05-20 22:27:29 via web to @kos59125
@zecl @kos59125 シグネチャ ファイルが付いてないコードはすべて手抜きです！（ｷﾘｯ などと。
2011-05-20 22:42:04 via web to @zecl
あ、シグネチャ ファイルって、実はあんまし書いたことなかったですよ^^;
ということで、せっかくなので書いておきます。
SleepSort.fsi
namespace Sort [<AutoOpen>] module Sort = val sleepSort : ('a -> int) -> seq<'a> -> seq<'a>
SleepSort.fs
namespace Sort [<AutoOpen>] module Sort = open System.Collections.Concurrent let sleepSort f s = let q = new ConcurrentQueue<'a> () seq {for x in s -> async { do! Async.Sleep((f:'a -> int) >> ( * ) 100 <| x) q.Enqueue x } } |> Async.Parallel |> Async.RunSynchronously |> ignore q :> seq<'a> ["5";"3";"6";"3";"6";"3";"1";"4";"7"] |> sleepSort int |> Seq.iter (printf "%s,") System.Console.ReadLine () |> ignore
これでよいかな？
追記:よいシグネチャ ファイルは、よいドキュメントでもある
せっかくなのでシグネチャ ファイル追記しておいた。これで勝つる。
2011-05-20 23:03:39 via web
@zecl 引数名の指定も .fsi 側でぜひ。あとコメント。
2011-05-20 23:05:50 via web to @zecl
val sleepSort : projection:('T -> int) -> source:seq<'T> -> seq<'T> とかしておくとすばらしいと思うです。
2011-05-20 23:18:23 via web
よいシグネチャ ファイルは、よいドキュメントでもある、とか OCaml のエロイ人が言ってた気がする。ただし僕はいまホッピーを飲んでいて酔っているのでよくわかりません。
2011-05-20 23:21:04 via web
記憶力の乏しさなら自信があります！
2011-05-20 23:24:02 via web
その気になれば、.fs ファイルでは気ままに f とか x とか短い引数名を付けておいて .fsi ファイル側で意味のある名前を付ける、ということも可能だろう、ということ。
2011-05-20 23:28:11 via web
@igeta ありがとうございます！コメントというのは、.fsの関数に「///」でコメントが欲しいということです？
2011-05-20 23:31:27 via web to @igeta
@zecl .fsi 側で各 val なり module なりの上っちょに /// でも // でもいいのでコメントがあるといいなあと。まあ簡単に言うと F# Compiler Source の書き方に準拠してる的な感じになってるといいなっていう。
2011-05-20 23:35:14 via web to @zecl
ぜんぜん勝ててなかったorz... なるほど。勉強になります。
ホッピーうまいですよね！ということで、コメントと引数名をさらに追記しました。
SleepSort.fsi
namespace Sort [<AutoOpen>] module Sort = /// 定義であり、ドキュメントにもなる。ここで、関数に対する熱き思いをぶつけるといい。 /// 常識を覆すソートアルゴリズム！その名も"sleep sort"！のシグネチャです。 val sleepSort : projection:('T -> int) -> source:seq<'T> -> seq<'T>
SleepSort.fs
namespace Sort [<AutoOpen>] module Sort = open System.Collections.Concurrent /// 常識を覆すソートアルゴリズム！その名も"sleep sort"！をしちゃいます。 let sleepSort f s = let q = new ConcurrentQueue<'a> () seq {for x in s -> async { do! Async.Sleep(f >> ( * ) 100 <| x) q.Enqueue x } } |> Async.Parallel |> Async.RunSynchronously |> ignore q :> seq<'a> ["5";"3";"6";"3";"6";"3";"1";"4";"7"] |> sleepSort int |> Seq.iter (printf "%s,") System.Console.ReadLine () |> ignore
という具合に、引数名を変えてもOKだし、ジェネリックの型名を'Tから'aに変えても問題ない、と。
そして、f の型についてはシグネチャファイルに定義してあるので省略可能になる、と。
こんどこそ、これで勝つる！
@igeta なるほど。.fsiが定義 and ドキュメントになるようにですね。手抜きをしないってのは結構大変っすね； この程度の規模ならよいですが、頻繁にリファクタリングしているようなときは、.fsiなんて書いている場合じゃない！ような気もしまする（単に能力不足か・・・
2011-05-20 23:42:29 via web to @igeta
追記：シグネチャ ファイルを自動生成しよう
@zecl fsc SleepSort.fs --sig:SleepSort.fsi
2011-05-20 23:58:06 via web to @zecl
@zecl ってすると fsc さんがよしなに fsi を作ってくれますよ。
2011-05-21 00:03:13 via web to @zecl
シグネチャファイル(.fsi)をよしなに自動生成したあとに、自分でいろいろ追記すればよい、と。
でも、大幅にコードの構成を変えた場合はやり直し。それはちょっとツライね。
「ハッカーのたのしみ」はかなりの良書。いまさらFlagsAttributeのレシピ、リターンズ。.NET FrameworkにBitCountくらい標準であってもいいのにね
以前、FlagsAttributeとビット演算のちょっとしたレシピという記事を書きました。
ご覧頂くとわかるように、とてもダサい実装になっています。記事を掲載してすぐに知人からツッコミがありました。
ツッコミがあったときにすぐに続編記事を書いて訂正しようと思っていたのですが、すっかり忘れていました。
最近でも、いまだに「FlagsAttribute」を検索ワードとして、こちらにたどり着く方も多いようなので、
このままダサい実装を晒し続けて、そのまま参考にされるのはとても心が痛みます。
なので、ダサくない実装をF#、C#、VB.NETの３つの言語で掲載しておこうと思います。
とある知人からの指摘
ブログのFlagsAttributeの記事みたけど、たしかにアレはださすぎるw
BitCountやりたいなら、常識的に考えてビット演算で。Javaの実装とかモロだから参考にするとよいよ。
あと、ビット演算関係では、「ハッカーのたのしみ」って本にいろいろ面白いこと載ってるから読んどいた方がいい。
というような感じでした。そうかー、Javaには標準であるのね。
その後、早速Javaの実装を見たり、「ハッカーのたのしみ」という本を読みました。*1
ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか
- 作者: ジュニア,ヘンリー・S.ウォーレン,Jr.,Henry S. Warren,滝沢徹,玉井浩,鈴木貢,赤池英夫,葛毅,藤波順久
- 出版社/メーカー: エスアイビーアクセス
- 発売日: 2004/09
- メディア: 単行本
- 購入: 35人 クリック: 732回
- この商品を含むブログ (127件) を見る
JavaのbitCountの実装はこんな感じになっている
Javaの Integer.bitCount( i ) という
intの1のビットの数を数えるメソッドの実装は、こんな感じになっているようです。
public static int bitCount(int i) { i = i - ((i >>> 1) & 0x55555555); i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); i = (i + (i >>> 4)) & 0x0f0f0f0f; i = i + (i >>> 8); i = i + (i >>> 16); return i & 0x3f; }
このような実装で、結果的に1のビットの立つ数を計算することができる、と。
一見意味不明のプログラムに見えますが、コードと向きあってちゃんと読めば、それほど難しいことはしていません。
これはいわゆる分割統治を用いたアルゴリズムで、まず2ビットごとに分割した16のブロックに
元々あった２つのビットの和をセットし、次に隣接する２つのブロックの和を計算し、
その結果をまた、4ビットごとに分割された8ブロックにそれぞれ結果をセットする。
といった操作を繰り返すことで、結果的に1のビットの数を数えています。
また、ブロックごとの和が隣接するブロックに影響を与えないのであればビット演算andは不要となることも
上記のコードは示しているというわけです。んー、なるほど。確かに無駄の少ない良質な実装ですね。
と、理屈はわかったのでのですが、
こういう発想は、ビット演算とは無縁に近いプログラミングライフを送っている自分には、
とても思い浮かばなかった。へっぽこプログラマであることを、再確認しました。
ググってみたところ、.NETでこの手の話を書いているひとは、なぜかいらっしゃらないようでした。
ということで、.NETにおけるBitCountの実装サンプルおよび、
FlagsAttributeのレシピを、F#、C#、VB.NETで書きましたので置いておきます。
F#による実装
namespace Library1 [<System.Runtime.CompilerServices.ExtensionAttribute>] module public EnumFlagsExtentions = open System open System.Runtime.CompilerServices ///intについてビットが立っている数を取得します。 [<Extension>] let BitCount (self : int) = self |> fun x -> x - ((x >>> 1) &&& 0x55555555) |> fun x -> ((x >>> 2) &&& 0x33333333) + (x &&& 0x33333333) |> fun x -> (x >>> 4) + x &&& 0x0f0f0f0f |> fun x -> (x >>> 8) + x |> fun x -> (x >>> 16) + x &&& 0x3f ///FlagsAttribute属性が付加されたenumについて、ビットが立っている数を取得します。 [<Extension>] let FlagsCount<'T when 'T: enum<int>> (self : 'T) = if not(self.GetType().IsEnum) then raise (new ArgumentException("enumじゃなきゃだめ")) if not(Attribute.IsDefined(self.GetType(),typeof<FlagsAttribute>)) then raise (new ArgumentException("FlagsAttrebute属性ついてなきゃだめ")) self |> Convert.ToInt32 |> BitCount ///FlagsAttribute属性が付加されたenumについて、ビットが立っているenumの要素を取得します。 [<Extension>] let GetFlags<'T when 'T: enum<int>> (self : 'T) = if not(self.GetType().IsEnum) then raise (new ArgumentException("enumじゃなきゃだめ")) if not(Attribute.IsDefined(self.GetType(),typeof<FlagsAttribute>)) then raise (new ArgumentException("FlagsAttrebute属性ついてなきゃだめ")) let target = self |> Convert.ToInt32 seq{for i in 0..31 do let bit x i = let x = target >>> i let x = x &&& - x x let x = bit target i if (x = 0b1) then yield x <<< i :> obj :?> 'T }
F#では、ジェネリックの制約にenum型を指定することができます。素晴らしいです。
ですので、通常F#で利用する分には、「self.GetType().IsEnum」によるチェックをする必要はありませんが、
C#やVB.NETでは、enum型によるジェネリックの制約は利用できないので、
C#やVB.NETから利用されることも考慮するのであれば、このように実装しておくことが望ましいでしょう。
また、Extension属性を付加することで、C#やVB.NETから利用したときに、ちゃんと拡張メソッドとして機能します。
お試し
namespace ConsoleApplication1 open Library1 module Test = open System open Library1.EnumFlagsExtentions [<Flags()>] type EDocks = | None = 0b00000 | Top = 0b00001 | Left = 0b00010 | Right = 0b00100 | Bottom = 0b01000 | All = 0b01111 let enum0 = EDocks.Non let enum1 = EDocks.Top let enum2 = EDocks.Top ||| EDocks.Left let enum3 = EDocks.Top ||| EDocks.Left ||| EDocks.Right let enum4 = EDocks.Top ||| EDocks.Left ||| EDocks.Right ||| EDocks.Bottom let enum5 = EDocks.Non ||| EDocks.Left ||| EDocks.Left ||| EDocks.Non let _ = Console.WriteLine(enum0 |> FlagsCount) Console.WriteLine(enum1 |> FlagsCount) Console.WriteLine(enum2 |> FlagsCount) Console.WriteLine(enum3 |> FlagsCount) Console.WriteLine(enum4 |> FlagsCount) Console.WriteLine(enum5 |> FlagsCount) enum2 |> GetFlags |> Seq.iter Console.WriteLine Console.WriteLine () enum4 |> GetFlags |> Seq.iter Console.WriteLine (-90000000) |> BitCount |> Console.WriteLine Console.ReadKey()
F#では、FlagsAttributeを付加したenum型を記述する際、
「0b00100」のようにビットで記述することができます。これは直感的に書けてとても便利ですね。
実行結果
0 1 2 3 4 1 Top Left Top Left Right Bottom 15
C#による実装
using System; using System.Collections.Generic; using System.Linq; using System.Text; namespace ClassLibrary1 { public static class EnumFlagsExtentions { /// <summary> /// intについてビットが立っている数を取得します。 /// </summary> /// <param name="self"></param> /// <returns></returns> public static int BitCount(this int self) { var x = self - ((self >> 1) & 0x55555555); x = ((x >> 2) & 0x33333333) + (x & 0x33333333); x = (x >> 4) + x & 0x0f0f0f0f; x += x >> 8; return (x >> 16) + x & 0xff; } /// <summary> /// FlagsAttribute属性が付加されたenumについて、ビットが立っている数を取得します。 /// </summary> /// <typeparam name="T"></typeparam> /// <param name="self"></param> /// <returns></returns> public static int FlagsCount<T>(this T self) where T : struct, IConvertible { if (!self.GetType().IsEnum) throw new ArgumentException("enumじゃなきゃだめ"); if (!Attribute.IsDefined(self.GetType(), typeof(FlagsAttribute))) throw new ArgumentException("FlagsAttrebute属性ついてなきゃだめ"); return BitCount(Convert.ToInt32(self)); } /// <summary> /// FlagsAttribute属性が付加されたenumについて、ビットが立っているenumの要素を取得します。 /// </summary> /// <typeparam name="T"></typeparam> /// <param name="self"></param> /// <returns></returns> public static IEnumerable<T> GetFlags<T>(this T self) where T : struct, IConvertible { if (!self.GetType().IsEnum) throw new ArgumentException("enumじゃなきゃだめ"); if (!Attribute.IsDefined(self.GetType(), typeof(FlagsAttribute))) throw new ArgumentException("FlagsAttrebute属性ついてなきゃだめ"); var target = Convert.ToInt32(self); for (int i = 0; i < 32; i++) { var x = target >> i; x &= -x; if (x == 0x0001) yield return (T)Enum.ToObject(typeof(T), x << i); } } } }
VB.NETによる実装
Imports System.Runtime.CompilerServices Public Module EnumFlagsExtentions ''' <summary> ''' Integerについてビットが立っている数を取得します。 ''' </summary> ''' <param name="self"></param> ''' <returns></returns> ''' <remarks></remarks> <Extension()> _ Public Function BitCount(ByVal self As Integer) As Integer Dim x As Integer = self - ((self >> 1) And &H55555555) x = ((x >> 2) And &H33333333) + (x And &H33333333) x = (x >> 4) + x And &HF0F0F0F x += x >> 8 Return (x >> 16) + x And &HFF End Function ''' <summary> ''' FlagsAttribute属性が付加されたenumについて、ビットが立っている数を取得します。 ''' </summary> ''' <typeparam name="T"></typeparam> ''' <param name="self"></param> ''' <returns></returns> ''' <remarks></remarks> <Extension()> _ Public Function FlagsCount(Of T As Structure)(ByVal self As T) If Not self.GetType().IsEnum Then Throw New ArgumentException("enumじゃなきゃだめ") End If If Not Attribute.IsDefined(self.GetType(), GetType(FlagsAttribute)) Then Throw New ArgumentException("FlagsAttrebute属性ついてなきゃだめ") End If Return BitCount(Convert.ToInt32(self)) End Function ''' <summary> ''' FlagsAttribute属性が付加されたenumについて、ビットが立っているenumの要素を取得します。 ''' </summary> ''' <typeparam name="T"></typeparam> ''' <param name="self"></param> ''' <returns></returns> ''' <remarks></remarks> <Extension()> _ Public Function GetFlags(Of T As Structure)(ByVal self As T) As IEnumerable(Of T) If Not self.GetType().IsEnum Then Throw New ArgumentException("enumじゃなきゃだめ") End If If Not Attribute.IsDefined(self.GetType(), GetType(FlagsAttribute)) Then Throw New ArgumentException("FlagsAttrebute属性ついてなきゃだめ") End If Dim target As Integer = Convert.ToInt32(self) Dim result As New List(Of T)() For i As Integer = 0 To 31 Dim x As Integer = target >> i x = x And -x If x = &H1 Then result.Add(DirectCast([Enum].ToObject(GetType(T), x << i), T)) End If Next Return result End Function End Module
.NET4が使えるのならば、C#やVB.NETではCode Contractsが利用できるので、「契約」を用いて
事前条件でenum型であるかどうか、FlagsAttribute属性が付加されているかどうかについて
判定することができればより良い実装にできるのではないかと検討してみたのですが、残念ながらできないようです。
このあたりのメタ的要素の判定についても「契約」で表現でるようになってくれると、
Code Contractsの利用価値が更に高まると思うのですが。これについては今後に期待したいところです。
最後に
というわけで、ダサい実装をやっと訂正できました。複数のbool(Boolean)値を一度に扱うような場合、FlagsAttributeを付加したenumは利用価値が高いことも多いです。
なので、このようなレシピは是非手持ちのクラスライブラリに忍ばせておきたいところです。
余裕があれば、他にJavaで標準でサポートされているInteger.Reverseや
Integer.HighestOneBit、Integer.LowestOneBitなどのメソッドについても実装しておくと嬉しいかもしれません。
それはそうと、C#やVB.NETでもF#と同様に、ジェネリック制約にenum型が使えるようにしてもらいたいものです。
*1:私はなぜか、「ハッカーのたしなみ」と空目します。
迷路の生成とその解
パラドックス大全 - 世にも不思議な逆説パズル
著：ウィリアム・パウンドストーン 訳：松浦俊介
という本を読了しました。冒頭の水槽の脳の話から最後まで楽しく読めました。
その中で、NP完全と迷宮の話がでてきまして、大変興味をそそられました。
プログラミングにおける、迷路のアルゴリズムの原理については、
一応たしなむ程度には知っていましたが、実際に書いたことはなかったので、
試しに書いてみることにしました。どうせなら、ちょっとは見た目にも懲りたいなー、と思って作っていたら、
結果的に見た目の部分のプログラミングの方がメインっぽくなってしまいました(本末転倒)。
まだリファクタリングが不十分だったり、クラス設計でポカやってたり、
やり残し感がかなりありますが、なんか飽きちゃった(笑)ので、このあたりで一端ストップ。
恥ずかしげもなく、今回書いたC#で迷路なコードをあげておきます。
迷路のインターフェイス
まずは迷路のインターフェイスを定義してみましょう。ひとくちに迷路のインターフェイスと言っても、いろいろと考えられますが、
今回定義する迷路のインターフェイスのコンセプトとしては、
「穴掘り法」や「壁延ばし法」などのさまざまな迷路生成のアルゴリズムを、
後で入れ替え可能にできるようにするイメージで。
いわゆるGoFのデザパタでいうところのStrategyパターンというやつです。
今回はこんな感じにしてみました。
using System; using System.Collections.Generic; using System.Drawing; namespace ClassLibrary1 { /// <summary> /// 迷路のインターフェイス /// </summary> public interface IMaze { /// <summary> /// 迷路の解が完了したことを通知 /// </summary> event EventHandler MazeSolveComplete; /// <summary> /// スタック /// </summary> Stack<Cell> CellStack { get; set; } /// <summary> /// Cells /// </summary> Cell[][] Cells { get; set; } /// <summary> /// カレントセル /// </summary> Cell CurrentCell { get; set; } /// <summary> /// 迷路を初期化します。 /// </summary> void Initialize(Size dimension); /// <summary> /// 迷路を生成します。 /// </summary> void Generate(); /// <summary> /// 迷路を解きます。 /// </summary> void Solve(); /// <summary> /// 迷路を描画します。 /// </summary> /// <param name="g"></param> void Draw(Graphics g); /// <summary> /// リセットします。 /// </summary> void Reset(); } }
迷路を描画する升目を表すCellクラス
迷路の自動生成と、解を求めるプログラムを表現するのであれば、別にConsoleApplicationへWrite()するだけの単純なプログラムでも良いのですが、
今回はそれなりに見た目にもこだわりたいということで、
迷路の升目をグラフィカルに描画することを考慮したうえでCellクラスを作ります。
なんかいろいろと、ツッ込みどころ満載ですがご容赦ください。
using System; using System.Drawing; using System.ComponentModel; namespace ClassLibrary1 { /// <summary> /// Cell /// </summary> public class Cell { public static readonly Random _random = new Random((int)DateTime.Now.Ticks); private static int _cellSize = 5; [DefaultValue(5)] public static int CellSize { get { return _cellSize; } set { _cellSize = value; } } public const int Padding = 10; /// <summary> /// 壁の色 /// </summary> private static Color _wallColor = Color.Black; [DefaultValue(typeof(Color),"Black")] public static Color WallColor { get { return _wallColor; } set { _wallColor = value; } } /// <summary> /// Cellの色 /// </summary> private static Color _cellColor = Color.Yellow; [DefaultValue(typeof(Color), "Yellow")] public static Color CellColor { get { return _cellColor; } set { _cellColor = value; } } /// <summary> /// 答えの色 /// </summary> private static Color _solveColor = Color.Pink; [DefaultValue(typeof(Color), "Pink")] public static Color SolveColor { get { return _solveColor; } set { _solveColor = value; } } /// <summary> /// 周りの壁 /// </summary> public int[] Walls = new int[4] { 1, 1, 1, 1 }; [DefaultValue(typeof(CellState), "CellState.Init")] public enum CellState { /// <summary> /// 初期 /// </summary> Init = 0, /// <summary> /// フリー /// </summary> Free = 1, /// <summary> /// 行き止まり /// </summary> Wall = 2 } public Cell() {} public int Row { get; set; } public int Column { get; set; } public CellState State { get; set; } public bool HasAllWalls() { for (int i = 0; i < 4; i++) if (Walls[i] == 0) return false; return true; } /// <summary> /// セルの周りの壁を全部ぬっ壊します。 /// </summary> /// <param name="wall"></param> public void DestroyWall(int wall) { Walls[wall] = 0; } /// <summary> /// 壁をぬっ壊します。 /// </summary> /// <param name="theCell"></param> public void DestroyWall(Cell cell) { //隣接している壁を探す int dw = GetAdjacentWall(cell); Walls[dw] = 0; //次のセルの逆の壁もぬっこわす int oppositeWall = (dw + 2) % 4; cell.Walls[oppositeWall] = 0; } /// <summary> /// 隣接しているセル方向の壁を取得します。 /// </summary> /// <param name="cell"></param> /// <returns></returns> public int GetAdjacentWall(Cell cell) { if (cell.Row == Row) { if (cell.Column < Column) return 0; return 2; } if (cell.Row < Row) return 1; return 3; } /// <summary> /// ランダムに壁を選択します。 /// </summary> /// <returns></returns> public int SelectRandomWall() { int nextWall = _random.Next(0, 3); while ( (Walls[nextWall] == 0) || ((Row == 0) && (nextWall == 0)) || ((Row == Excavation.Dimension.Height - 1) && (nextWall == 2)) || ((Column == 0) && (nextWall == 1)) || ((Column == Excavation.Dimension.Width - 1) && (nextWall == 3)) ) { nextWall = _random.Next(0, 3); } return nextWall; } /// <summary> /// Cellを描画します。 /// </summary> /// <param name="g"></param> public void Draw(Graphics g) { g.CompositingMode = System.Drawing.Drawing2D.CompositingMode.SourceOver; using (var wallPen = new Pen(WallColor)) using (var cellPen = new Pen(CellColor)) { if (State == CellState.Free) { using (var solvePen = new Pen(SolveColor)) { g.FillRectangle(solvePen.Brush, Row * CellSize + Padding + 1, Column * CellSize + Padding + 1, CellSize - 1, CellSize - 1); if (Walls[0] == 0) g.DrawLine(solvePen, Row * CellSize + Padding, Column * CellSize + Padding, (Row + 1) * CellSize + Padding, Column * CellSize + +Padding); if (Walls[1] == 0) g.DrawLine(solvePen, Row * CellSize + Padding, Column * CellSize + Padding, Row * CellSize + Padding, (Column + 1) * CellSize + Padding); if (Walls[2] == 0) g.DrawLine(solvePen, Row * CellSize + Padding, (Column + 1) * CellSize + Padding, (Row + 1) * CellSize + Padding, (Column + 1) * CellSize + Padding); if (Walls[3] == 0) g.DrawLine(solvePen, (Row + 1) * CellSize + Padding, Column * CellSize + Padding, (Row + 1) * CellSize + Padding, (Column + 1) * CellSize + Padding); } } if (State != CellState.Free) g.FillRectangle(cellPen.Brush, Row * CellSize + Padding + 1, Column * CellSize + Padding + 1, CellSize, CellSize); if (Walls[0] == 1) g.DrawLine(wallPen, Row * CellSize + Padding, Column * CellSize + Padding, (Row + 1) * CellSize + Padding, Column * CellSize + +Padding); if (Walls[1] == 1) g.DrawLine(wallPen, Row * CellSize + Padding, Column * CellSize + Padding, Row * CellSize + Padding, (Column + 1) * CellSize + Padding); if (Walls[2] == 1) g.DrawLine(wallPen, Row * CellSize + Padding, (Column + 1) * CellSize + Padding, (Row + 1) * CellSize + Padding, (Column + 1) * CellSize + Padding); if (Walls[3] == 1) g.DrawLine(wallPen, (Row + 1) * CellSize + Padding, Column * CellSize + Padding, (Row + 1) * CellSize + Padding, (Column + 1) * CellSize + Padding); } } } }
IMazeインターフェイスを実装する、穴掘り法な迷路
穴掘り法を用いた迷路の自動生成の実装です。
迷路の解を求めるアルゴリズムは、総当りでの塗りつぶし法を採用しています。
効率的なアルゴリズムではないので、迷路が巨大になると、それに比例してかなりの時間を要します。
using System; using System.ComponentModel; using System.Collections.Generic; using System.Drawing; namespace ClassLibrary1 { /// <summary> /// 穴掘り法の迷路 /// </summary> public sealed class Excavation : IMaze { public Stack<Cell> CellStack { get; set;} public Excavation() { this.Initialize(Dimension); } /// <summary> /// Solveの終了を通知します。 /// </summary> public event EventHandler MazeSolveComplete; /// <summary> /// 現在のセル /// </summary> public Cell CurrentCell { get; set; } /// <summary> /// Cells /// </summary> public Cell[][] Cells { get; set; } private static Size _dimension= new Size(50, 50); [DefaultValue(typeof(Size))] public static Size Dimension { get { return _dimension; } set { _dimension = value; } } [EditorBrowsable(EditorBrowsableState.Never)] public bool ShouldSerializeDimension() { if (_dimension.Width != 50) return true; if (_dimension.Height != 50) return true; return false; } [EditorBrowsable(EditorBrowsableState.Never)] public void ResetDimension() { _dimension = new Size(50, 50); } /// <summary> /// 隣接する壁を持つセルのリストを取得 /// </summary> /// <param name="cell"></param> /// <returns></returns> private List<Cell> GetNeighborsWithWalls(Cell cell) { List<Cell> Neighbors = new List<Cell>(); //int count = 0; for (int countRow = -1; countRow <= 1; countRow++) for (int countCol = -1; countCol <= 1; countCol++) { if ( (cell.Row + countRow < Excavation.Dimension.Height) && (cell.Column + countCol < Excavation.Dimension.Width) && (cell.Row + countRow >= 0) && (cell.Column + countCol >= 0) && ((countCol == 0) || (countRow == 0)) && (countRow != countCol)) { if (Cells[cell.Row+countRow][cell.Column+countCol].HasAllWalls()) Neighbors.Add( Cells[cell.Row+countRow][cell.Column+countCol]); } } return Neighbors; } /// <summary> /// 迷路の初期化 /// </summary> public void Initialize(Size dimension) { this.CellStack = this.CellStack ?? new Stack<Cell>(); this.Cells = new Cell[dimension.Height][]; var totalCells = dimension.Height * dimension.Width; for (int i = 0; i < dimension.Height; i++) { this.Cells[i] = new Cell[dimension.Width]; for (int j = 0; j < dimension.Width; j++) this.Cells[i][j] = new Cell() { Row = i, Column = j }; } this.CurrentCell = this.Cells[0][0]; this.CellStack.Clear(); } /// <summary> /// 迷路を生成します。 /// /// 穴掘り法 /// </summary> public void Generate() { for (int i = 1; i < Dimension.Width * Dimension.Height;) { var adjacentCells = GetNeighborsWithWalls(CurrentCell); if (adjacentCells.Count > 0) { //ランダムにセル1つを選択し、それとカレントセルの間の壁をぬっ壊す int randomCell = Cell._random.Next(0, adjacentCells.Count); var cell = (Cell)adjacentCells[randomCell]; CurrentCell.DestroyWall(cell); CellStack.Push(CurrentCell); CurrentCell = cell; i++; continue; } CurrentCell = CellStack.Pop(); } Cells[0][0].Walls[1] = 0; Cells[Excavation.Dimension.Height - 1][Excavation.Dimension.Width - 1].Walls[3] = 0; } /// <summary> /// 迷路を解きます。 /// /// すべての行き止まりを塗り潰せば、結果的に正解が浮かび上がる方式で解を得る /// </summary> public void Solve() { bool search = true; while (search) { search = false; foreach (var cell in GetDeadEnd()) { cell.State = Cell.CellState.Wall; search = true; } }; MazeSolveComplete(this, EventArgs.Empty); } /// <summary> /// 行き止まりのセルのリストを取得します。 /// </summary> /// <returns></returns> private IEnumerable<Cell> GetDeadEnd() { for (int i = 0; i < Excavation.Dimension.Height; i++) { for (int j = 0; j < Excavation.Dimension.Width; j++) { if (Cells[i][j].State == Cell.CellState.Free) if (!IsFree(i,j)) yield return Cells[i][j]; } } } /// <summary> /// Cellがフリーか否かを取得します。 /// </summary> /// <param name="r"></param> /// <param name="c"></param> /// <returns></returns> private bool IsFree( int r, int c ) { int walls = 0; if( Cells[r][c].Walls[0] == 1 ) walls ++; else if( c > 0 && ((int)Cells[r][c - 1].State > (int)Cell.CellState.Free )) walls++; if( Cells[r][c].Walls[1] == 1 ) walls ++; else if( r > 0 && ((int)Cells[r - 1][c].State > (int)Cell.CellState.Free )) walls++; if( Cells[r][c].Walls[2] == 1 ) walls ++; else if (c < Excavation.Dimension.Width - 1 && ((int)Cells[r][c + 1].State > (int)Cell.CellState.Free)) walls++; if( Cells[r][c].Walls[3] == 1 ) walls ++; else if (r < Excavation.Dimension.Height - 1 && ((int)Cells[r + 1][c].State > (int)Cell.CellState.Free)) walls++; return (walls < 3); } /// <summary> /// 迷路を描画します。 /// </summary> /// <param name="g"></param> public void Draw(Graphics g) { for (int i = 0; i < Excavation.Dimension.Height; i++) for (int j = 0; j < Excavation.Dimension.Width; j++) Cells[i][j].Draw(g); } /// <summary> /// 迷路のCellをリセットします。 /// </summary> public void Reset() { for (int i = 0; i < Excavation.Dimension.Height; i++) for (int j = 0; j < Excavation.Dimension.Width; j++) Cells[i][j].State = Cell.CellState.Free; } } }
ToolStripNumericUpDown
ToolStripにNumericUpDownを表示するためのもの
using System; using System.Drawing; using System.Windows.Forms; namespace ClassLibrary1 { /// <summary> /// ToolStripNumericUpDown /// </summary> [ToolboxBitmap(typeof(NumericUpDown), "NumericUpDown")] public sealed class ToolStripNumericUpDown : ToolStripControlHost { #region コンストラクタ /// <summary> /// コンストラクタ /// </summary> public ToolStripNumericUpDown() : base(new NumericUpDown() { TextAlign = HorizontalAlignment.Right , Maximum = 128, Minimum = 2}) {} public ToolStripNumericUpDown(string name) : base(new NumericUpDown() { TextAlign = HorizontalAlignment.Right , Maximum = 128, Minimum = 2}, name) {} #endregion #region プロパティ /// <summary> /// ホストしているNumericUpDownコントロール /// </summary> public NumericUpDown NumericUpDown { get { return (NumericUpDown)Control; } } /// <summary> /// ホストしているコントロールのValueの値を取得または設定します。 /// </summary> public decimal Value { get { return NumericUpDown.Value; } set { NumericUpDown.Value = value; } } /// <summary> /// ホストしているコントロールのTextの値を取得または設定します。 /// </summary> public string NumericUpDownText { get { return NumericUpDown.Text; } set { NumericUpDown.Text = value; } } #endregion #region イベント /// <summary> /// Valueの値が変化した /// </summary> public event EventHandler ValueChanged; /// <summary> /// ValueChangedイベント発生 /// </summary> /// <param name="sender"></param> /// <param name="e"></param> private void NumericUpDown_OnValueChanged(object sender, EventArgs e) { if (ValueChanged != null) { ValueChanged(this, e); } } #endregion #region オーバーライド /// <summary> /// ホストしているNumericUpDownのイベントをサブスクライブします。 /// </summary> /// <param name="control"></param> protected override void OnSubscribeControlEvents(System.Windows.Forms.Control control) { base.OnSubscribeControlEvents(control); NumericUpDown chkControl = (NumericUpDown)control; chkControl.ValueChanged += new EventHandler(NumericUpDown_OnValueChanged); } /// <summary> /// ホストしているNumericUpDownのイベントをアンサブスクライブします。 /// </summary> /// <param name="control"></param> protected override void OnUnsubscribeControlEvents(System.Windows.Forms.Control control) { base.OnUnsubscribeControlEvents(control); NumericUpDown chkControl = (NumericUpDown)control; chkControl.ValueChanged -= new EventHandler(NumericUpDown_OnValueChanged); } #endregion } }
ColorComboBox
オーナードローで色分けコンボボックス
using System.Collections.Generic; using System.Linq; using System.ComponentModel; using System.Drawing; using System.Windows.Forms; namespace ClassLibrary1 { public sealed class SplitColorComboBox : ComboBox { private const int MarginItemToColorBox = 2; private const int MarginColorBoxToString = 1; private const int MarginItemToString = MarginItemToColorBox + MarginColorBoxToString; /// <summary> /// コンストラクタ /// </summary> public SplitColorComboBox() { this.DropDownStyle = ComboBoxStyle.DropDownList; this.DrawMode = DrawMode.OwnerDrawFixed; this.ItemHeight = this.Font.Height + MarginItemToString * 2; this.DropDownWidth = 180; InitColorCombo(); this.SelectedIndex = 0; } private bool _displayColorName = true; /// <summary> /// 色名を表示するか否かを取得または設定します。 /// </summary> [DefaultValue(true)] public bool DisplayColorName { get { return _displayColorName; } set { _displayColorName = value; } } private Dictionary<string, int> _dicColor = new Dictionary<string, int>(); /// <summary> /// 現在選択中の色を取得または設定します。 /// </summary> public Color CurrentColor { get { return Color.FromName(this.Items[SelectedIndex].ToString()); } set { SelectedIndex = _dicColor[value.Name]; } } /// <summary> /// コンボボックスにKnownColor列挙体に存在する色名を設定します。 /// </summary> private void InitColorCombo() { foreach (var Item in System.Enum.GetNames(typeof(KnownColor)).Select( (x,i) => new {Value = x, Index = i })) { this.Items.Add(Item.Value); _dicColor.Add(Item.Value,Item.Index); } } /// <summary> /// OnDrawItem /// </summary> /// <param name="e"></param> protected override void OnDrawItem(DrawItemEventArgs e) { if (e.Index == -1) return; var itemColor = Color.FromName(this.Items[e.Index].ToString()); var backColor = itemColor; Rectangle rect = new Rectangle(MarginItemToColorBox , MarginItemToColorBox , e.Bounds.Width - MarginItemToColorBox * 2 , e.Bounds.Height - MarginItemToColorBox * 2); PointF colorNameLocation = new PointF(rect.Left + MarginColorBoxToString, rect.Top + MarginColorBoxToString); using (var bmp = new Bitmap(e.Bounds.Width, e.Bounds.Height)) using (var g = Graphics.FromImage(bmp)) using (var foreBrush = new SolidBrush(GetForeColor(itemColor))) { DrawFrameBox(g, Color.Black, backColor, rect); if (DisplayColorName) { if (e.State == (DrawItemState.Focus | DrawItemState.Selected) || e.State == DrawItemState.Selected) g.DrawString(itemColor.Name, this.Font, foreBrush, colorNameLocation); } e.Graphics.DrawImage(bmp, e.Bounds); } } /// <summary> /// 枠付きの塗り潰しボックスを描画します。 /// </summary> /// <param name="g"></param> /// <param name="frameColor"></param> /// <param name="backColor"></param> /// <param name="rect"></param> private void DrawFrameBox(Graphics g, Color frameColor, Color backColor, Rectangle rect) { using (var backBrush = new SolidBrush(backColor)) using (var framePen = new Pen(frameColor)) { g.FillRectangle(backBrush, rect); g.DrawRectangle(framePen, rect); } } /// <summary> /// 項目の色の明るさに応じて、色名を表示する文字色を取得します。 /// </summary> /// <param name="itemColor"></param> /// <returns></returns> private Color GetForeColor(Color itemColor) { if (itemColor.GetBrightness() >= 0.35) return Color.Black; return Color.White; } } }
ToolStripSplitColorComboBox
ToolStripにSplitColorComboBoxを表示するためのもの
using System; using System.ComponentModel; using System.Drawing; using System.Windows.Forms; namespace ClassLibrary1 { /// <summary> /// ToolStripSplitColorComboBox /// </summary> public class ToolStripSplitColorComboBox : ToolStripControlHost { #region コンストラクタ /// <summary> /// コンストラクタ /// </summary> public ToolStripSplitColorComboBox() : base(new ColorComboBox()) {} public ToolStripSplitColorComboBox(string name) : base(new ColorComboBox(), name) {} #endregion #region プロパティ /// <summary> /// ホストしているColorComboBoxコントロール /// </summary> public ColorComboBox ColorComboBox { get { return (ColorComboBox)Control; } } /// <summary> /// ホストしているコントロールのCurrentColorの値を取得します。 /// </summary> public Color CurrentColor { get { return ColorComboBox.CurrentColor; } set { ColorComboBox.CurrentColor = value; } } #endregion #region イベント /// <summary> /// SelectedIndexの値が変化した /// </summary> [Category("動作")] public event EventHandler SelectedIndexChanged; /// <summary> /// ValueChangedイベント発生 /// </summary> /// <param name="sender"></param> /// <param name="e"></param> private void ColorComboBox_OnSelectedIndexChanged(object sender, EventArgs e) { if (SelectedIndexChanged != null) SelectedIndexChanged(this, e); } #endregion #region オーバーライド /// <summary> /// ホストしているColorComboBoxのイベントをサブスクライブします。 /// </summary> /// <param name="control"></param> protected override void OnSubscribeControlEvents(System.Windows.Forms.Control control) { base.OnSubscribeControlEvents(control); ColorComboBox chkControl = (ColorComboBox)control; chkControl.SelectedIndexChanged += new EventHandler(ColorComboBox_OnSelectedIndexChanged); } /// <summary> /// ホストしているColorComboBoxのイベントをアンサブスクライブします。 /// </summary> /// <param name="control"></param> protected override void OnUnsubscribeControlEvents(System.Windows.Forms.Control control) { base.OnUnsubscribeControlEvents(control); ColorComboBox chkControl = (ColorComboBox)control; chkControl.SelectedIndexChanged -= new EventHandler(ColorComboBox_OnSelectedIndexChanged); } #endregion } }
迷路の描画をスクロール可能にするための対応
迷路の描画についてスクロールしても描画が崩れないようにするために、
面倒くさいけど、スクロール対応Panelを作ります。
それもこれも標準のPanelが空気読めなさすぎによるためのものです。
using System.Drawing; using System.Windows.Forms; namespace ClassLibrary1 { /// <summary> /// ScrollPanle /// </summary> [ToolboxBitmap(typeof(Panel), "Panel")] public sealed class ScrollPanle : Panel { public new event PaintEventHandler Paint; private readonly DrawControl _drawctrl = null; public ScrollPanle() { _drawctrl = new DrawControl(this) { Size = new System.Drawing.Size(this.Width, this.Height) }; Controls.Add(_drawctrl); AutoScroll = true; } public Size DrawScrollControlSize { get { return _drawctrl.Size; } set { _drawctrl.Size = value; } } private sealed class DrawControl : Control { private ScrollPanle _parent; public DrawControl(ScrollPanle parent) { _parent = parent; SetStyle(ControlStyles.AllPaintingInWmPaint | ControlStyles.UserPaint | ControlStyles.DoubleBuffer | ControlStyles.ResizeRedraw, true); } protected override void OnPaint(PaintEventArgs e) { base.OnPaint(e); if (_parent.DesignMode) return; var g = e.Graphics; g.FillRectangle(new Pen(_parent.BackColor).Brush, ClientRectangle); _parent.Paint(this, e); } } } }
カーソルチェンジャー
本来の使い方ではないIDisposableの使い方。
まぁ、本来の使い方ではないとはいえ、ありがちな実装ですね。
using System; using System.Windows.Forms; namespace ClassLibrary1 { /// <summary> /// カーソルチェンジャー /// </summary> public sealed class CursorChanger : IDisposable { private Control control; private Cursor oldCursor; /// <summary> /// コンストラクタ /// </summary> /// <param name="control">カーソル適用対象</param> /// <param name="newCursor">新しいカーソル</param> public CursorChanger(Control control, Cursor newCursor) { this.control = control; this.oldCursor = this.control.Cursor; FindTopParent(control).Cursor = newCursor; } /// <summary> /// デストラクタ /// </summary> ~CursorChanger() { Dispose(false); } #region IDisposableメンバ private bool disposed = false; public void Dispose() { Dispose(true); GC.SuppressFinalize(this); } public void Dispose(bool disposing) { if (!disposed) { if (disposing) { FindTopParent(control).Cursor = oldCursor; } disposed = true; } } #endregion /// <summary> /// 対象コントロールについて、TopParentを取得します。 /// </summary> /// <param name="control">対象コントロール</param> /// <returns>TopParent</returns> private Control FindTopParent(Control control) { var parent = control.Parent; if (parent == null) return control; return (FindTopParent(parent)); } } }
迷路のフォームの実装
最後にFormの実装です。
いままで作ってきたクラスをごにょごにょすれば完成です。
using System; using System.Collections.Generic; using System.Drawing; using System.Drawing.Drawing2D; using System.Linq; using System.Threading; using System.Windows.Forms; using ClassLibrary1; namespace WindowsFormsApplication1 { public partial class frmMaze : Form { private IMaze _maze = new Excavation(); public frmMaze() { InitializeComponent(); this.SetStyle(ControlStyles.SupportsTransparentBackColor, true); this.tssccmbCellColor.CurrentColor = Cell.CellColor; this.tssccmbWallColor.CurrentColor = Cell.WallColor; this.tssccmbSolveColor.CurrentColor = Cell.SolveColor; SetEvent(); using (var cur = new CursorChanger(this,Cursors.WaitCursor)) { _maze.Generate(); _maze.MazeSolveComplete += new EventHandler(MazeComplete); } SetFormSize(); } /// <summary> /// イベント設定 /// </summary> private void SetEvent() { this.pnlMaze.Paint += (sender, e) => this.pnlMaze_Paint(sender, e); this.tssccmbCellColor.SelectedIndexChanged += (sender, e) => tssccmbCellColor_SelectedIndexChanged(sender, e); this.tssccmbWallColor.SelectedIndexChanged += (sender, e) => tssccmbWallColor_SelectedIndexChanged(sender, e); this.tssccmbSolveColor.SelectedIndexChanged += (sender, e) => tssccmbSolveColor_SelectedIndexChanged(sender, e); this.tsnrcCellSize.ValueChanged += (sender, e) => tsnrcCellSize_ValueChanged(sender, e); } private void SetFormSize() { var header = this.toolStripTop.Height; var footer = this.toolStripBottom.Height; SetBounds(this.Left , this.Top , Excavation.Dimension.Height * Cell.CellSize + Cell.Padding * 3 , Excavation.Dimension.Width * Cell.CellSize + Cell.Padding * 3 + header + footer + 30); this.pnlMaze.DrawScrollControlSize = new Size(this.pnlMaze.Width, this.pnlMaze.Height); } private void pnlMaze_Paint(object sender, PaintEventArgs e) { _maze.Draw(e.Graphics); } private delegate void Action(); private void MazeComplete(object sender, EventArgs e) { if (this.IsRestrictedWindow) { this.Refresh(); this.Cursor = Cursors.Default; return; } this.Invoke(new Action(() => { this.Refresh(); this.Cursor = Cursors.Default; })); } private void tsbtnGenerate_Click(object sender, EventArgs e) { var col = Convert.ToInt32(this.tsnrcCol.Value); var row = Convert.ToInt32(this.tsnrcRow.Value); Excavation.Dimension = new Size(col, row); Cell.CellSize = Convert.ToInt32(this.tsnrcCellSize.Value); _maze.Initialize(Excavation.Dimension); _maze.Generate(); SetFormSize(); Invalidate(true); } private void tsbtnSolve_Click(object sender, EventArgs e) { _maze.Reset(); this.Cursor = Cursors.WaitCursor; new Thread(new ThreadStart(_maze.Solve)).Start(); } private void tssccmbCellColor_SelectedIndexChanged(object sender, EventArgs e) { Cell.CellColor = this.tssccmbCellColor.CurrentColor; this.pnlMaze.Invalidate(true); } private void tssccmbWallColor_SelectedIndexChanged(object sender, EventArgs e) { Cell.WallColor = this.tssccmbWallColor.CurrentColor; this.pnlMaze.Invalidate(true); } private void tssccmbSolveColor_SelectedIndexChanged(object sender, EventArgs e) { Cell.SolveColor = this.tssccmbSolveColor.CurrentColor; this.pnlMaze.Invalidate(true); } private void tsnrcCellSize_ValueChanged(object sender, EventArgs e) { Cell.CellSize = (int)this.tsnrcCellSize.Value; this.pnlMaze.Invalidate(true); SetFormSize(); } } }
という感じです。お疲れ様でした。
迷路の解法部分を抽象化したり、迷路の生成部分と解法をプラグイン化したりとか
いろいろとやり残しがあるので、興味があるかたは改造したりして遊んでみてください。
自分も気が向いたら、また遊んでみます。
レーベンシュタイン距離とN-gramモデルのアルゴリズム。それは擬似Google Suggestっぽい何か。
きっかけは
レーベンシュタイン距離 - shin5papaの日記
http://d.hatena.ne.jp/shin5papa/20090311/1236745197
レーベンシュタイン距離とN-gramモデルで、擬似的なGoogle Suggest
レーベンシュタイン距離を使うことによって、擬似的にGoogle先生の「もしかして」とか、Google Suggestっぽいことができそうかなーと思って、面白そうなのでお勉強してみた。
PHPでは標準で関数があるのかー。んー、面白いですねコレ。ということで、さっそくC#で書いてみることにしました。
ただ、このレーベンシュタイン距離のみの判定だけでは、距離が等しい結果が複数あるような場合の結果が、
イマイチ納得のゆくものにはならなかったので、更に N-gram *1による共起頻度での判定も併用することにしました。
using System; namespace ClassLibrary1 { /// <summary> /// レーベンシュタイン距離 /// </summary> public static class LevenshteinDistance { public static int Compute(string s, string t) { if (s == null) throw new ArgumentNullException("s"); if (t == null) throw new ArgumentNullException("t"); int x = s.Length; int y = t.Length; if (x == 0) return y; if (y == 0) return x; int[,] d = new int[x + 1, y + 1]; for (int i = 0; i <= x; d[i, 0] = i++) ; for (int j = 0; j <= y; d[0, j] = j++) ; int cost = default(int); for (int i = 1; i <= x; i++) { for (int j = 1; j <= y; j++) { cost = (s.Substring(i - 1, 1) != t.Substring(j - 1, 1) ? 1 : 0); d[i, j] = Math.Min(Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1) , d[i - 1, j - 1] + cost); } } return d[x, y]; } } }
using System; using System.Collections.Generic; namespace ClassLibrary1 { /// <summary> /// N-gram /// </summary> public class Ngram { /// <summary> /// Unigram /// </summary> /// <param name="s"></param> /// <param name="t"></param> /// <returns></returns> public static decimal CompareUnigram(string s, string t) { return Compare(1, s, t); } /// <summary> /// Bigram /// </summary> /// <param name="s"></param> /// <param name="t"></param> /// <returns> /// </returns> public static decimal CompareBigram(string s, string t) { return Compare(2, s, t); } /// <summary> /// Trigram /// </summary> /// <param name="s"></param> /// <param name="t"></param> /// <returns></returns> public static decimal CompareTrigram(string s, string t) { return Compare(3, s, t); } private static decimal Compare(int n, string s, string t) { if (s == null) throw new ArgumentNullException("s"); if (t == null) throw new ArgumentNullException("t"); var noise = new List<string>(); for (int i = 0; i < s.Length - (n - 1); i++) { var ngitem = s.Substring(i, n); if (!noise.Contains(ngitem)) { noise.Add(ngitem); } } if (noise.Count == 0) return 0; int coincidence = 0; for (int i = 0; i < t.Length - (n - 1); i++) { var ngitem = t.Substring(i, n); if (noise.Contains(ngitem)) { coincidence++; } } return (decimal)coincidence / noise.Count; } } }
もしかして…
using System; using System.Collections.Generic; namespace ClassLibrary1 { public static class Utility { /// <summary> /// もしかして… /// </summary> /// <param name="s"></param> /// <param name="source"></param> /// <returns></returns> public static string GetPossibility(string s, IEnumerable<string> source) { if (s == null) throw new ArgumentNullException("s"); if (source == null) throw new ArgumentNullException("source"); List<string> possibilityList = new List<string>(); int mincost = int.MaxValue; string moshikashite = null; foreach (string t in source) { int cost = LevenshteinDistance.Compute(s, t); if (cost == 0) return t; if (cost <= mincost) { mincost = cost; possibilityList.Add(t); } } decimal k = -1m; foreach (string t in possibilityList) { decimal result = Ngram.CompareBigram(s, t); if (k == -1m || result > k) { k = result; moshikashite = t; } } return moshikashite; } } }
もしかして…ほにゃらら的な何か
using System; using System.Collections.Generic; using System.Linq; using ClassLibrary1; namespace ConsoleApplication1 { class program { public static void Main() { List<string> list = new List<string>(); list.Add("クロワッサン"); list.Add("クリイム"); list.Add("クレーム"); list.Add("クライム"); list.Add("コロネパン"); list.Add("クリーナ"); list.Add("リクーム"); list.Add("クローバースタジオ"); list.Add("クローム"); list.Add("クラウド"); list.Add("クリゴハン"); list.Add("クリキントン"); list.Add("クリームパン"); list.Add("クリスティーナ"); list.Add("クロノトリガー"); Console.WriteLine(">>もしかして…ほにゃらら的な何か"); Console.WriteLine(); while (true) { Console.WriteLine("何かキーワードを入力してください... ( exit で終了します。)"); var input = Console.ReadLine(); if (input == "exit") break; var candidate = (from s in list let ld = LevenshteinDistance.Compute(input, s) let bigram = Ngram.CompareBigram(input, s) orderby bigram descending orderby ld ascending select new { LD = ld, Value = s }).Take(5); foreach (var item in candidate) Console.WriteLine("LD [{0}] : {1}", item.LD, item.Value); Console.WriteLine(); Console.WriteLine("もしかして…‘{0}’", Utility.GetPossibility(input, list)); if (!list.Contains(input)) list.Add(input); Console.WriteLine(); } } } }
Google SuggestではN-gramと形態素解析を併用して実現されているようですね。
形態素解析を使っているという点で、今回の作ったやつとはまったくの別物。サンプルはあくまで擬似に過ぎない。
ちなみに、Google Suggestで使われている形態素解析システムはGoogleお手製のではなくて、
他社のベイシス・テクノロジー社製のものを使っているようです。
Googleはなんでもセルフオーダーメイドするイメージがあったから、ちょっと意外。
おまけ
残念ながら商用利用は禁止されているようですが、
Googleから大規模日本語 N-gramデータ*2が提供されています。
http://googlejapan.blogspot.com/2007/11/N-gram.html
そういえば、Sennaなんてのも話題になっていたのを思い出しました。
http://qwik.jp/senna/FrontPageJ.html
拡張ユークリッド互除法も再帰で書いた方が自然に見える
最適化のために最大公約数を求める必要があって、
ユークリッド互除法と拡張ユークリッド互除法を書いたので、チラ裏に残しておく*1。
ユークリッド互除法
まずはよく見る実装をC#で
public static int Gcd(int a, int b)
{
while (b != 0)
{
int r = a % b;
a = b;
b = r;
}
return a;
}
実にありがちな実装なのですが、どう見てもダサすぎ。
これってつまり、こういうことだよね。
public static int GcdR(int a, int b)
{
if (b == 0) return a;
return GcdR(b, a % b);
}
スッキリしました。
何を思ったか、久々にHaskellでも書いてみることに。
って、実はHaskellでは最初からgcd関数が定義されていたりする。
http://www.zvon.org/other/haskell/Outputprelude/gcd_f.html
なので
main :: IO() main = return (gcd 1029 1071) >>= print
これで、21って答えが出ちゃったりする。
でも、自分で書いてみることに意味があるよね。たぶん。
gcd2 :: Int -> Int -> Int gcd2 a 0 = a gcd2 a b = gcd2 b (rem a b)
こんだけ。書くまでもなかった。
拡張ユークリッド互除法
よく見る実装をC#で。
public static int GcdEx(int a, int b)
{
int x1 = 0;
int x2 = 1;
int y1 = 1;
int y2 = 0;
int r1 = b;
int r2 = a;
while (true)
{
if (r1 == 0) return r2;
//Math.DivRemなんてのもあるけど
int q = (int)Math.Floor((double)(r2 / r1));
int r = r2 % r1;
int x = x2 - q * x1;
int y = y2 - q * y1;
if (r == 0) break;
x2 = x1;
x1 = x;
y2 = y1;
y1 = y;
r2 = r1;
r1 = r;
}
return r1;
}
うへ。これはひどい・・・。
なんというローカル変数の乱立ｗｗｗ
これも再帰で表現したほうがスッキリできそうです。
実際に書いてみると、こんな感じでした。
private delegate TResult Func<T1, T2, T3, T4, T5, T6,TResult>(T1 a1, T2 a2, T3 a3, T4 a4, T5 a5, T6 a6);
public static int GcdExR(int a, int b)
{
Func<int, int, int, int, int, int, int> f = null;
f = (a2, b2, w2, x2, y2, z2) =>
{
if (b2 == 0) return a2;
return f(b2, a2 % b2, x2, (w2 - a2) / b2 * x2, z2, (y2 - a2) / b2 * z2);
};
return f(a, b, 1, 0, 0, 1);
}
いざ書いてみると、引数を６つとるFuncがないことに気付く…ｗ
一見わかりにくそうに見えるかもしれませんが、個人的には上に書いたよく見る実装よりも、
こちらの方が好みです。書き方的に「今風」っぽいというのも含めて。
あと、ラムダ式ばっか書いてると、匿名delegateでの旧式な書き方を忘れ気味であることに気付いた俺ガイル。
締めにHaskellでも
gcdex :: Int -> Int -> Int gcdex a b = gcdex' a b 1 0 0 1 where gcdex' a 0 _ _ _ _ = a gcdex' a b w x y z = gcdex' b r y z (w-y*q) (x-z*q) where (q, r) = quotRem a b
こうしてみると、やっぱHaskellはクールだなあ。
*1:負の数に関しては考えていません
