A data structure known as a hash table.

In computer science, a data structure is a data organization and storage format that is usually chosen for efficient access to data.[1][2][3] More precisely, a data structure is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data,[4] i.e., it is an algebraic structure about data.

Usage

Data structures serve as the basis for abstract data types (ADT). The ADT defines the logical form of the data type. The data structure implements the physical form of the data type.[5]

Various types of data structures are suited to different kinds of applications, and some are highly defined to specific tasks. For example, relational databases commonly use B-tree indice for data retrieval,[6] while compiler implementations usually use hash tables to look up identifiers.[7]

Data structures provide a means to manage large amounts of data efficiently for uses such as large databases and internet indexing services. Usually, efficient data structures are key to designing efficient algorithms. Some formal design methods and programming languages emphasize data structures, rather than algorithms, as the key organizing factor in software design. Data structures can be used to organize the storage and retrieval of data stored in both main memory and secondary memory.[8]

Implementation

データ構造は、さまざまなプログラミング言語や手法を用いて実装できますが、それらすべてに共通する目標は、データを効率的に整理して格納することです。[9]データ構造は一般的に、ポインタ（メモリアドレスを表すビット列）によって指定されるメモリ内の任意の場所からデータを取得して格納できるコンピュータの能力に基づいています。ポインタ自体もメモリに格納され、プログラムによって操作されます。したがって、配列とレコードのデータ構造は、算術演算によってデータ項目のアドレスを計算することに基づいていますが、リンクされたデータ構造は、データ項目のアドレスを構造自体に格納することに基づいています。このデータ構造化のアプローチは、アルゴリズムの効率とスケーラビリティに大きな影響を与えます。たとえば、配列内の連続したメモリ割り当ては、迅速なアクセスと変更操作を容易にし、順次データ処理シナリオにおけるパフォーマンスの最適化につながります。[10]

データ構造の実装には通常、その構造のインスタンスを作成および操作する一連の手順を記述する必要があります。データ構造の効率は、これらの操作とは切り離して分析することはできません。この観察から、抽象データ型という理論的概念が生まれました。抽象データ型とは、実行可能な操作と、それらの操作の数学的特性（空間コストと時間コストを含む）によって間接的に定義されるデータ構造です。[ 11]

例

プログラミング言語Python 3の標準的な型階層

データ構造には多くの種類があり、一般的にはより単純なプリミティブデータ型に基づいて構築されています。よく知られている例は次のとおりです。[12]

  • 配列とは、特定の順序で並んだ要素の数で、通常はすべて同じ型です（言語によっては、個々の要素がすべて同じ型に強制される場合もあれば、ほぼ任意の型になる場合もあります）。要素へのアクセスは、必要な要素を指定する整数インデックスを使用して行われます。一般的な実装では、配列の要素に連続したメモリワードを割り当てます（ただし、これは必ずしも必要ではありません）。配列は固定長またはサイズ変更可能な場合があります。
  • 連結リスト（単にリストとも呼ばれます）は、ノードと呼ばれる任意の型のデータ要素の線形集合です。各ノードは値を持ち、連結リスト内の次のノードを指します。配列に対する連結リストの主な利点は、リストの残りの部分を再配置することなく、常に効率的に値を挿入および削除できることです。ただし、特定の要素へのランダムアクセスなど、他の特定の操作は、配列よりもリストの方が遅くなります
  • レコード（タプルまたは構造体とも呼ばれる）は、集約データ構造です。レコードは、通常は固定数と固定順序で他の値を含み、通常は名前でインデックス付けされた値です。レコードの要素は通常、フィールドまたはメンバーと呼ばれます。オブジェクト指向プログラミングの文脈では、レコードはオブジェクトと区別するために、プレーンオールドデータ構造として知られています。 [13]
  • ハッシュテーブル（ハッシュマップとも呼ばれる）は、キーに基づいて値を高速に取得できるデータ構造です。ハッシュ関数を使用してキーを配列内のインデックスにマッピングすることで、平均的なケースでは定数時間でのアクセスを可能にします。ハッシュテーブルは、辞書、キャッシュ、データベースのインデックス作成で一般的に使用されます。ただし、ハッシュの衝突が発生する可能性があり、パフォーマンスに影響を与える可能性があります。衝突に対処するために、連鎖法やオープンアドレッシングなどの手法が採用されています。
  • グラフは、エッジで接続されたノードの集合であり、エンティティ間の関係を表します。グラフは、ソーシャルネットワーク、コンピュータネットワーク、交通ネットワークなどをモデル化するために使用できます。グラフは頂点（ノード）とエッジ（ノード間の接続）で構成されます。グラフは有向グラフまたは無向グラフ、また循環グラフまたは非循環グラフにすることができます。グラフ走査アルゴリズムには、幅優先探索と深さ優先探索があります
  • スタックとキューは、配列または連結リストを使用して実装できる抽象データ型です。スタックには、プッシュ（スタックの先頭に要素を追加する）とポップ（スタックから最上位の要素を削除する）という2つの主要な操作があり、これらは後入れ先出し（LIFO）の原則に従います。キューには、エンキュー（キューの最後尾に要素を追加する）とデキュー（キューの先頭から要素を削除する）という2つの主要な操作があり、これらは先入れ先出し（FIFO）の原則に従います。
  • ツリーは要素の階層構造を表します。ツリーはエッジで接続されたノードで構成され、1つのノードがルートで、他のすべてのノードはサブツリーを形成します。ツリーは、さまざまなアルゴリズムやデータストレージのシナリオで広く使用されています。二分木（特にヒープ）、AVL木、B木は、一般的なツリーの種類です。これらは、データの効率的で最適な検索、ソート、および階層的な表現を可能にします
  • トライ木、または接頭辞木は、文字列を効率的に取得するために使用される特殊なタイプの木です。トライ木では、各ノードは文字列の文字を表し、ノード間のエッジはそれらを接続する文字を表します。この構造は、オートコンプリート、スペルチェック、辞書の作成などのタスクに特に役立ちます。トライ木を使用すると、文字列の接頭辞に基づいた迅速な検索と操作が可能になります。

