データ構造

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ
ハッシュテーブルと呼ばれるデータ構造

コンピュータサイエンスではデータ構造は、効率的なアクセスと変更を可能にするデータ編成、管理、およびストレージ形式です。[1] [2] [3]より正確には、データ構造は、データ値、それらの間の関係、およびデータに適用できる関数または操作のコレクションです[4]、つまり、代数的構造です。データについて

使用法

データ構造は、抽象データ型(ADT)の基礎として機能します。ADTは、データ型の論理形式を定義します。データ構造は、データ型の物理形式を実装します。[5]

さまざまな種類のデータ構造がさまざまな種類のアプリケーションに適しており、特定のタスクに高度に特化したものもあります。たとえば、リレーショナルデータベースは通常データ取得にBツリーインデックスを使用しますが[6]コンパイラの実装は通常ハッシュテーブルを使用して識別子を検索します。[7]

データ構造は、大規模なデータベースやインターネットインデックスサービスなどの用途で大量のデータを効率的に管理する手段を提供します。通常、効率的なデータ構造は、効率的なアルゴリズムを設計するための鍵です。一部の正式な設計手法とプログラミング言語は、ソフトウェア設計の主要な編成要素として、アルゴリズムではなくデータ構造を強調しています。データ構造を使用して、メインメモリとセカンダリメモリの両方に保存されている情報の保存と取得を整理できます。[8]

実装

データ構造は、一般に、ポインタ(メモリアドレスを表すビット文字列)によって指定された、メモリ内の任意の場所でデータをフェッチして格納するコンピュータの機能に基づいています。このビット文字列は、それ自体がメモリに格納され、プログラムによって操作されます。したがって、配列およびレコードのデータ構造は、算術演算を使用してデータ項目のアドレスを計算することに基づいていますがリンクされたデータ構造は、構造自体にデータ項目のアドレスを格納することに基づいています。

データ構造の実装には、通常、その構造のインスタンスを作成および操作する一連のプロシージャを作成する必要があります。データ構造の効率は、これらの操作とは別に分析することはできません。この観察は、抽象データ型の理論的概念、それに対して実行される可能性のある操作によって間接的に定義されるデータ構造、およびそれらの操作の数学的特性(スペースと時間のコストを含む)を動機付けます。[9]

Python3。標準タイプhierarchy.png

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

  • バイトは、コンピュータのCPUがメモリからレジスタにコピーしたり、単一のCPU命令で戻したりできる最小量のデータです。したがって、バイトストリームは、コンピュータを介してビッグデータを実行する最も効率的な方法であり、ストリーム処理です。Ref。メモリ内のすべてのビットはバイトの一部であるため、CPUはメモリからレジスタに1ビットをコピーしたり戻したりすることはできません。[11]
  • 配列は、特定の順序の要素の数であり、通常はすべて同じタイプです(言語に応じて、個々の要素はすべて同じタイプになるように強制される場合と、ほぼすべてのタイプの場合があります)。整数インデックスを使用して要素にアクセスし、必要な要素を指定します。一般的な実装では、配列の要素に連続したメモリワードが割り当てられます(ただし、これは必ずしも必要ではありません)。配列は固定長またはサイズ変更可能です。
  • リンクリスト単にリストとも呼ばれます)は、ノードと呼ばれる任意のタイプのデータ要素の線形コレクションであり、各ノードはそれ自体に値を持ち、リンクリスト内の次のノードを指します。配列に対するリンクリストの主な利点は、リストの残りの部分を再配置することなく、値を常に効率的に挿入および削除できることです。ただし、特定の要素へのランダムアクセスなど、他の特定の操作は、配列よりもリストの方が遅くなります。
  • レコード(タプルまたは構造体とも呼ばれます)は、集約データ構造です。レコードは、他の値を含む値であり、通常は固定の番号と順序で、通常は名前でインデックスが付けられます。レコードの要素は通常、フィールドまたはメンバーと呼ばれます。
  • ユニオンは、許可されたプリミティブ型のどれをインスタンスに格納できるかを指定するデータ構造です。たとえば、floatまたはlongintegerです浮動小数点数整数を含むように定義できるレコードと対比してください。一方、ユニオンでは、一度に1つの値しかありません。最も広いメンバーデータ型を含むのに十分なスペースが割り当てられます。
  • タグ付き共用体バリアントバリアントレコード識別ユニオン、または非交和ユニオンとも呼ばれます)には、タイプの安全性を高めるために、現在のタイプを示す追加のフィールドが含まれています。
  • オブジェクトは、レコードのようにデータフィールドと、データの内容を操作するさまざまなメソッドを含むデータ構造です。オブジェクトは、分類法のクラスのメモリ内インスタンスです。オブジェクト指向プログラミングのコンテキストでは、レコードはオブジェクトと区別するためにプレーンな古いデータ構造として知られています。[12]

