スポンサーサイト

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

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

 この記事は、「マルチパラダイム時代におけるデータ構造 第14回 ー 可変オブジェクトと命令型プログラミング」の続きです。前回は、 可変オブジェクトと命令型プログラミングについて解説しました。今回は引き続き、 可変オブジェクトと命令型プログラミングについて解説します。
 今度は更新と消滅を考えてみましょう。こんな具合に、イメージすると面白いですよ・・・

武田「食堂のおばん!準備が遅すぎるぞ!
 こっちは貴重な昼休みの時間を使っているんだ!」
?「うるさい!貴方は必要最低限度のマナーを守れないの?」
一同(よく言ってくれた!)
武田「誰に向かって口をきいている。こっちへ来い!
 俺が一言声を書ければ、何時でも業者を変えられるんだぞ。」
?「うるさいね・・・私が出て後悔するのはそっちだよ。」
武田「ふん。食堂のおばん風情が何を言っている。」
?「私の顔を忘れたの?」
武田「?...まさか!」
会長「久しぶりね。」
武田「か、会長...」
会長「誰が誰のクビを飛ばすって?」
武田「い、いや、その、なんでこんなところに・・・」
会長「わが社は大衆食堂から始まった事忘れたのかい?
 初心を忘れないために、そして何よりも、
 うちで頑張ってくれている社員をねぎらうためにいるのよ。」
武田「申し訳ございません。何卒、お赦し下さい。」
会長「そんなことより、順番がおかしいから並び替えなさい。」
武田「そ、その。いつから・・・」
会長「一部始終見ていたわ。これからいう順番通りに変更して。」
一同「はい」

ケース1:最初の位置のデータ更新
会長「始めは、山田さんだったわ。」
佐藤「はい。」
武田「あの、俺は・・・」
会長「一度、列の外に出て。」
行列:山田 前田 (山田) 田中 斎藤 佐藤
※()内は重複データ

ケース2:任意の位置のデータを更新
会長「次は田中さんね。」
田中「はい。」
行列:山田 田中 (山田) (田中) 斎藤 佐藤

会長「次は武田。3番目に並びなさい。」
武田「はい。」
行列:山田 田中 武田 (田中) 斎藤 佐藤

会長「4番目は...斎藤さん。」
斎藤「はい。」
行列:山田 田中 武田 斎藤 (斎藤) 佐藤

会長「5番目は前田さん。」
前田(甘え声)「そんなぁ。」
会長「甘えても駄目!」
行列:山田 田中 武田 斎藤 前田 佐藤

ケース3:任意のデータを消滅
会長「これでよし!次はマナーを守れない人に退場してもらうよ。」
武田「!!!」
会長「武田。マナーが悪すぎるからおひるごはん抜きよ。」
武田「そ、それは、あんまりです。」
会長「前から悪いうわさを聞いていたわ。
 次の人事楽しみにしていなさい。」
武田「........」
行列:山田 田中 斎藤 前田 佐藤

会長「これにて一件落着!」
斎藤「流石会長!名判事です。」
山田「いやぁ、それにしてもおなかすいたな。」
会長「はは。腕によりをかけて作るよ。」
田中「楽しみにしています。」
前田「ダイエットしているから、カロリー低いめでお願いします♪」
会長「あいよ。任しな。ダイエット用もあるよ。」
前田「わーい♪」
佐藤(あれ?みんな、俺の事を忘れているぞ。)


この例を見てわかるのは、一時的に重複データがあることです。データの更新は、書き換えるまで重複するデータが存在します。これを意識しておかないと、データの整合性に関するトラブルが発生します。また、更新と消滅はともにデータを検索していることに注目してください。carとcdrがある構造上、データ更新時はcarを持つインスタンスを、データの消滅時はcdrを持つインスタンスを検索しています。これらの事を把握すれば、容易に実装できます。
 命令型プログラミングで単刀直入に実装すると、こんな感じになります・・・


//指定位置の要素を検索する。
private ConsCell<T> Search( int index )
{
    var before = this.SearchBefore( index );
    return before.Cdr;
}

//指定位置のデータを更新する。
public void Update( T newValue, int index )
{
    var target = this.Search( index );
    target.Car = newValue;
}

//最後尾のデータを消滅する。
public void Delete( )
{
    this.Delete( this.Count - 1 );
}

