用語集
- データ構造
データを効率的に扱うためにデータ構成を整える方法のひとつ
- 線形データ構造
要素を順番に配置したデータ構造
- 非線形データ構造
配置が順不同の要素同士をリンクしたデータ構造
- 走査
データ構造を最初の要素から最後の要素までたどること
- 静的データ構造
固定長で、プログラムを書くときにサイズを決めるデータ構造
- 動的データ構造
プログラムの実行中にサイズを決められ、サイズを拡大したり縮小したりもできるデータ構造
- メモリー
コンピュータがデータを覚えておく場所
- すでにPython組み込みのリストや辞書などのデータ構造を利用して、データの検索やソートを行ってきた
- 第2部では、データ構造とその扱い方について、もう少し詳しく紹介する
- 配列、連結リスト、スタック、キュー、木、ヒープ、グラフ、ハッシュテーブルなど
- これらのデータ構造にはメリットとデメリットがある
- どのデータ構造を使うとよいか
- プログラムでどのような問題を解決しようとしているのか、どこを最適化したいのか、による
- 第2部では、データ構造のメリデリを学ぶ
- アプリケーションを作成するとき、どのデータ構造を選ぶかを決められるようになる
- データ構造を理解せずに、すぐれたプログラマーにはなれない
- プログラミングは、アルゴリムを書き、それに合う正しいデータ構造を選択することが大事
- アルゴリムは、コンピュータに何をするかを指示する。そしてデータ構造は、そのアルゴリムにおいてデータをどのように格納するかを指示する
「実際のところ、良いプログラマーと悪いそれの違いは、データ構造を重要であるかどうかにあると言いたい。悪いプログラマーはコードそのものに気を遣ってしまうものだ」（リーナス・トーバルズ）
- 抽象データ型は概念で、データ構造は実装です
- 抽象データ型は、データ構造に対する操作（インターフェース）を定義したもの。データ型の実装では、可変長にするかといった詳細を決め、それに応じてメモリー効率や走査のオーダーも変わってくるが、抽象データ型では、そのような詳細は気にしません。
- たとえば、抽象データ型としてのリストは、複数要素の集まりで、各要素は他の要素との前後関係を保持する
- リストはまた追削といった要素を操作する機能をもっている
- Python組み込みの
listは抽象データ型ではなく、実際に実装されたデータ構造です
- リストという抽象データ型にもとづいた、まったく異なる2つのデータ構造を実装することもできる
- データ構造はリスト以外にも多くの種類がある
- それぞれの特徴に基づいて分類ができる
- 一例に、線形か非線形か、がある
- 線形データ構造は、要素を順番に配置していく（Pythonのリスト）
- 非線形データ構造は、配置が順不同の要素同士をリンクしていく（後述のグラフ）
- 走査は、データ構造を最初の要素から最後の要素までたどること
- 線形データ構造では、最初から最後まで簡単に走査でき、後戻りすることはない
- 非線形データ構造では、頻繁に後戻りする必要がある。
- 非線形データ構造は後戻りが必要だったり、1つのデータ要素に到達するために再帰が必要になることもよくあるため、線形データ構造よりも特定の要素へのアクセス効率は悪い
- データ構造のすべてのデータに変更を加える場合、走査が簡単な線形データ構造はシンプルな実装ですむ
- 非線形データ構造は、後戻りがあるため、設計や利用に多少手間がかかるが、SNSなどの人間関係をあらわすようなデータ構造を扱う場合には、線形データよりも効率的にデータを格納し、利用できる
- データ構造は、静的データ構造と動的データ構造がある
- 静的データ構造のサイズは固定長、動的データ構造のサイズはその要素によって拡大縮小ができる
- 静的データ構造を遣う場合は、プログラムを書くときにサイズを決める
- このサイズをプログラム実行中に変えることはできない
- データ構造内の値は変更可能
- Pythonには静的データ構造がないが、C言語などには静的データ構造がある
- 静的データ構造には、一定量のメモリーをあらかじめ割り当てておく必要がある、という問題がある
- コンピューターメモリーは、コンピューターがデータを蓄えておく場所
- メモリーにも種類があるが、本章ではコンピューターがデータを格納してアドレスを得たり、メモリーアドレスに基づいて格納されているデータを参照したりするものとする
- 必要だと思って割り当てたメモリー領域よりも小さいサイズで処理が済んだ場合、使わなかったメモリー領域は無駄になる
- 逆に、想定よりも多くのメモリーが必要になった場合でも、固定長のメモリー領域は後から拡張できない
- 固定長の連続したメモリー領域のサイズを増やそうとすると、すでに使われているメモリーアドレスと衝突する可能性が高いため、サイズを変更できないのです
- 固定長のデータ構造に想定よりも多くの要素を追加するには、想定したサイズより大きなサイズの別のメモリー領域を割り当てて、そこに元のデータをすべてコピーしてから処理の続きを行うしかありません
- つまり、事前に格納する要素数がわからない場合、固定長メモリーを必要とするデータ構造は最適ではないといえる
- 一方で、格納する要素数がわかっていて、その数が変化しないと考えられる場合は、固定長のデータ構造は可変長のデータ構造よりも優れたパフォーマンスを出せる
- 多くのデータ構造は、固定長と可変長のどちらでも表現できる
- 例えば、次章で紹介する配列は、従来のプログラミング言語の多くで固定長のデータ構造として実装されてきたが、Pythonを含む近年のプログラミング言語では可変長のデータ構造として提供されている
- 固定長のデータ構造とは対照的に、可変長のデータ構造のサイズは簡単に変えられる
- 可変長のデータ構造においては、コンピューターは要素数に応じてメモリーを追加で割り当てる
- データが不要になれば、メモリーを解放し、コンピュータはそのメモリーを他のことに使えるため、メモリーリソースを有効活用できる
- しかし、先に説明したように可変長のデータ構造は、要素へアクセスする処理速度が固定長のデータ構造にくらべて遅くなりがち
- また可変長のデータ構造はより多くのメモリーを消費することがある
- 可変長のデータ構造は、扱うデータ量がわからない場合や、メモリーを効率良く使いたい場合に選択するとよい
- たいていの場合、静的データ構造と動的データ構造のどちらを選択するかを悩む必要はない
- OSなどの低水準のプログラムや、パフォーマンス最適化のためにあらゆる対策をおこなわなければならないようなプロジェクトの場合には重要になるが、それ以外のプログラミングでは、線形データ構造（またはどの非線形データ構造）を使うべきかに知恵をしぼるべきです
- これまで紹介してきたように、データ構造それぞれに利点と欠点がある
- そうした利点と欠点は、データの挿入、削除、検索、ソートの効率、メモリー効率に大きく関係している
- たとえば、Pythonの辞書に10億の要素が格納されていても、ある要素が格納させれているかどうかの判定は非常に効率的に処理されます
- しかし、グラフ構造の中にあるデータを探すのはそれほど効率的ではない
- 次の章から、データ構造をいつ、どのように使用するかについて、より詳しく紹介していく