言語サポート

ほとんどのアセンブリ言語と、 BCPL （Basic Combined Programming Language）などの一部の低水準言語には、データ構造の組み込みサポートがありません。一方、多くの高水準プログラミング言語と、 MASMなどの一部の高水準アセンブリ言語には、レコードや配列などの特定のデータ構造に対する特別な構文やその他の組み込みサポートがあります。たとえば、C言語（BCPLの直系の子孫）とPascal言語は、ベクター（1次元配列）と多次元配列に加えて、それぞれ構造体とレコードをサポートしています。 [14] [15]

ほとんどのプログラミング言語は、データ構造の実装を異なるプログラムで再利用できるようにする何らかのライブラリメカニズムを備えています。現代の言語には通常、最も一般的なデータ構造を実装する標準ライブラリが付属しています。例としては、C++ 標準テンプレートライブラリ、Javaコレクションフレームワーク、Microsoft .NET Frameworkなど があります

現代の言語は一般的にモジュールプログラミング、つまりライブラリモジュールのインターフェースとその実装の分離をサポートしています。一部の言語では、クライアントが実装の詳細を隠すことができる不透明データ型を提供しています。C ++、Java、Smalltalkなどのオブジェクト指向プログラミング言語は、通常、この目的で クラスを使用します。

多くの既知のデータ構造には、複数の計算スレッドがデータ構造の単一の具体的なインスタンスに同時にアクセスできる並行バージョンがあります。 [16]

参照

参考文献

  1. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms, Third Edition (3rd ed.). The MIT Press. ISBN 978-0262033848。
  2. ^ Black, Paul E. (2004年12月15日). 「データ構造」. Pieterse, Vreda; Black, Paul E. (編). Dictionary of Algorithms and Data Structures [online] . National Institute of Standards and Technology . 2018年11月6日閲覧.
  3. ^ 「データ構造」. Encyclopaedia Britannica . 2017年4月17日. 2018年11月6日閲覧.
  4. ^ Wegner, Peter; Reilly, Edwin D. (2003年8月29日). Encyclopedia of Computer Science. Chichester, UK: John Wiley and Sons. pp.  507– 512. ISBN  978-0470864128。
  5. ^ 「抽象データ型」。バージニア工科大学 - CS3 データ構造とアルゴリズム。2023年2月10日にオリジナルからアーカイブ。 2023年2月15日閲覧。
  6. ^ Gavin Powell (2006).「第8章：高速データベースモデルの構築」。データベース設計入門。Wrox Publishing。ISBN  978-0-7645-7490-02007年8月18日にオリジナルからアーカイブ。
  7. ^ 「1.5 ハッシュテーブルの応用」。レジーナ大学 - CS210 ラボ：ハッシュテーブル。2021年4月27日にオリジナルからアーカイブ。2018年6月14日閲覧
  8. ^ 「データが大きすぎてメインメモリに収まらない場合」インディアナ大学ブルーミントン校 - データ構造 (C343/A594) 2014年。2018年4月10日時点のオリジナルよりアーカイブ
  9. ^ Vaishnavi, Gunjal; Shraddha, Gavane; Yogeshwari, Joshi (2021-06-21). 「機械学習を用いた細粒度顔表情認識に関する調査論文」(PDF) . International Journal of Computer Applications . 183 (11): 47– 49. doi :10.5120/ijca2021921427.
  10. ^ Nievergelt, Jürg; Widmayer, Peter (2000-01-01), Sack, J.-R.; Urrutia, J. (編), 「第17章 空間データ構造：概念と設計上の選択」, Handbook of Computational Geometry , Amsterdam: North-Holland, pp.  725– 764, ISBN 978-0-444-82537-72023年11月12日
  11. ^ Dubey, RC (2014).高度バイオテクノロジー：バイオテクノロジーおよびその他の生物科学の学士および修士課程の学生向け. ニューデリー: S Chand. ISBN 978-81-219-4290-4 . OCLC  883695533.
  12. ^ シーモア、リップシュッツ (2014).データ構造（改訂第1版）. ニューデリー、インド: マグロウヒル・エデュケーション. ISBN 9781259029967 . OCLC  927793728
  13. ^ Walter E. Brown (1999年9月29日). 「C++言語ノート：POD型」.フェルミ国立加速器研究所. 2016年12月3日時点のオリジナルよりアーカイブ。 2016年12月6日閲覧。
  14. ^ 「GNU Cマニュアル」. フリーソフトウェア財団. 2014年10月15日閲覧。
  15. ^ Van Canneyt, Michaël (2017年9月). 「Free Pascal：リファレンスガイド」. Free Pascal.
  16. ^ Mark MoirとNir Shavit. 「並行データ構造」(PDF) . cs.tau.ac.il. 2011年4月1日時点のオリジナル(PDF)よりアーカイブ。

参考文献

参考文献