Chapter05から、データ構造について学んでいきます。

『アルゴリズム＋データ構造＝プログラミング』という古典的な名著がありますが、大量のデータを扱う上でデータ構造はとても大切です。それは「プログラミングだから〜」というワケではなくて、私たちが普段日常で行なっていることと全く同じです。

・データ構造とは何か？
・アルゴリズムと何が違うのか？
・どのような使い道、どんなメリットがある？

といったトピックについて学んでいきたいと思います。

データ構造とは何か？

データ構造とはデータを効率的に扱うための組み合わせ方のことです。

データ：データ、情報
構造：組み合わせ方、モノ同士の関連

という2つの言葉が組み合わさった概念です。

「データを扱うのにそのままじゃいけないのか？」と思うかもしれせん。しかし情報量が増えた時はその扱い方を工夫する必要があります。というのも、ゴロだしのデータをそのまま扱うのは非効率になってくるからです。

本を探す場合

本屋さんで本を探す場合を考えてみましょう。この時に本が棚へテキトーに入ってたらどうでしょうか。

ジャンルがバラバラ
横積みで取り出しづらい
背表紙を後ろに向けてる　
検索できない

テキトーに本が置かれている中から探すとなると、かなり大変ですよね。しかし実際の本屋さんは探しやすい工夫がしてあります。

ジャンルごとに分ける
取り出しやすいように縦置き
タイトルを外側に向ける
目的の本を検索・在庫確認

今回探したのは本でしたが、これはデータを扱う場合でも全く同じです。

データを扱うための工夫

情報量が大きくなってくると、乱雑にデータを格納してはかなり非効率になってしまいます。確かにコンピュータは情報を高速に処理できる機械です。しかし１つ１つデータを探させているようでは本来の力を発揮できません。

先程の本屋の例もそうですし、私たちの普段の生活でも同じです。データを効率的・カンタンに扱うには、コンピュータにとっても工夫が必要です。

アルゴリズムと比較

次はアルゴリズムと比べながら考えます。アルゴリズムとデータ構造は必ずセットで出てくる言葉ですよね。２つは似たような言葉と思われていますが、どのような違いがあるのでしょうか。

結論からいえば、これは料理で考えると分かりやすいと思います。

アルゴリズム　→　料理のレシピ（＝作業手順）
データ構造　→　料理の具材をどう扱うか？（＝データの取り扱い方法）

といった違いがあります。

カレーを作る場合

料理でカレーを作るとします。この時にカレーのレシピがアルゴリズムです。アルゴリズムとはある目的を達成するための作業手順のことでしたよね。カレーという目的の料理を作るためのレシピ（作業手順）というのが、アルゴリズムを指しています。

そしてデータ構造は「具材をどう扱うか？」を指します。土から出てきたジャガイモを泥だらけのまま鍋に放り込むことはしないですよね。

・子供用なら小さく切る
・大人用なら大きめに切る
・好みによって柔らかめ、固め
・形を四角、丸くする

確かに最低限、水で洗って皮を向いてあれば食べることはできます。しかし、その人の好みに合った形で準備しておけばもっと美味しく食べれますよね。それはデータ構造でも全く同じです。このようにアルゴリズムとデータ構造にはすごく密接な関係があります。

アルゴリズムは作業手順であり、そもそも作業手順が間違っていたらゴールに辿り着くことはできません。しかしやり方が正しくても、データが扱いづらければ時間がかかってしまいます。 アルゴリズムが本来の力を発揮するためにもデータ構造は非常に大切です。

目的に合ったデータ構造

注意して頂きたいのが、データ構造には色々な種類がある点です。先ほどカレーを作る際に、素材であるジャガイモをどのように調理するか？という例を出しました。

・水で洗う、皮をむく
・子供用なら小さく切る
・大人用なら大きめに切る
・好みによって柔らかめ、固め
・形を四角、丸くする

目的によってジャガイモの切り方・煮方・盛り付けは全く変わってきますよね。これと同じでデータ構造というのも、目的によって色々な方法が考えられます。どのようなデータ構造をとれば効率的か？を考えるのが、プログラマの腕の見せ所です。

かつてビルゲイツは『アルゴリズムを考えるよりも、データ構造を設計する方が面白い』と話しました。用途に合わせたデータ構造を考えることも非常にクリエイティブな作業です。

注文を受け取るアプリ

レストランでお客さんの注文を取るためのアプリケーションを作るとします。お客さんから受けた注文を古い順から厨房へと送っていく必要があります。この場合、どのデータ構造を使うべきでしょうか。そのままテキトーにデータを送っていると、順番が前後などしてお客さんを待たせてしまうかもしれません。

この場合に利用されるのがキューというデータ構造です。キューとはカンタンにいえば、ラーメン屋の待ち行列方式です。古い方からデータを処理し、新しい情報は末尾へ追加されます。これによって、先に注文したお客さんを優先して料理を作ることができます。

このようにシチュエーションに応じてデータの扱い方は工夫する必要があります。

学校の生徒を管理するアプリ

もう１つ具体例を考えてみます。例えば、学校の生徒を管理するプログラムを作る場合はどうでしょうか。この時にはどのデータ構造が良いでしょうか。学校にはたくさんの生徒がいるので、名前だけで管理するのは大変です。このようにゴロだしの情報だけではかなり扱いづらいのがお分かり頂けると思います。

そこで利用されるのが構造体です。構造体とは、１つのデータに情報を付加するための仕組みです。生徒の名前に番号・学年・クラスなど、特定のための様々なデータをくっつけます。これによってグルーピングや番号による検索など、効率的な管理が可能になるのです。

データ構造のハイブリッド

更にいうなら、データ構造のハイブリッドも可能です。生徒の人数が多い場合、構造体を１つ１つ作っていては面倒です。そこに配列というデータ構造を使えば、数百人分の構造体を一瞬で作ることも可能になります。このように複数のデータ構造を組み合わせて、問題を解決することもできます。

ここまでキュー・構造体・配列の３つのデータ構造が登場しましたが、他にも目的に応じて様々なデータ構造があります。

パソコンのファイル　→　階層構造
ブラウザの戻るボタン　→　スタック
ホテルのキャンセル待ち　→　キュー
FaceBookのユーザー名　→　配列・連結リスト

このように場面に応じてデータ構造が使われる点を覚えておきましょう。

まとめ

・データ構造とはデータを扱いやすくするための仕組み
・データの量が増えると扱いやすさが問題になる
・アルゴリズム＝作業手順、　データ構造＝データの扱い方
・データ構造には色々な種類があり、目的に応じて使い分けることが大切