データ構造とは?

Weblio 辞書 > 固有名詞の種類 > 方式・規則 > 主義・方式 > 学問 > 学問 > データ構造の意味・解説 

データ構造

読み方でーたこうぞう
【英】:data structure

概要

与えられたデータを, 計算高速化のために構造をもたせて記憶する手法総称. 目的合わせ, あるいくつかの機能を, 高速, あるいは省メモリで行えるよう設計される. 例えば, ある言葉n \, 個の言葉辞書データから検索するとき, 通常の配列では, 最悪挿入削除O(n) \,, 検索O(\log n) \, か, 挿入削除O(1) \,, 検索O(n) \,時間要する. 二分探索木というデータ構造は, これらの機能O(\log n) \, 時間行い, 使用メモリO(n) \, である.

詳説

 データ構造とは, 与えられたデータに対して, そのデータを使った計算高速化, そのデータ記憶するために必要な領域減少等の目的で, データ構造持たせ, データ対す操作効率化を行う手法総称である. あるいくつかの機能を, データ記憶形式と, その形式データ操作するアルゴリズムにより実現する.

 通常のコンピューター言語では, データ蓄え手法として配列リスト, またはその両方用意されている. 配列指定した位置にあるデータ\mbox{O}(1)\, 時間アクセスでき, リスト与えられたデータ並べて記憶し, 隣のデータ\mbox{O}(1)\, 時間アクセスできる. リスト配列により実現可能だが, リスト配列実現できない.

 配列リストは最も単純なデータ構造である. ここで両者を使ったデータ構造の性能違い見てみよう. 例として n\, n\, 列の行列 M\, 保持し, 他の行列との掛け算を行うためのデータ構造を考える. 通常の配列使用して行列記憶する場合 \mbox{O}(n^2)\, メモリが必要であるが, もし M\, の非要素の数 H\, 小さ場合, 非要素連結してリストで持つことにより, 記憶容量\mbox{O}(H)\, まで減少させることができる. 行列掛け算は非要素に関する部分だけ計算を行えばよいので, 計算時間2つ行列の非要素の数の積に比例する. しかし, リストは一要素記憶するのに必要なメモリ配列比べ大きいので, 非要素が多い場合リストのほうが遅く, メモリ多くなる.

 次に, n\, 個の用語の辞書データ保持し, その中から与えられた用語を検索するためのデータ構造を考える. データ変更がないときは, 用語を辞書順並べて記憶すれば, 二分探索により\mbox{O}(\log n)\, 時間1つの用語が検索できる. しかし, 辞書データの中の用語を削除する・新しい用語を追加する, という操作が必要な場合には, 通常平均的\mbox{O}(n)\, 時間要する. 辞書順並べかわりに, 二分探索木 (AVL木, 2-3木など) というデータ構造を用いれば, 使用メモリ\mbox{O}(n)\, のままで, これらの操作実行時間を\mbox{O}(\log n)\, まで減らすことができる. このようにデータ動的な変に対して効率良く操作が行えるよう設計されたデータ構造を動的データ構造という. 辞書データを扱う他の効率良いデータ構造としてはハッシュ表が知られている.

 動的データ構造の中で最も基礎的なものとしてはヒープが挙げられる. 基本的ヒープは, n\, 個の要素の中の最小値を得る・要素追加削除するという操作を, 1回あたり\mbox{O}(\log n)\, 時間実行し, またメモリ使用量も\mbox{O}(n)\, である. 応用広く, プリム法 (最小木問題アルゴリズム), 最少費用フロー問題 (最小費用問題) のアルゴリズムなどで使用される. また, 改良版の Fヒープ (フィボナッチヒープ) は, 最短路問題を解くアルゴリズムで使われている. その他, n\, 個の区間集合保持し, 質問点を含む区間列挙する, 区間挿入削除を行う, などの操作を1回あたり \mbox{O}(\log n)\, 時間で行う区分木, 大きさ n\, 木構造グラフに対し, 合併分割変形・ある頂点の子孫数を求める, など多く操作\mbox{O}(\log n)\, 時間で行う動的木, 集合合併要素探索高速化し, n\, 回の合併m\, 回の探索合計時間がほぼ \mbox{O}(m+n)\, となる集合ユニオン・ファインド木, 動的変化する有向グラフの強連結性保持し, k\, 回の挿入削除\mbox{O}(kn^{1.3})\, で行うデータ構造[7], など数多くのものが考案されている. 文字列グラフを扱う離散アルゴリズム多くは, これらの基礎的なデータ構造に手を加えたものを使用することにより高速化されている. また, アルゴリズム動作記録変換して保持し, パラメーター変更による計算結果変化出力するデータ構造は動的計画, 組み合わせ最適化問題感度分析などに応用が広い.

 データ構造, 特に動的データ構造は, 計算幾何学における発展著しい. 幾何的データデータの量に対して構造が複雑なものが多い. 例えば, 平面上の n\, 点の集合に対し, 距離が d\, 以下の2点つないだグラフ(幾何グラフ)を考える. このグラフO(n^2)\, 本のを含む可能性があるが, このグラフ記憶するには点集合だけ記憶すれば十分である. つまり, メモリ計算時間省略するためには, 点集合データから必要な情報を得るための構造が必要となる. また, 交差など, グラフ的な情報からは導けないものもあり, それらの情報効率的に得るためにもデータ構造はかかせない. 幾何的なデータ構造としては, 平面上のn\, 点集合凸包保持し, 点の追加消去に対し新し凸包\mbox{O}(\log n)\, 時間求めるもの, k\, 次元n\, 点集合に対し, 質問点から近い順に点を1個あたり平均 \mbox{O}(1)\, 時間出力する k-d\, 木, 質問領域中に含まれる点を1個あたり \mbox{O}(\log^{k-1} n)\, 出力するレンジサーチ木 [8], 平面いくつかの領域分割する n\, 本の線分集合与えられたとき, 質問点がどの領域含まれるかを \mbox{O}(\log n)\, 時間答え領域探索などが挙げられる. その他に, 線分集合に対し, ある点から見える点, すなわち2点をつなぐ線分が他の線分交差ないよう点集合保持するデータ構造など, 交差, 領域に関してさまざまなデータ構造が考案されている.

 前述幾何的なデータ構造は, 幾何的対象を扱う計算幾何学アルゴリズム多く使われている. 多角形の三角形分割線形時間アルゴリズムなども高度な技術用いてデータ構造を活用しているが, しかしその反面複雑になりすぎ, 現実的ではないという欠点がある. また, 個々アルゴリズム使用するデータ構造がそのアルゴリズム特化した, 一般性のないアルゴリズムとデータ構造も少なくない. それゆえ, 最近では簡素化視野に入れた研究進んでいる. スパーシフィケイション [6] もその一つであり, 動的データ構造高速化の一般化した技術を提供している. スパーシフィケーションにより, n\, 頂点 m\, を持つ無向グラフ最小張木保持するデータ構造は, 1回の追加削除重み変化対す計算時間が, \mbox{O}(m^{1/2})\, から\mbox{O}(n^{1/2})\, 高速化される. また同様にグラフ二部グラフ性の判定, 二連結性の判定, 頂点連結性判定なども, 一回操作計算時間\mbox{O}(m)\, から \mbox{O}(n)\, 高速化される.

 最後に参考文献挙げる. 動的木などグラフ的なデータ構造は [3], [4], [5] 等に詳しい. また, 幾何的データ構造については [1], [2] 等が詳しい.



