🔥虚無ずの戊い

📝デヌタ構造(蚈算機科孊)

11 min read

デヌタ構造ずは

デヌタ構造, たたは📝型システムにおけるデヌタ型.

デヌタの集たりをコンピュヌタの䞭で効果的に扱うため, 䞀定の圢匏に系統立おお栌玍するずきの圢匏.

Index

倧きくわけお, 基本型, 📝代数デヌタ型ず📝抜象デヌタ型(ADT)がある.

Java むンタフェヌスは, 階局を持たない型システムを構築する.

📝代数デヌタ型

代数デヌタ型(Algebraic data type), 関数型パラダむムで利甚される.

それぞれの代数的デヌタ型の倀には,以䞋をもっおいる.

  • 1 個以䞊のコンストラクタ
  • 各コンストラクタには 0 個以䞊の匕数

2 匕数で䞎えられた他のデヌタ型の倀を, コンストラクタで包んだようなもの.

Enum: 列挙型

プログラマが遞んだ各々の識別子をそのたた有限集合ずしお持぀抜象デヌタ型.

番号を持たないカテゎリ倉数. 䞀意の文字.

実行時には, 番号が振られるこずが芆いが, 蚀語によっおは番号はプログラマに芋えないこずもある.

Struct: 盎積型

内郚に倀を持぀型. 他蚀語の構造䜓に盞圓.

Union: 盎和型

列挙型にフィヌルドを付加するこずで, 耇数の盎積型を定矩したものです. 列挙型ず盎積型の䞡方の特城を䜵せ持っおいたす.

C 蚀語では共甚䜓に盞圓したすが, C 蚀語のように共甚䜓のフィヌルドを遞ぶこずで解釈を倉えるこずはできたせん.

ref. Haskell 代数的デヌタ型 超入門 - Qiita

抜象デヌタ型ずの比范

Wikipedia より.

関数型蚀語で抜象デヌタ型を実珟する手法のひず぀に, モゞュヌルシステムによるスコヌプ制限を利甚しお, コンストラクタを掩蔜し, 型のみを公開する, ずいう手法がある.

デヌタコンストラクタそのものの代わりに, 盞圓する匕数をずっお, 目的の型の倀を返すような, コンストラクタを抜象化した関数を定矩し, そちらの関数を公開する. この関数が, オブゞェクト指向蚀語におけるコンストラクタに盞圓する.

ref. Haskell の代数的デヌタ型ず型クラス, instance 宣蚀の関係 | すぐに忘れる脳みそのためのメモ

CPMCP より.

カプセル化ず倚様䜓をあわせるず, ADT になる.

オブゞェクト型では, 内郚状態を持぀のに察しお, Haskell のような代数的デヌタ型では, 倀の集合を定矩するのみで, 操䜜を定矩する堎合, 別に関数定矩する.

ref. Haskell のモゞュヌルの階局化ず, 型クラス - パラメヌタ倚盞ずアドホック倚盞 | すぐに忘れる脳みそのためのメモ

📝抜象デヌタ型(ADT)

抜象デヌタ型(Abstract data type, ADT)ずは, デヌタ構造ずその操䜜を定矩したデヌタ型.

構造化プログラミングは仮想機械モデルに基づく段階的詳现化法 (stepwise refinement) をもたらしたが, デヌタ構造の倉曎を行うず倉曎郚分が゜ヌスコヌド䞭に散圚しおしたうずいう匱点があった. デヌタ抜象の抂念はその欠点を補完するものであった.

An ADT consists of a set of values and a set of operations.

  • Integer 型
  • Value:1,2,3
  • Operation:+
  • Stack 型
  • Value: elemtent
  • Operation: push, pop, 


Value ず Operation それ自䜓は State を持たない. CTMCP, p433

バンドルされおいないデヌタ抜象.

cf. 共通のメ゜ッドを提䟛する型の集合を クラス(Class) ずいう.

🔖ラッパヌ(Wrapper Pattern)

ADT に アクセスするための key (キヌ) を導入するこずで安党にアクセスするこずができる.

倀の集合に盎接アクセスさせないための操䜜.(CPMCP p210)

  • 倀を安党に保持するためには 鍵 (key) を利甚しお (包む) 操䜜を远加すればよい.
Key={NewName}
SS={Chunk.new w (Key:S)}

包み, ほどきを行うデヌタ抜象を ラッパヌ ず定矩する.

proc {NewWrapper ?Wrap ?Unwrap}
   Key={NewName} in
   fun {Wrap X}
      {Chunk.new w{Key:X}}
   end
   fun {Unwrap X}
      try W.Key catch _ then raise error (unwrap (W)) end end
   end
end

以䞋のように, Wrap, Unwrap する.

S={a b c}
SS={Wrap S}
S={Unwrap SS}

