データ構造とはなにか
コンピュータプログラミングでの、データの集まりの形式化された構成(Wikipedia)
とあるが、本記事ではこのうち「データの集まりの形式化された構成」について深堀をしていく。
データの集まりといえば、データベースが初めに思い浮かぶと思うが、実は「データベース≠データ構造」である。
実は、以下のものもデータ構造である。
- プログラミングにおけるすべての変数
- List,Map,Set等のコレクション
- ファイル
- データベース etc…
このことから、言い換えるとデータ構造とはプログラミングにおけるアルゴリズム以外のすべて といっても過言ではない（と思う）。
実は普段からデータ構造を意識している
データ構造は実はプログラミング以外にも活かすことができる。
例えば、あなたは本を保管するときにどのようにして保管しているだろうか。
私は本棚に本を巻数順に並べて保存しているが、本の保管方法はほかにもたくさんある。
例えば「本棚に入れずに無秩序に本を保管する」というのも一つの保管方法である。
しかし、大半の人は本棚に入れて本を保管していると思う。ではなぜ私を含め、多くの人は本棚に本をいれて保管するのだろうか？
それは私たちは無意識にデータ構造のトレードオフの関係 を意識しているからだと思う。ここでは、本棚に入れる方法と無秩序に保管する方法のそれぞれのメリット・デメリットについて考えてみよう。
| メリット | デメリット | |
|---|---|---|
| 本棚に入れて本を保管する方法 | 整列されていて、本を探すのが楽 | 本を新しく買ったときに整列しなおさなければならない |
| 無秩序に本を保管する方法 | 買った後、何の操作もせずに保管ができる（整列する必要がない） | 本を探すときに大変 |
以上に示したように、普段から私たちはデータ構造について無意識的に考えているのである。
プログラミングにおいては、これらを意識的に考えなければならない機会が数多く存在する。なぜなら、コンピュータには次に示すある特性があるからだ。
コンピュータの特性
コンピュータには以下の特性がある
- 有限な記憶領域
- コンピュータが一度に記憶できる情報の量は有限である
- 記憶領域へのアクセスの正確性
- コンピュータは指定した記憶領域へのアクセスを間違うことなく、正確に行うことができる（これをランダムアクセスという）
- 高速性
- コンピュータはCPUによって、高速に記憶領域へのアクセスを行うことができる
したがって、一見なんでもできるように見えるコンピュータだが、実は記憶領域は有限であるため一度に複数の情報を保存できるわけではないし、高速に処理できるといっても限界はある。
この「どのくらい記憶領域を使うか」を定量的に表したものを空間計算量といい、「どのくらい計算に時間がかかるか」を定量的に表したものを時間計算量という。
計算量
計算量には空間計算量と時間計算量があるが、この２つのうちどちらが重要だろうか？
どちらも重要であることには変わりないのだが、近年のコンピュータの進化により記憶領域はかなり大きな領域確保できるようになった。しかし、CPUに関しては発熱の観点もあり、進化はほぼ頭打ち状態であり、今後も集積回路を用いたCPUは大きく進化しないだろう。
したがって、この２つの計算量のうちプログラマーが意識すべきは主に時間計算量だと思う。
そのため、多くの場合単に「計算量」というと時間計算量のことを指す。
計算量の具体的な算出方法は以下を参考にしてほしい。
計算量とは？プログラムの性能を計ってみよう | Shino's Mind Archive (shinoarchive.com)
まとめ
- データ構造はプログラミングにおけるアルゴリズム以外のすべて
- データ構造はトレードオフの関係
- トレードオフを考えるときの定量的な基準が計算量
- 特に重要なのは時間計算量