データ構造に関する世界観です。アルゴリズムも参照のこと。
データ構造とは、プログラムで使われるデータをどのように保管・格納し、どのような順番で要素を追加・取り出しをするか、複数のデータをある一定の順番でどのように連結・管理するか、という「データの構造」のこと。
データの連結の仕方には配列とリストがあり、データの格納・取り出しの順序によってキューとスタックがある。
配列・リストやキュー・スタックに限らず、ある目的のためのデータの構造のことをデータ構造と呼ぶ。どのようにデータを保管するか、どのようにデータを書き換え取り出すかという、プログラミングはアルゴリズムとデータ構造で成り立っている。
後日注記:連結リストは、データとデータがポインタによって紐付けされるため、任意の場所に追加・削除しやすい。このため、配列のサイズがよく変わる場合によく使われる。また、集合は要するにビットフラグのことで、数値によって複数のフラグを「ビットを立てる」ことで実現できる。また、キューは異なるシステムを接続してやりとりをするインターフェースや、異なる機器やネットワークにおけるサービスの要求のためによく使われる。
後日注記:集合はビットフラグであるとするのは誤解を招く表現だった。集合はビットフラグによって表されることもあるが、セット専用のデータ構造を使って表されることも多い。基本的に、リスト(順番のある複数の要素の集合)、マップ(キーと値を持つ要素の集合)、セット(順番のない複数の要素の集合)という3つのデータ構造がC++でもJavaでも用意されている。スタックとキューがひとくくりにされるのと同様、この3つのデータ構造はよくまとめて分類される。
後日注記:スタックとキューはとてもよく使われます。入れ子構造になっているものは、スタックあるいはツリーで表現できることが多いです。キューは行列が生まれるような待ち状態が発生するところで必ず使われます。
(一部の内容で絵で見てわかるITインフラの仕組み (DB SELECTION)を参考に執筆しました。)
自分の書いたブログ「神々とともに生きる詩人」2021/01/19より。
プログラミングにおいて、データ構造はさまざまな場面で使われる。
たとえば、既出の単語を検索するために、二分木構造を使い、アルファベット順で先のものは左の子要素に、後のものは右の子要素にと、常に整理されたデータ構造を保つことで、最短で探索を行うアルゴリズムは、K&Rなどで紹介されていることもあり、よく知られている。
反対に、頻繁にデータを書き換える場合には、データの矛盾が発生しないことが大切になる。
複数のスレッドから操作する場合は、排他制御とロックが必要となり、デッドロックにならないように、処理の順番を同じにする。
また、データの値をある種のフラグや状態と見なし、データが変わるとプログラムの制御が変わるようにする、制御モデルも考えられる。
より応用的な例では、スタックと再帰が考えられる。
たとえば、数学の算術式におけるカッコや、HTMLやXMLのタグは、最後に開いたタグが最初に閉じるタグとなるため、再帰とスタックで実現できる。
また、設定ファイルやコンパイラなどは、文字列のトークンを解析する字句解析の後に、構文ルールからパースツリーを作る構文解析を行う。
また、より発展的な内容であれば、スクレイピングによって取得したWebページのソースを、自動で処理し、GUIでたとえばIEコンポーネントで表示するのも、一般的なデータ処理である。
ほかにも、配列やリスト、ツリー、ヒープ、グラフなど、さまざまなデータ構造があり、データベースを使ったり、PythonやR言語のデータフレームを使ったり、マッピング関数などでコールバック関数となる関数オブジェクトを、データにひとつひとつ適用したりすることもある。
場合によっては、オブジェクト指向のカプセル化や、イテレータを使うことで外部から分からないように隠蔽する。
メッセージキューなどは、リアルタイム性や連携が必要な時に、システムとシステムを繋げ合うグルーの役目をする。
このように、プログラミングにおいてデータ構造は、とても重要である。
(一部の内容でCode Reading ~オープンソースから学ぶソフトウェア開発技法~ (プレミアムブックス版)を参考に執筆しました。)
データ構造はプログラミングの色んなところ、いたるところで活躍します。
たとえばLinuxカーネルでも、独自の双方向リストを使ってファイルシステムの内部情報を管理したりしています。
また、コンパイラやインタプリタ、メモリ管理などでも、スタックとヒープのデータ構造は必須です。
データベースでは、Bツリーと呼ばれる独自のインデックス構造によって、高速なデータ検索を実現しています。また、データ構造を自分で独自に設計することは、データベースでも重要です。
データ構造を考える上で参考になるのが、オブジェクト指向モデリングのクラス図とシーケンス図です。
クラス図はクラスごとの属性や関係性、シーケンス図は処理の流れを時系列にして、図にしたものです。
オブジェクト指向モデリングも参照のこと。
また、データベースにおいてはE-R図を描くことで、エンティティ(実体)とリレーションシップ(関連)の関係性を図にすることができます。
データ構造について言えることとして、「劣ったエンジニアはコードに悩むが、優れたエンジニアはデータ構造に悩む」というのが言えます。
実際のところ、プログラムとはデータを扱う手続き・操作・処理にすぎません。プログラムで悩むのではなく、データ構造をどうすれば良いかを考えることこそ、コードを書く上で、プログラマには必要なのです。
データ構造をなぜ使うのか、それは順次的にアクセスできないような複雑なデータを扱うためなどが挙げられます。
たとえば、ファイルは先頭から末尾まで、順次的にアクセスすることはできますが、それ以外のアクセスの方法は考えられていません。
しかしながら、場合によっては、順次的にアクセスするだけではなく、表の行や列としてアクセスしたり、ツリー構造にしてアクセスしたい時などもあります。
このような時、いったんファイルを読み込んだ上で、データ構造に変換し、そのデータ構造に基づいてアクセスすることで、順次的ではない複雑なアクセスをすることができます。
もちろん、このデータ構造の変換ルーチンは、関数として専用のルーチンを用意します。
あるいは、単純にオブジェクトとファイルを変換するなら、シリアライズを使う方法もあります。
単にファイルの内容を順番に読み書きするだけでできること以上のことをしたくなった場合には、データ構造を使ってみてください。
データ構造はアルゴリズムと密接に結びついています。なんらかのアルゴリズムを書きたい時に、それ専用のデータ構造を用いることがあります。
アルゴリズムとデータ構造は不可分の存在です。アルゴリズムのあるところにデータ構造はあり、データ構造のあるところにアルゴリズムがあると言えます。
アルゴリズムも参照のこと。
(以下のページはRuby Way 第2版 (Professional Ruby Series)とCode Reading ~オープンソースから学ぶソフトウェア開発技法~ (プレミアムブックス版)を参考に執筆しました。)
・ツリー
・グラフ
ここに書いたデータ構造は、一例です。実際のシステム開発では、むしろ、これらの変化形である「亜種」が多いです。
たとえば、連結リストであれば、データ構造の中の配列やテーブルの中の一部の要素が、別のデータ構造にくっついていたりするような、「連結リストやテーブルの亜種」があります。テーブルなら、それぞれの属性が複雑に絡み合っていて、構造体の中にさらに構造体(あるいは構造体へのポインタ)があったり、属性が別のテーブルやリストへのポインタになっていたりすることもあります。
また、ハッシュテーブルの実装として、配列からポインタを通じて連結リストに繋がっていたりすることもあります。これは単にマッピングの問題ではなく、高速化や効率の問題(少しでもデータベースを速くするための設計)でもあります。
このように「亜種」あるいは「複数のデータ構造の組み合わせ」となることがあるため、データ構造は簡単に言い述べることはできません。もちろん、システムや言語にはそんな亜種は用意されていないため、自ら構造体やクラスの設計をして「自分で作る」ことになるでしょう。
後日注記:連結されたデータ構造はすべてグラフであると考えることもできます。グラフ操作の詳細はグラフ理論を参照してください。
データ構造について言えるのは、なんらかの原理原則の下に、常に整理された状態を保つように使うことが多いということです。
スタックやキュー、あるいはツリーやグラフなどのデータ構造は、単にデータを格納して保持するためにも使いますが、それだけではなく、「なんらかの原理原則」のあるアルゴリズムを実現させるための手段として使うことが多いです。
特に多いのが、なんらかのリソースを常に効率的に保持するためにデータ構造を使う例です。なんらかの仮想的なリソースが存在して、そのリソースを効率的に確保したり、あるいは効率的にアクセスしたりすることができるようにするために、データ構造を使うことがとても一般的です。
データ構造だけを学んでも、このような「データ構造を応用するための手法」を学ぶことがなければ意味がありません。幸い、多くのデータ構造に関する書籍が、このような「アルゴリズムとデータ構造によるロジックの実現」を教えているので、そのような本を読んで参考にするといいでしょう。
ふつうのLinuxプログラミング Linuxの仕組みから学べるgccプログラミングの王道で言われているように、ソフトウェアのソースコードを読む際には、データ構造から確認しましょう。
データ構造が何を意味しているのか分からないままプログラムを解析するのと、データ構造が分かった上でプログラムを解析するのとでは、プログラムの理解のしやすさが異なります。
C言語なら、まず、struct Hoge { ... };が何を意味しているのか、ということからプログラムを理解すれば、巨大なプログラムであってもソースコードの意味を理解することがしやすくなるでしょう。
2023.01.21
データ構造を分析する上で、データ構造にとって大切なものがなんであるかと言えば、「順番」「結びつき」そして「アクセス手段」だと思います。
どのようにデータが順序関係を持っていて、データとデータがどのように結びついていて、どのようにデータに順序的あるいはランダム的にアクセスする手段があるか、ということが、データ構造においては重要です。
ほかには、「取り出す方法」と「追加する方法」も重要です。
データ自体がどのような規則性を持って整理されていて、その中からデータをどのような順番で取り出すか、どのような位置に新しく追加するか、削除するか、ということが重要になります。
また、データ構造を考える上で重要なのは、「効率」と「パフォーマンス」です。システムが最大の効率とパフォーマンスを発揮するために、どのようにデータ構造を設計し、実装するか、ということが、全体のアルゴリズムにおける大きな効率とパフォーマンス上の力を左右します。
2023.03.17
僕が思うに、プログラミングの基本は「パース」「データ構造」「表示」だと思います。
データをファイルなどから正規表現によって「パース」する部分、パースしたデータを「データ構造」として保持する部分、データ構造を「表示」する部分があれば、プログラミングはできると思います。
僕もかつて2ちゃんねる専用ブラウザを改造していた頃がありましたが、僕はパース部分ばかりを書き換えていて、残念ながらデータをどのように保持して表示していたか覚えていません。
ですが、まずパースするところから作って、それをデータ構造に保持し、表示することができたら、それで大丈夫だと思います。
パースする部分は簡単です。サーバーからダウンロードしたdatファイルを保存して読み書きし、正規表現にマッチさせるだけです。
データ構造の部分も簡単です。単に構造体かハッシュテーブルを作ればいいだけです。
問題はビューの部分ですが、僕の触っていた2ちゃんねるブラウザは、どれもIEコンポーネントを内部で使って、HTMLのテンプレートを用意して、中身に変数の値を代入して、表示させていたと思います。
ただし、中にはIEコンポーネントを使わず、独自の軽量なビューを使うブラウザ(Jane Doeなど)もあったので、それはそれでビューを作ればいいと思います。ビューを作るためにはリッチテキストエディタのコンポーネントを利用すればいいでしょう。
また、データ構造を保持する部分では、データ構造の内容と、データファイルやビューとの間で矛盾が起きないようにしないといけませんが、これはハッシュ関数を使ってコンポーネントのハッシュ値を記録すればいいかもしれません。
2ちゃんねる専用ブラウザも参照のこと。
2024.06.16
以下の書籍が参考になります。