//指定位置のデータを消滅する。
public void Delete( int index )
{
    if ( this.Count == 0 )
        throw new ArgumentException( 
            "データは1件も存在しません。" );
    var before = SearchBefore( index );
    if ( before.Cdr == null )
        throw new ArgumentException( 
            index + "にデータは存在しません。" );
    if ( before.Cdr.Cdr != null ) {
        before.Cdr = before.Cdr.Cdr;
    }
}

これでテストができるようになったので、テストにかけると・・・失敗します。何故ならば、nullに関する処理が甘いからです。命令型プログラミングでは、nullに対するチェックを厳重にしないとなりません。そこで、nullチェックを強化すると、次のようになります・・・

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

        //インスタンスの文字列表現を取得する。
        public override string ToString( )
        {
            System.Text.StringBuilder result = 
                new System.Text.StringBuilder();
            ConsCell<T> cons = this;
            result.Append( "{ " );
            do {
                result.Append( cons.Car + " " );
                cons = cons.Cdr;
            } while( cons != null );
            result.Append( "}" );
            return result.ToString();
        }

        //cdrの数を数える。
        private int GetCdrCount( ConsCell<T> 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 T Select( )
        {
            return this.Car;
        }

        //指定位置のデータを選択する。
        private ConsCell<T> Select( 
            ConsCell<T> target, int index, int count )
        {
            if ( index > this.Count )
                throw new IndexOutOfRangeException( 
                    "指定された位置" + index + 
                    "にデータは存在しません。" );
            return index == count
                ? target
                : this.Select(
                    target.Cdr, 
                    index, 
                    ++count );
        }

        //指定位置のデータを選択する。
        public T Select( int index )
        {
            return this.Select( this, index, 0 ).Car;
        }

        //指定した位置の前の要素を返す。
        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 ConsCell<T> Search( int index )
        {
            var before = this.SearchBefore( index );
            var result = before != null ? before.Cdr : null;
            return result;
        }

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

        //指定位置へデータを発生させる。
        public void Insert( T value, int index )
        {
            if ( !this._hasElement || 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 void InsertMiddle( int index, T value )
        {
            ConsCell<T> before = this.SearchBefore( index );
            if ( before == null ) {
                ConsCell<T> newValue =
                new ConsCell<T> {
                    Car = value,
                    Cdr = null
                };
                this.Cdr = newValue;
            } else {
                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;
        }

        //指定位置のデータを更新する。
        public void Update( T newValue, int index )
        {
            var target = this.Search( index );
            if ( target == null ) {
                this.Car = newValue;
            } else {
                target.Car = newValue;
            }
        }

        //最後尾のデータを消滅する。
        public void Delete( )
        {
            this.Delete( this.Count - 1 );
        }

        //指定位置のデータを消滅する。
        public void Delete( int index )
        {
            if ( this.Count == 0 )
                throw new ArgumentException( 
                    "データは1件も存在しません。" );
            if ( index == 0 ) {
                DeleteFirst();
                return;
            }
            var before = SearchBefore( index );
            if ( before.Cdr == null )
                throw new ArgumentException( 
                    index + "にデータは存在しません。" );
            if ( before.Cdr.Cdr != null ) {
                before.Cdr = before.Cdr.Cdr;
            } else {
                before.Cdr = null;
            }
        }

        //最初のデータを消滅する。
        private void DeleteFirst( )
        {
            if ( this.Cdr != null ) {
                this.Car = this.Cdr.Car;
                this.Cdr = this.Cdr.Cdr;
            } else {
                this.Car = default(T);
                this._hasElement = false;
            }
            return;
        }

        //暗黙的にコンスセルをタプルに変換する。
        public static implicit operator Tuple<T, ConsCell<T>>( ConsCell<T> obj )
        {
            if ( obj == null ) return null;
            return new Tuple<T, ConsCell<T>> { 
                First = obj.Car, 
                Second = obj.Cdr };
        }
    }
}

このように、命令型プログラミングは、nullチェック関連のコードにより、余計な処理が増える傾向があります。リファクタリングをすれば、もっと簡潔になります。ですが、命令型プログラミングの性質上、宣言型プログラミングと比べると、どうしても長くなりがちです。コードを磨くことを忘れないようにしましょう。
 前回と併せて読むと、可変オブジェクトと命令型プログラミングの特徴がよくわかると思います。オブジェクトの性質と、選択したプログラミングパラダイムの性質をよく考えプログラミングしましょう。続く...
スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

インドリ

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