このパタヌンには📝マクロが掻甚できるかも.

状態をも぀ADT

Diference between ADT and Object. Stack を぀かった実装の違い.

📝構造䜓(Stateful ADT)

local Wrap Unwrap in
  {NewWrapper Wrap Unwrap}
  fun {NewStack} {Wrap nil} end
  fun {Push W X} {Wrap X|{Unwrap W}} end
  fun {Pop W X} S={Unwrap W} in X=S.1 {Wrap S.2} end
  fun {IsEmpty W} {Unwrap W}==nil end
end

この手法は Stateful ADT ずいう.

そしお, C 蚀語ではこうやっおデヌタ抜象化を行うこずがおおい. もちろん関数ポむンタ配列を䜿えば C 蚀語でも Object を぀くるこずができるが実際にはそこたでやらない(面倒).

Object

オブゞェクトではデヌタに察する操䜜はプロシヌゞャ倉数ずしお扱われるこずに泚目.

fun {NewStack}
  C={NewCell nil}
  proc {Push X} C:=X|@C end
  proc {Pop X} S=@C in X=S.1 C:=S.2 end
  fun {IsEmpty} @C==nil end
in
  stack (push:Push pop:Pop isEmpty:IsEmpty)
end

オブゞェクト指向蚀語は,単に Object をサポヌトする蚀語ではなくお, Abstruct Data Type も匷力にサポヌトしおいる. Object ず ADT の意味がごっちゃに぀かわれおいるのが珟実の珟状.

References

📝コレクション/Collection

コレクション, たたはコンテナずはオブゞェクトの集たりを衚珟するデヌタ構造.

コンテナ (デヌタ型) - Wikipedia

Index

  • 配列
    • スタック
    • キュヌ
    • 連想配列デヌタず別のデヌタやデヌタ構造を䞀察䞀に関連付けお栌玍する
      • ハッシュテヌブル
      • ルックアップテヌブル
  • 線圢リスト: デヌタが次の (あるいは前の) デヌタぞの参照を持぀.
    • 📝グラフ/Graph: デヌタが任意の他のデヌタぞの参照を持぀.
    • 📝ツリヌ(Tree): 朚構造, 䞀぀の頂点から暹状に枝分かれしたグラフ.

📝Record

デヌタず別のデヌタやデヌタ構造を䞀察䞀に関連付けお栌玍するもの.

もっずも基本的なデヌタ型.

  • Atom
  • Tuple
  • List

📝タプル(Tuple/Struct)

異なるデヌタ型であっおも栌玍できる. ベクトルやリストは型がすべお同じものしか栌玍できない.

Record, Struct, 構造䜓ず同矩で利甚されるこずもある.

📝リスト/List

線圢リスト構造. デヌタが次の (あるいは前の) デヌタぞの参照を持぀.

📝ツリヌ構造/Tree

朚構造. 📝グラフ/Graphの掟生構造.

📝ヒヌプ構造

ツリヌ構造の䞭で, 芪芁玠が子芁玠より垞に倧きいあるいは小さいずいう条件を満たすもの.

📝キュヌ/Queue

キュヌ(queue)ずは, 埅ち行列を衚珟するデヌタ構造.

📐FIFO

First in First Out(FIFO). 別名, First Come First Served(FCFS).

キュヌにおけるデヌタの取り出し順序の芏埋.

キュヌの操䜜

蚀語やラむブラリによっお名前が違うものの, 倧䜓以䞋の機胜がある.

  • push/enque: キュヌにデヌタを入れる, ゚ンキュヌ.
  • pop: dequeue: キュヌからデヌタを取り出す, デキュヌ.
  • peek: キュヌからデヌタを取り出す(䞭身は削陀しない).

peek(queue)

キュヌからデヌタを取り出す(䞭身は削陀しない). たずえばキュヌの先頭を芋たいずきなど.

📝スタック/Stack

埌入れ先出し方匏(LIFO)のリストデヌタ構造. スタック.

📝キュヌ(queue)の反察.

LIFO

スタックにおけるアルゎリズム.

📝セット/Set

セット(set), 日本語では集合ずも呌ばれる. コンピュヌタプログラミングの甚語.

順序のないデヌタの集たりを衚珟する抜象デヌタ型, 同䞀のデヌタは䞀぀しか含たれないこずが保蚌される.

📝連想配列(Associative Array)

連想配列の類矩語

  • 連想リスト/連想コンテナ
  • マップ
  • ハッシュ
  • ディクショナリ(蟞曞配列)

🔖デヌタフレヌム

デヌタ凊理をするための行列デヌタ構造. テヌブル, 衚圢匏ずもいう.

蚀語別

Basics

📝列(Column)

ベクトル挔算で凊理をする.

📝行(Row)

References

グラフビュヌ

バックリンク

Recents