スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

オブジェクトの非正規化

 オブジェクト指向で有限オートマトンを表現してみるで、オブジェクト指向プログラミングでよくある問題について書きました。むろん頻繁に発生するこの問題は、解決方法もあります。今回はその手法について解説します。それと、学習方法の補足説明をします。
 オブジェクト指向で有限オートマトンを表現してみるで指摘した問題点は、型システムに依存した考え方をすることにより発生する問題です。これは、オブジェクト指向初心者にありがちな間違いです。初心者は定義をそのままオブジェクトにしがちです。定義をそのまま型として表現すると、この様なプログラムを書いてしまいます。
 解決する方法は簡単です。ちゃんと、オブジェクト指向分析と、オブジェクト指向設計をすることです。分析と設計を正しく行えば、硬直したプログラムは作りません。何故ならば、分析を通して本質を見極め、設計を通して賢いオブジェクトを考えるからです。これから、簡単な分析と設計をしてみます。
 有限オートマトンを分析すると、各集合{ 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 );
    }
}

オブジェクト指向で有限オートマトンを表現してみるのサンプルと比べると、随分とすっきりして、有限オートマトンの定義が分かりやすくなったと思います。
 この記事を読んだ人の中には、随分と面倒だと思った人が居る事でしょう。ですが、実際のところは、全然面倒ではありません。慣れれば一瞬でできる事です。私は慣れているので、今回紹介したプログラムのイメージが直接瞬時に出てきます。ブログに書くときは、間違ったプログラムを逆算して書きました。ちょっと考えて本を読んでいる程度なので、全然負担に感じません。感覚的には小説を読むとき、風景などをイメージしながら読んでいると同じです。こうやって改めて文章で読むと、難解に感じるでしょうが、読書家ならば普通にしている事なので簡単です。おなかつ、学習効果も高いので、落ち着いて専門書を読むときに試してみてください。
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメントの投稿

非公開コメント

プロフィール

インドリ

Author:インドリ
みなさん、はじめまして、
コンニチハ。

ボクは、無限の夢(infinity dream)を持つネタ好きな虹色の鳥インドリ(in dre)です。
色々な情報処理技術を啄ばむから楽しみにしてね。

http://twitter.com/indori
は別人による嫌がらせ行為です。
私とは関係ないので注意して下さい。
次はなりすましブログなどをするかもしれませんが、ここ以外でブログをするつもりがないので、ここ以外にインドリのブログがあったとしても無視してください。


何度言っても分からない人がいるので、ここにコメント欄へ書き込むときの注意事項を書きます。


一、社会人としてのマナーをわきまえましょう。
一、妄想に基づく書き込みを止めてください。
一、暴言の類は書かないで下さい。
一、某誹謗中傷サイトの書き込みは彼らの妄想に基づく書き込みですから無視して、ここへ書き込まないで下さい。
一、コメント書く前に他のコメントよく読んでから行って下さい。
一、言いがかかり等の行為を禁止します。
一、その他常識的に考えて迷惑なコメントはしないで下さい。


以上のルールを守れない人のコメントは削除します。



利用上の注意
ここに紹介してある文章およびプログラムコードは正確であるように心がけておりますが、内容を保証するものではありません。当サイトの内容によって生じた損害については、一切の責任を負いませんので御了承ください。


執筆したCodeZineの記事


【VB.NETで仮想CPUを作ろう】

  1. VB.NETで仮想CPUを作ろう
  2. レジスタの実装
  3. 仮想CPUのGUI化
  4. テストドライバの改良
  5. CPUの基礎動作の実装
  6. MOV命令の実装
  7. ADD命令実装
  8. SUB命令実装
  9. INC命令&DEC命令の実装と命令長
  10. MLU命令の実装とModR/Mについて
  11. DIV命令の実装とイベント設計について
  12. 機械語駆動式 関数電卓を作ろう!
  13. 機械語駆動式 関数電卓を作ろう! 解答編(前半)
  14. 機械語駆動式 関数電卓を作ろう! 解答編(後半)


【仮想ネットワーク実装でTCP/IPを学ぼう】
  1. TCP/IPの基礎と勘所
  2. ネットワークアクセス層の勘所
  3. インターネット層の勘所
  4. トランスポート層の勘所
  5. アプリケーション層の勘所
  6. セキュリティの基礎と仮想ネットワークの仕様
  7. GDI+と独自プロトコルの定義



【並列化】
インテル Parallel Studioを使って並列化プログラミングを試してみた
並列プログラミングの効率的なデバッグを実現する「Parallel Inspector」


【TBBシリーズ】
  1. インテル スレッディング・ビルディング・ブロックの概要
  2. インテルTBBから学ぶループの並列化
  3. スレッドセーフとインテルTBBのコンテナ
  4. インテルTBBのスレッドクラス


【OpenMPシリーズ】
  1. OpenMPの基礎構文
  2. OpenMPの実行時ライブラリと並列ループ
  3. OpenMPのメモリモデルとfork- joinモデル

最近の記事
最近のコメント
月別アーカイブ
カテゴリ
Ada (9)
COBOL (5)
C (9)
C++ (11)
C# (370)
D (25)
Java (8)
Perl (1)
Ruby (14)
PHP (2)
Boo (2)
Cobra (2)
LISP (6)
F# (33)
HTML (0)
XHTML (0)
CSS (0)
XML (0)
XSLT (0)
Scala (4)
WPF (0)
WF (2)
WCF (0)
LINQ (4)
MONO (5)
Linux (0)
MySQL (0)
ブログ内検索
リンク
最近のトラックバック
RSSフィード
ブロとも申請フォーム

この人とブロともになる

QRコード
FC2カウンター
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。