さらに、ハッシュグラフ、およびバイナリツリーは、他の一般的に使用されるデータ構造です。

言語サポート

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

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

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

多くの既知のデータ構造には、複数のコンピューティングスレッドがデータ構造の単一の具象インスタンスに同時にアクセスできるようにする同時バージョンがあります。[15]

も参照してください

参考文献

  1. ^ コーメン、トーマスH。; Leiserson、Charles E。; リベスト、ロナルドL。; スタイン、クリフォード(2009)。アルゴリズム入門、第3版(第3版)。MITプレス。ISBN 978-0262033848
  2. ^ ブラック、ポールE.(2004年12月15日)。「データ構造」Pieterseでは、Vreda; ブラック、ポールE.(編)。アルゴリズムとデータ構造の辞書[オンライン]米国国立標準技術研究所2018116日取得
  3. ^ 「データ構造」ブリタニカ百科事典2017年4月17日2018年11月6日取得
  4. ^ ウェグナー、ピーター; Reilly、Edwin D.(2003-08-29)。コンピュータサイエンス百科事典英国チチェスター:ジョン・ワイリーとサンズ。pp。507–512。ISBN 978-0470864128
  5. ^ 「抽象データ型」バージニア工科大学-CS3データ構造とアルゴリズム
  6. ^ ギャヴィンパウエル(2006)。「第8章:高速パフォーマンスのデータベースモデルの構築」データベース設計の開始。WroxPublishingISBN 978-0-7645-7490-0
  7. ^ 「1.5ハッシュテーブルのアプリケーション」レジャイナ大学-CS210ラボ:ハッシュテーブル
  8. ^ 「データが大きすぎてメインメモリに収まらない場合」homes.sice.indiana.edu
  9. ^ Dubey、RC(2014)。高度なバイオテクノロジー:バイオテクノロジーおよびその他の生物科学のBScおよびMScの学生向けニューデリー:Sチャンド。ISBN 978-81-219-4290-4OCLC883695533 _
  10. ^ シーモア、リプシュッツ(2014)。データ構造(初版改訂)。インド、ニューデリー:マグロウヒルエデュケーション。ISBN 9781259029967OCLC927793728 _
  11. ^ クライン、マーシャル。「C ++ FAQ:バイト、文字、および文字に関する規則」
  12. ^ Walter E. Brown(1999年9月29日)。「C ++言語注:PODタイプ」フェルミ国立加速器研究所2016年12月3日にオリジナルからアーカイブされました2016年12月6日取得
  13. ^ 「GNUCマニュアル」フリーソフトウェアファウンデーション2014年10月15日取得
  14. ^ Van Canneyt、Michaël(2017年9月)。「FreePascal:リファレンスガイド」無料のPascal。
  15. ^ マークモアとニルシャビット。「同時データ構造」(PDF)cs.tau.ac.il。 _

参考文献

さらに読む

外部リンク