データ構造

カウンター by  SOHO COUNTER

データ構造とは、コンピューターがデータ処理や計算を行う際に、あらかじめデータを扱いやすいように加工しておき、計算速度が速くなるようにする、というものです。これではピンと来ないと思いますので、簡単な例を見てみましょう。

タウンページのように、店の名前と電話番号をたくさん集めたデータがあるとします。このデータが、もし、何も整理されていなかったら、お店の名前から電話番号を調べるのは、とても骨の折れる作業になるでしょう。10000件の電話番号がカードに書いてあると思えば、5000枚なり7000枚なりのカードを調べることになります。コンピューターの中に、無秩序にデータをしまっておいても、やはりコンピューターは5000件なり7000件のデータを検索することになります。コンピューターの操作は早いですから、これぐらいの処理はすぐに終えてしまいますが、手間をかけていることは変わりありません。

普通、電話帳というものは、業種で種類分けされていたり、店名のあいうえお順に並んでいるものです。そういうふうに、電話番号のデータを加工(あるいは整理すると言ったほうがいいでしょうか)しているわけです。これなら、業種で検索範囲を絞ったり、適当にページを開いて、「ここより、前だな、あるいは後ろだな」ということがわかるので、検索はぐっと楽になります。データの検索は50件程度になるでしょう。各業種、あるいは各あかさたな行に見出しをつけておけば、さらに検索が楽になります。下の図で須田乳業を検索するときは、最初に赤の見出しを見て、探している店(須田乳業)が前にあるか後ろにあるかを調べて、次に一段低い緑の見出しを見て、と、矢印のように進んで行けば、4手で見つかるわけです。コンピューターで検索を行うときも同様です。データがちゃんと並んでいて、見出しがついていれば、検索にかかる手間は少なくなり、もっと速く計算できるようになるわけです。

この例では、コンピューターなり人間なりの、検索をするほうの能力は、何も変わっていません。ただ、「店名を業種ごとに分類して、あいうえお順に並べる」という、データの加工をしただけで、作業効率がぐんと上がったわけです。もっと複雑な計算や検索、あるいは最適化組合せ最適化などにも、こういったデータ加工を用いた高速化、というのは行えます。どの程度高速化できるかは、その計算なり問題なりによります。高速化できないものもありますが、可能性はあるわけです。このように、「データの加工をするだけで、コンピューターの計算を速くしよう」、というのが、データ構造の研究です。

実際、データ構造を工夫すると、コンピューターの計算は爆発的に速くなることがあります。例えば、配送計画。1000店舗程度の問題の計算を1日くらいかけて行うプログラムが、あるデータ構造を使うと、計算時間が1分ぐらいに短くなります。スケジューリング問題などでも同じような高速化方法があります。このように、今まではとても現実的な時間では解けなかった問題が、データ構造の開発で解けるようになる可能性があるわけです。

 

 宇野毅明のホームページへ          情報学研究所のホームページへ