抽象データ型

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

抽象データ型(ちゅうしょうデータがた、abstract data type、ADT)とは、データ構造とそれを直接操作する手続きをまとめてデータ型の定義とすることでデータ抽象[1]を実現する手法またはそのひとまとまりとして定義されたデータ型を言う。通常のデータ型であれば変数宣言で変数に束縛されるものは値であるが、抽象データ型の世界において値に相当するものはデータ構造とその操作[2]のまとまり[3]である。

抽象データ型を用いない場合、データ構造またはデータの操作手続きのアルゴリズムの変更を行うとソースコード中にその変更部分が散在してしまい規模によっては修正困難となるが、データとその操作がひとまとめに記載されることになる抽象データ型においては、型の定義における実装部分を変更するだけで修正が完了する。

概要[編集]

エドガー・ダイクストラらの構造化プログラミングは仮想機械モデルに基づく段階的詳細化法(stepwise refinement)をもたらしたが、データ構造の変更を行うと変更部分がソースコード中に散在してしまうという弱点があった。データ抽象の概念はその欠点を補完するものであった。抽象データ型はデータ抽象の具体的手法として1974年にB.H.Liskovの提案した言語CLUにおいて提案された[4]

インタフェースと実装の分離[編集]

プログラムが実装されたとき、抽象データ型は実装を隠蔽するインタフェースを表す。実装は将来において変更されうるので、抽象データ型のユーザーは実装ではなくインタフェースに関心がある。

抽象データ型の強みはユーザーから実装が隠蔽されていることである。インタフェースのみが公開されるのである。このことは、抽象データ型がいろいろな方法で実装されうることを意味するが、インタフェースに忠実な限りユーザープログラムは影響を受けないのである。

例えば、二分探索木抽象データ型はいくつかの方法で実装できる。例えば、二分木(en:binary tree),AVL木(en:AVL tree),赤黒木(en:red black tree),配列である。しかし実装に関わらず二分探索木はinsert, remove, findといった同じ操作が可能である。

抽象データ構造[編集]

抽象データ構造とは、実際のデータ構造による実装に関わらず、操作の集合とその計算量により定義されるデータのための抽象的な領域のことである。

具体的なデータ構造の選択がアルゴリズムの効率的な実装にとって重要である一方、抽象データ構造の選択は効率的なアルゴリズムの設計とその計算量の推定にとって極めて重要である。

この概念はプログラミング言語の理論で用いられる抽象データ型の概念に非常に近い。多くの抽象データ構造や抽象データ型の名前は具体的なデータ構造の名前と一致する。

具体例[編集]

抽象データ型としての有理数[編集]

有理数は計算機においてはそのまま扱うことはできない。有理数の抽象データ型は以下のように定義できる。

コンストラクタ: 2つの整数a, bを用いて有理数の抽象データ型のインスタンスを作成する。ここでaは分子でbが分母である。

関数: 加算,減算,乗算,除算,指数計算,比較,約分,実数への変換

完全な記述にするためには、それぞれの関数はデータに言及して記述されるべきである。例えば、有理数a/bc/dを乗算するときには結果はac/bdと定義される。通常、入力,出力,実行前条件,実行後条件,抽象データ型に対する仮定も記述される。

脚注[編集]

  1. ^ データ抽象(data abstraction)とは、データ型の詳細定義とその操作に関する手続きを情報の局所性が高まるようにソースコード中の一カ所にまとめて記述するための記法のことを言う。情報が一カ所に局所的にまとめて記載されているため、非公開(private)部分の変更であればその定義部分の詳細を変更するだけでソースコード全体の修正が完了する。 データ型の詳細定義とその操作手続きの局所的記述を実現する方法は複数あり、抽象データ型はその一例である。
  2. ^ 言語に応じて名称が異なり、C++であればメンバ関数(member function)、JAVAであればメソッド(method)と呼ばれる
  3. ^ データ型の値に相当するこのまとまりのことを抽象データ型の実体(インスタンス , instance)と呼ぶ。
  4. ^ 参考文献5

参考文献[編集]

関連項目[編集]