スポンサーサイト

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

マルチパラダイム時代におけるデータ構造 第14回 ー 可変オブジェクトと命令型プログラミング

 この記事は、「マルチパラダイム時代におけるデータ構造 第13回 ー 不変なコンセンスセルを考えよう」の続きです。前回は、不変オブジェクトについて解説しました。今回は、可変オブジェクトと命令型プログラミングについて解説します。
 不変コンセンスセルを実装したので、今度は可変コンセンスセルを実装しましょう。可変オブジェクトを実装する場合は、基本的に命令型プログラミングを使用します。何故ならば、可変オブジェクトは状態が変化するからです。状態を変化させて望む結果を得るという考え方は、命令型プログラミングの考え方と同一です。もちろん、絶対に命令型プログラミングしか使用してはならないという事ではなく、どちらかというと向いているという事です。実際は可読性や保守性などを考慮して混合します。
 可変オブジェクトを実装する際には、オブジェクトの状態に気を付けます。不変オブジェクトとは違って、内部の状態が変化するので、どの状態に何をするのかはっきりとせねばなりません。その為には、イメージをしっかりと持ちましょう。
 具体的に可変オブジェクトと命令型プログラミングを理解するために、可変コンセンスセルのデータ発生処理について考えてみましょう。データを発生させるという事は、次のようになります・・・

「社員食堂にて」
ケース1:始めてデータを発生させたとき
山田「やったぁ!一番乗りだ!」
行列の状態 ー 山田 

ケース2:2回目にデータを発生させたとき
田中「くそっ!山田に負けた。」
行列の状態 ー 山田 田中

ケース3:最初の位置でデータを発生させたとき
武田「俺はお前らの上司だから先頭でいいよな!」
山田&田中「・・・ど、どうぞ。」
行列の状態 - 武田 山田 田中

ケース4:最後の位置でデータを発生させたとき
佐藤「俺はトイレに行っていただけで、最初に並んで居たんだ。」
武田「そんなこと知るか!順番を守れ!」
山田&田中( お前が言うな! )
※心の声、口に出す勇気はない。100倍返しなんてとんでもない。
行列の状態 - 武田 山田 田中 佐藤

ケース5:最初と最後以外の場所へデータを発生させたとき
前田(甘え声で)「わぁ、もうこんなに並んでいる。おなかすいたな...」
武田「俺の後ろに来なよ。」
前田「ありがとうございます♪」
山田&田中&斎藤( 可愛い女には甘いな。それでも後ろか・・・ )
武田「同じぐらいに料理が来るだろうから一緒に食べよう。」
山田&田中&斎藤( それが狙いか! )
佐藤(?!いつの間にか斎藤が俺の前にいるぞ)
行列の状態 - 武田 前田 山田 田中 斎藤 佐藤

武田「準備はまだか!」
データの更新&消滅編へ続く...

こんな具合にイメージを持てなければ、命令型プログラミングはやりにくいです。イメージを持ったら、プログラミングを始めましょう♪
 先ず考えられるのは、プロパティ&フィールド&コンストラクタです。さくっとやりましょう。

using System;

namespace DataStructure
{
    //1つの要素とそれ以外の要素への参照を持つデータ構造。
    public class ConsCell<T> : IDataFreeManager<T>
    {
        //要素
        private Tuple<T, ConsCell<T>> _cons;

        //要素を持っているか否か
        private bool _hasElement;

        // 最初の要素。
        //※プロパティ名はカーと読む。
        public T Car
        {
            get { return this._cons.First; }
            private set
            {
                this._cons.First = value;
                this._hasElement = true;
            }

        }

        //他の要素。
        //※プロパティ名はクダーと読む。
        public ConsCell<T> Cdr
        {
            get
            {
                return this._cons.Second;
            }
            private set
            {
                this._cons.Second = value;
                this._hasElement = true;
            }
        }

        //cdrの数を数える。
        private int GetCdrCount( ConsCell target, int index )
        {
            if ( !this._hasElement ) return 0;
            if ( target.Cdr == null ) return index;
            else return GetCdrCount( target.Cdr, ++index );
        }

        //要素の数を返す。
        public int Count
        {
            get 
            {
                return this.GetCdrCount( this, 1 );
            }
        }

        //インスタンスを生成する。
        public ConsCell( )
        {
            //始めはデータを持っていない
            this._cons = new Tuple<T, ConsCell<T>>();
            this._hasElement = false;
        }
    }
}

 次に実装するのはInsertメソッドです。先ほどのイメージでいうと、先頭・中間・最後の3つのパターンがあります。そのパターンに従って、実装してみましょう。

//最後尾へデータを追加する。
public void Insert( T value )
{
    this.Insert( value, this.Count );
}

//指定位置へデータを発生させる。
public void Insert( T value, int index )
{
    if ( index == 0 ) {
        InsertFirst( value );
    } else if ( index == this.Count ) {
        InsertLast( value ); 
    } else {
        if ( index > this.Count )
            throw new ArgumentOutOfRangeException(
                "範囲外の値が指定されています。" );
        InsertMiddle( index, value );
    }
}

//最初の位置でデータを発生させる。
private void InsertFirst( T value )
{
    if ( !this._hasElement ) {
        //始めての要素
        this.Car = value;
    } else {
        var next = 
            new ConsCell<T> { 
                Car = this._cons.First,
                Cdr = this._cons.Second
        };
        this.Car = value;
        this.Cdr = next;
    }
    return;
}

//指定した位置の前の要素を返す。
private ConsCell<T> SearchBefore( int index )
{
    ConsCell<T> before = null;
    ConsCell<T> current = this;
    int count = 0;
    while( current.Cdr != null && index != count) {
        before = current;
        current = current.Cdr;
        ++count;
    }
    if ( index != count ){
        new ArgumentOutOfRangeException(
            "指定された位置にデータは存在しません。" );
    }
    return before;
}

//中間位置でデータを発生させる。
private void InsertMiddle( int index, T value )
{
    ConsCell<T> before = this.SearchBefore( index );
    ConsCell<T> newValue =
        new ConsCell<T> { 
            Car = value, 
            Cdr = before.Cdr
        };
    before.Cdr = newValue;
}

//最後の要素を取得する。
private ConsCell<T> GetLast( )
{
    ConsCell<T> result = this;
    while ( result.Cdr != null )
        result = result.Cdr;
    return result;
}

//最後の位置でデータを発生させる。
private void InsertLast( T value )
{
    ConsCell<T> last = this.GetLast();
    ConsCell<T> newValue = new ConsCell<T> {
        Car = value 
    };
    last.Cdr = newValue;
}

このように、状態を個別に考えてプログラミングすると行い易いです。これが命令型プログラミングの特徴です。
 察しがいい人は、この時点で不変オブジェクトとの違いが分かったと思います。それは、一々インスタンスを生成していない事です。不変オブジェクトの場合、プロパティの値を更新できないので、一々インスタンスを生成し直ししていました。これが不変オブジェクトの弱点であり、命令型プログラミングの長所でもあります。
 命令型プログラミングは必要とするメモリ量を削減する効果があります。どちらかというと、本質とは関係がないループや状態分けがないため、宣言型プログラミングの方がプログラミングしやすいのですが、逆に状態を細かく特定したほうが実装しやすい場合もあります。求められる処理の内容を考慮して決定するとよいでしょう。続く...
スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

インドリ

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ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。