ソフトウェアのバグをなくすには？--プログラミングの際に避けるべき10の失敗 - (page 6)

＃10：適切なデータ構造を選択しない

　データ構造は、データをプログラム内で表現するうえでのメカニズムと言える。連結リストや木構造、配列といった用語を耳にしたことがある人も多いはずだ。これらはそれぞれ、描写しようとしているデータの構造に対応付けられたデータの論理的表現形式だ。

　データ構造を適当に選択してしまうという過ちを、筆者はよく目にしている。こういった過ちは、新米プログラマーに限らず、経験豊富なプログラマーでもおかしてしまっている。コードのほとんどすべては、プログラマーが選択したデータ構造をベースにして組み立てられるため、不適切なデータ構造を選択すると、後で手痛いしっぺ返しをくらいかねない。

　この手の設計ミスの例を挙げてみよう。データ構造として、リングバッファではなく、単純なスタックやキューを選択したと考えてほしい。スタックは、皿の積み重ねにたとえることができるデータ構造だ。1枚目の皿（データ）を置いた後、その上に別の皿を置き、さらにその上に別の皿を、という具合に皿をどんどん積み重ねていく。

　皿を1枚取る場合、一番上にある皿を取ることになる。これは後入れ先出し（LIFO：Last In First Out）と呼ばれている。このデータ構造では、何枚か前に置いた皿を取りたい場合、面倒なことになる。10枚の皿が積み重ねられている状態で最初に置いた皿を取るには、その上に重ねられた9枚の皿をどうにかする必要があるのだ。

　次に、キューというデータ構造に目を向けてみよう。これは銀行で順番待ちをしている人の行列にたとえることができる。最初に対応してもらえるのは、列に最初に並んだ人だ。その人の対応が済めば、次に並んでいた人が列の先頭になり、その人に順番が回ってくる。つまり、誰かが対応してもらうたびに、並んでいる人は1歩前へ踏み出し、列が前に進んでいくわけだ。

　では、あまりにも多くの人々が銀行に来た場合はどうなるのだろうか？彼らは出直してくるよう言われるか、列が銀行の外にまで続くことになる。後者の場合、最初の人が呼ばれると、その後ろに並んでいる全員が1歩前に進むわけだ。

　こうしたデータ構造は、データの量が膨大になると極端に効率が低下する。キューの先頭にあるデータが取り除かれるたびに、後続のデータすべてを移送しなければならないためだ。今はビッグデータの時代であり、システムの中は常にデータが流れている状況だ。

　この点を考えた場合、リングバッファ上にキューを構築するという手を検討すべきだろう。このようにすれば、データの移送は不要となる。代わりにキューの先頭と最後尾を指すポインタを用意するのだ。リングバッファはバッファを線形に並べるのではなく、（論理的に）リング状につないだものだ。つまり、リングバッファ上ではキューの先頭と最後尾がつながり、データは列状ではなくリング状に並ぶことになる。キューの先頭にあるデータの処理が完了し、キューから取り去る場合でも、後続の全データを移送する必要はない。キューの先頭を指し示すポインタを更新し、リング内の次のデータを指し示すようにするだけだ。

　これは、適切なデータ構造を選択するかどうかがコードの効率や有効性を大きく左右するという、数ある例のうちの1つでしかない。