オブジェクトの非正規化
オブジェクト指向で有限オートマトンを表現してみるで、オブジェクト指向プログラミングでよくある問題について書きました。むろん頻繁に発生するこの問題は、解決方法もあります。今回はその手法について解説します。それと、学習方法の補足説明をします。
オブジェクト指向で有限オートマトンを表現してみるで指摘した問題点は、型システムに依存した考え方をすることにより発生する問題です。これは、オブジェクト指向初心者にありがちな間違いです。初心者は定義をそのままオブジェクトにしがちです。定義をそのまま型として表現すると、この様なプログラムを書いてしまいます。
解決する方法は簡単です。ちゃんと、オブジェクト指向分析と、オブジェクト指向設計をすることです。分析と設計を正しく行えば、硬直したプログラムは作りません。何故ならば、分析を通して本質を見極め、設計を通して賢いオブジェクトを考えるからです。これから、簡単な分析と設計をしてみます。
有限オートマトンを分析すると、各集合{ Q, Σ, δ, q0, F }と出力との関係が大事です。また、今回の目的を考えると、「有限オートマトンを学習すること」です。従って、{ Q, Σ, δ, q0, F }は必ず指定する方式にする必要があります。そうしないと、有限オートマトンの学習に抜けが生じる恐れがあります。
次に設計をします。オブジェクト指向設計は、適切に実装できるようにオブジェクトを考える段階です。オブジェクトの実装方法を検討すると、この要件で有限オートマトンの各状態を型として扱うのはやりすぎだと思います。何故ならば、実装が面倒ですし、細部に気を取られて有限オートマトンの概念を覚えるという本題が有耶無耶になる恐れがあるからです。状態オブジェクトを工夫し、各状態はインスタンスとして扱うのが適切だと考えられます。状態遷移関数については、状態オブジェクト・オートマトンオブジェクト・入力オブジェクトのどれにも依存しない形が良いでしょう。従って、柔軟性も考慮し別のオブジェクトとして扱うのがベストです。なお、私は概念を型に当てはめる考える事をオブジェクトの正規化、逆に型にしないでインスタンスで対応することをオブジェクトの非正規化と呼んでいます。
簡単ながら、これで分析と設計が終わったので、その結果を踏まえて実装してみます。
この記事を読んだ人の中には、随分と面倒だと思った人が居る事でしょう。ですが、実際のところは、全然面倒ではありません。慣れれば一瞬でできる事です。私は慣れているので、今回紹介したプログラムのイメージが直接瞬時に出てきます。ブログに書くときは、間違ったプログラムを逆算して書きました。ちょっと考えて本を読んでいる程度なので、全然負担に感じません。感覚的には小説を読むとき、風景などをイメージしながら読んでいると同じです。こうやって改めて文章で読むと、難解に感じるでしょうが、読書家ならば普通にしている事なので簡単です。おなかつ、学習効果も高いので、落ち着いて専門書を読むときに試してみてください。
オブジェクト指向で有限オートマトンを表現してみるで指摘した問題点は、型システムに依存した考え方をすることにより発生する問題です。これは、オブジェクト指向初心者にありがちな間違いです。初心者は定義をそのままオブジェクトにしがちです。定義をそのまま型として表現すると、この様なプログラムを書いてしまいます。
解決する方法は簡単です。ちゃんと、オブジェクト指向分析と、オブジェクト指向設計をすることです。分析と設計を正しく行えば、硬直したプログラムは作りません。何故ならば、分析を通して本質を見極め、設計を通して賢いオブジェクトを考えるからです。これから、簡単な分析と設計をしてみます。
有限オートマトンを分析すると、各集合{ Q, Σ, δ, q0, F }と出力との関係が大事です。また、今回の目的を考えると、「有限オートマトンを学習すること」です。従って、{ Q, Σ, δ, q0, F }は必ず指定する方式にする必要があります。そうしないと、有限オートマトンの学習に抜けが生じる恐れがあります。
次に設計をします。オブジェクト指向設計は、適切に実装できるようにオブジェクトを考える段階です。オブジェクトの実装方法を検討すると、この要件で有限オートマトンの各状態を型として扱うのはやりすぎだと思います。何故ならば、実装が面倒ですし、細部に気を取られて有限オートマトンの概念を覚えるという本題が有耶無耶になる恐れがあるからです。状態オブジェクトを工夫し、各状態はインスタンスとして扱うのが適切だと考えられます。状態遷移関数については、状態オブジェクト・オートマトンオブジェクト・入力オブジェクトのどれにも依存しない形が良いでしょう。従って、柔軟性も考慮し別のオブジェクトとして扱うのがベストです。なお、私は概念を型に当てはめる考える事をオブジェクトの正規化、逆に型にしないでインスタンスで対応することをオブジェクトの非正規化と呼んでいます。
簡単ながら、これで分析と設計が終わったので、その結果を踏まえて実装してみます。
using System;
using System.Collections.Generic;
using System.Linq;
//有限オートマトン( FA : finite automaton )
class Fa<StateT, InputT, ValueT>
where StateT : FaState<ValueT>
{
//FAの定義に必要なフィールド
private IEnumerable<StateT> _stateSet;
private IEnumerable<InputT> _inputSet;
private Converter<StateT, InputT, ValueT> _stateTransition;
private StateT _firstState;
private IEnumerable<StateT> _lastStateSet;
//現在の状態を覚えておく必要がある
private StateT _currentState;
//受理
public bool IsAccept
{
get
{
return this._lastStateSet.Contains( this._currentState );
}
}
//FAの定義（ Q, Σ, δ, q0, F ）でインスタンスを生成する
public Fa(
IEnumerable<StateT> stateSet,
IEnumerable<InputT> inputSet,
Converter<StateT, InputT, ValueT> stateTransition,
StateT firstState,
IEnumerable<StateT> lastStateSet )
{
this._stateSet = stateSet;
this._inputSet = inputSet;
this._stateTransition = stateTransition;
this._firstState = firstState;
this._lastStateSet = lastStateSet;
this._currentState = firstState;
}
//記号1つを指定して現在の状態を遷移させる
public bool StateTransition( InputT input )
{
if ( !this._inputSet.Contains( input ) )
throw new ArgumentException(
input + "は想定外です" );
this._currentState =
this._stateTransition.NextState(
this._currentState, input );
return this.IsAccept;
}
}
//オートマトンの状態を表わす抽象オブジェクト
class FaState<T>
{
//状態の識別子
private int _id;
public int ID
{
get { return _id; }
}
//状態が保持する値
private T _value;
public T Value
{
get { return _value; }
}
//IDと値は必須とする
public FaState( int id, T value )
{
this._id = id;
this._value = value;
}
//等価性を判定する
public override bool Equals( object obj )
{
FaState<T> other = obj as FaState<T>;
if ( other == null ) return false;
if ( this.ID != other.ID ) return false;
if ( !this.Value.Equals( other.Value ) ) return false;
return true;
}
//本題と関係ないのでハッシュコードはいい加減にしている
public override int GetHashCode()
{
return (
this.ID.ToString() +
this.Value.ToString()
).GetHashCode();
}
}
//状態遷移関数の役割を果たすオブジェクト
abstract class Converter<StateT, InputT, ValueT>
{
//次の状態を取得
public abstract StateT NextState(
StateT state, InputT input );
}
//サンプルに特化した状態遷移関数の定義
class SampleConvertoer
: Converter<FaState<int>, int, int>
{
public override FaState<int> NextState(
FaState<int> state, int input )
{
if ( input == 0 )
return new FaState<int>( state.ID, state.Value );
if ( input == 100 )
return new FaState<int>(
state.ID + 1,
state.Value + input );
throw new ArgumentException(
String.Format( "状態：{0}と入力値{1}の組み合わせは想定外です。",
state, input ) );
}
}
class Sample
{
static void Main()
{
//300円の商品を扱う機械
Console.WriteLine( "300円の商品を扱う機械の状態遷移" );
Test( new FaState<int>( 3, 300 ) );
Console.WriteLine( );
//400円の商品を扱う機会
Console.WriteLine( "400円の商品を扱う機械の状態遷移" );
Test( new FaState<int>( 4, 400 ) );
Console.WriteLine( );
}
static void Test( FaState<int> maxValue )
{
//自動販売機の有限オートマトンを用意する
Fa<FaState<int>, int, int> obj = Init( maxValue );
//100円投入してみる
int input = 100;
Console.WriteLine( "{0}円投入しました。商品は出てきた？{1}",
input, obj.StateTransition( input ) );
//もう100円投入
input = 100;
Console.WriteLine( "{0}円投入しました。商品は出てきた？{1}",
input, obj.StateTransition( input ) );
//投入したふりをしてみる
input = 0;
Console.WriteLine( "{0}円投入しました。商品は出てきた？{1}",
input, obj.StateTransition( input ) );
//もう100円を投入
input = 100;
Console.WriteLine( "{0}円投入しました。商品は出てきた？{1}",
input, obj.StateTransition( input ) );
}
static Fa<FaState<int>, int, int> Init(
FaState<int> lastValue )
{
//機械が取りうる状態
var state = new FaState<int>[ ] {
new FaState<int>( 0, 0 ),
new FaState<int>( 1, 100 ),
new FaState<int>( 2, 200 ),
new FaState<int>( 3, 300 )
};
//入力できる記号
var input = new int[ ] { 0, 100 };
//状態遷移関数
SampleConvertoer convert = new SampleConvertoer( );
//初期状態
var first = new FaState<int>( 0, 0 );
//最終状態
var last = new FaState<int>[ ] { lastValue };
//作成（ FA = { Q, Σ, δ, q0, F } ）
return new Fa<FaState<int>, int, int>(
state, input, convert, first, last );
}
}
オブジェクト指向で有限オートマトンを表現してみるのサンプルと比べると、随分とすっきりして、有限オートマトンの定義が分かりやすくなったと思います。この記事を読んだ人の中には、随分と面倒だと思った人が居る事でしょう。ですが、実際のところは、全然面倒ではありません。慣れれば一瞬でできる事です。私は慣れているので、今回紹介したプログラムのイメージが直接瞬時に出てきます。ブログに書くときは、間違ったプログラムを逆算して書きました。ちょっと考えて本を読んでいる程度なので、全然負担に感じません。感覚的には小説を読むとき、風景などをイメージしながら読んでいると同じです。こうやって改めて文章で読むと、難解に感じるでしょうが、読書家ならば普通にしている事なので簡単です。おなかつ、学習効果も高いので、落ち着いて専門書を読むときに試してみてください。
スポンサーサイト