参考文献

[1] F. P. Preparata and M. L. Shamos, "Computational Geometry - An Introduction," Springer-Verlag, 1985. 浅野孝夫, 浅野哲夫 訳,『計算幾何学入門』, 総研出版, 1992.

[2] 今井浩, 今井圭子,『計算幾何学』, 共立出版, 1994.

[3] T. H. Cormen, C. E. Leiserson and R. L. Rivest, "Introduction To Algorithms," The MIT Press, 1990. 浅野哲夫, 岩間和生, 尾博司, 山下雅史, 和田幸一 訳,『アルゴリズムイントロダクション 1,2,3巻』, 近代科学, 1995.

[4] 浅野孝夫,『情報構造 上, 下』, 日本評論社, 1994.

[5] 茨木俊秀,『アルゴリズムとデータ構造』, 昭晃堂, 1989.

[6] D. Eppstein, Z. Galil, G. F. Italiano, A. Nissenzweig "Sparsification - A Technique for Speeding up Dynamic Graph Algorithms," FOCS, 33, 1992

[7] S. Khanna, R. Motwani and R. H. Wilson, "On Certificates and Lookahead in Dynamic Graph Problems," SODA, 1995

[8] D. E. Willard "New Data Structures for Orthogonal Range Queries," SIAM Journal on Computing, 14 (1985), 232-253.


データ構造

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/08/06 09:45 UTC 版)

データ構造(データこうぞう、: data structure)は、計算機科学において、データの集まりをコンピュータの中で効果的に扱うため、一定の形式に系統立てて格納するときの形式のことである。




「データ構造」の続きの解説一覧



データ構造と同じ種類の言葉


固有名詞の分類


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「データ構造」の関連用語

データ構造のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



データ構造のページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2021 (社)日本オペレーションズ・リサーチ学会 All rights reserved.
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのデータ構造 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2021 GRAS Group, Inc.RSS