スポンサーサイト

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

マルチパラダイム時代におけるデータ構造 第3回 ー 不変で自己記述的なデータ構造が原点

 この記事は、「マルチパラダイム時代におけるデータ構造 第2回 ー 最も基本的なデータ構造は・・・」の続きです。前回は、最も基本的なデータ構造「タプル」について解説しました。今回は、タプルを活用した、配列の元となるデータ構造について解説します。
 タプルは非常に簡単ですが、簡単ゆえにどうやって配列などのデータ構造を構成するのか、すぐにはわからないと思います。その鍵は再帰構造にあります。データ構造というオブジェクトは、再帰構造が基本であり、再帰構造がわかるか否かが明暗を分けています。しかしながら、再帰構造がわかりにくいという人が多いも確かです。それで、タプルを使って、いきなり配列を実装できますが、それだと分かりにくいので、段階的に解説していきます。
 いくつものデータが並んでいる様子を思い浮かべてください。数値で例えると、こんな具合になっています。

1 2 3 4 5 ...

これを、タプルを使って表現すればどうなるでしょうか?ちょっと発想し難いと思いますが、「1とその他の数値」と考えればタプルで表現できます。この発想はLISP言語にもあります。そこで今回は、LISP言語から借りてきたものを実装します。

namespace DataStructure
{
    //2つの要素を管理するデータ構造。
    public class Tuple<T1, T2>
    {
        //最初の要素。
        private T1 _first;
        public T1 First
        {
            get { return this._first; }
        }

        //2番目の要素。
        private T2 _second;
        public T2 Second
        {
            get { return this._second; }
        }

        //2つの要素を指定し、インスタンスを生成する。
        public Tuple( T1 first, T2 second )
        {
            this._first = first;
            this._second = second;
        }
    }
}

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

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

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

        //格納する要素と次のセルを指定し、インスタンスを生成する。
        public ConsCell( T element, ConsCell<T> next )
        {
            this._cons = new Tuple<T, ConsCell<T>>( element, next );
        }

        //インスタンスの文字列表現を取得する。
        //※デバッグ時に役立つので実装しました。
        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();
        }
    }
}

タプルは前回実装しましたが、深い学習を行うために、いったん不変オブジェクトにします。ちなみに、carとcdrは古い計算機のレジスタの名前が由来だそうです。面白い省略名ですね。
 もしかしたら、再帰構造は邪道な印象を与えるかもしれませんが、データ構造とアルゴリズムの学習には、再帰は欠かせないのでこれを機会に習得しましょう。そうすれば、貴方のプログラミング力は飛躍的にアップすると思います。続く...
スポンサーサイト

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

コメントの投稿

非公開コメント

プロフィール

インドリ

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