データ構造とは？
データ構造は、データをコンピュータの中で扱う際にデータを格納する一定の形式のこと。
代表的なデータ構造
Bag、Sequence、Tree、Mapの4つの構造がある。
Bag
データを格納した順序付けはなく、重複したデータを格納することができる。
Bagの中で重複を許さないものをSetという。
- Bagは重複データを扱える
- 延べ人数を記録するようなデータにむいている。
- Setは重複を除ける
- ユニークな人数を記録するようなデータに向いている。
Sequence
データが順に並んでいるような構造をSequenceという。
データの格納順をインデックスとして記録できるため、特定の要素を指定して参照したり、取り出したりといった操作が可能。
Sequenceの実装方法として、主に配列とリストがある。
配列 Array
同じ型のデータをインデックスをもとに格納していく。
この時、型とは数値や文字列といった個々のデータに対する型のこと。
要素数をあらかじめ決めてからデータを格納するため、領域の拡張ができない。
データを確保するには、予め余分に領域を確保するか、より大きい配列を新しく作成し、現在の内容をコピーして移す必要がある。
データにアクセスする際の計算量は、インデックスをもとに直接指定の要素アクセスができるので、O(1)、データ探索はインデックスをたどる必要があるので、O(n)。
リスト List
リストは各要素に次の要素のリンクを保持させる。チェーンみたいな構造。
最後の要素はリンクを持たせないことで表現する。
2種類ある
- 単方向リスト
- 一定の順序でしかアクセスできないもの
- 双方向リスト
- 前後のリストを保持しているもの
リストはあらかじめ要素数を決めておく必要がなく、データの増減に合わせて調整することができるので、データを記録するためのメモリ効率が良いというメリットがある。
しかしデータを取り出す際には、最初の要素から順にリンクを辿って行かなければならないため、計算量は__O(n)と要素数に合わせて増えてしまう。
追加する際は直接挿入したい場所に追加できるので、計算量は__O(1)。
Tree
木構造。階層関係を表すことができる。PC内のfolderもこの構造。概念の上下関係（親子関係）があるような関係を階層関係という。
木構造では、ひとつひとつの要素をノードという。親に当たるノードを持たないノードをルートといい、子に当たるノードを持たないノードをリーフという。
それぞれのノードをつなぐ枝はエッジという。
二分探索木
木構造にも様々な種類があるが、二分探索木を例に考える。
ルートノードの任意の値に対して、左のノードはルートノードよりも小さく、右のノードはルートノードよりも大きいという関係が成り立つように値を入れていく。これを下の階層のノードでも繰り返します。
データを取り出す際には必ずルートから順にノードを探索する必要がある。
計算量は木構造の階層の数に比例し、__O(log n)__となる。
ただし、木構造の一方にノードが集中して偏った構造になる場合__O(log n)__よりも遅い__O(n)__に近づいて遅くなる傾向がある。
Map
Mapの最大の特徴はひとつの要素内に、データの場所表す「キー」と、データの「バリュー」を対応づけて格納すること。
データの保管場所をキーとすることで、SequenceでもTreeでも実装することができる。
ハッシュ Hash
キーとの結びつけをハッシュ関数という計算式によって行います。
まず格納するデータからハッシュ関数を用いて、ハッシュ値という値を得ます。その値をキーとしてでデータを格納する場所を決めます。
しかし、別々のデータから計算したハッシュ値が等しくなることがある。これを__衝突__という。
衝突の解決策
- クローズドハッシュ法
- ハッシュ値を求め直して格納場所を移動させる方法
- オープンハッシュ法
- 同じ要素の中でリスト構造を作りデータを追加していく方法
その際に、ハッシュ値を求め直して格納場所を移動させることをクローズドハッシュ法という。
また、同じ要素の中でリスト構造を作りデータを追加していく方法
まとめ
計算量を少なくするには、コードのアルゴリズムだけでなく、データ構造との関係性が重要になってくる。
参考
開発新卒に捧ぐ、データ構造の基本と特徴 | TECHSCORE BLOG
https://www.techscore.com/blog/2016/10/05/%E9%96%8B%E7%99%BA%E6%96%B0%E5%8D%92%E3%81%AB%E6%8D%A7%E3%81%90%E3%80%81%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0%E3%81%AE%E5%9F%BA%E6%9C%AC%E3%81%A8%E7%89%B9%E5%BE%B4/