アルゴリズムとデータ構造#2 データ構造？タスクに合わせてデータを持て

はじめに

本記事は、「アルゴリズムとデータ構造」コースの第二回となります。全体の概要については、イントロダクションをご覧いただくのがよろしいかと。

対象読者(本記事)

以下のどれかにあてはまる方を対象にしています。一つも当てはまらない場合は、[次の記事]に行かれてもよいかもしれませんね。

• 「データ構造」って言われても何をイメージしたらいいのかわからない人

データ構造とは？

一言でいえば、「データをどうやってメモリ上に配置するか」です。

具体例:電車の所要時間

例えば、電車の所要時間表を考えます。
以下の表は、隣駅までの所要時間が記録されています。例えば、2駅から3駅に行くのには、3分かかるようですよ。

この表では、隣り合う駅の間の所要時間が書かれていますね。
それでは、この表をデータとしてどのように持つのがいいでしょうか？
答えは、「そのデータをどう使いたいかによる」なんですが、一番簡単なのはそのまま配列として持ってしまうことですよね。

例えば、time_tableという配列を用意して、time_table[0]には0駅目と1駅目の間の所要時間、time_table[1]には1駅目と2駅目の間……というように、time_table[i]にはi駅目とi+1駅目の所要時間を持たせてみましょう。

これはまさに、「電車の所要時間一覧」をデータ構造に落とし込んだ例であるといえます。

データ構造の作り方は、目的によって定める

さて、隣り合う電車の所要時間はわかりました。「ある駅からある駅までの所要時間を知りたい」という目的があったとします。さあ、どうしたらいいでしょう？

ナイーブな方法

一番ナイーブな方法は、time_tableを順番に見ていって、目的の駅の間の所要時間を探すことです。
例えば、「1駅目から3駅目までの所要時間」を知りたいときは、time_table[1]とtime_table[2]を足せばいいですね。
具体的なアルゴリズムは例えば以下の様になります。

def naive(time_table, start, end):
    s = 0
    for i in range(start, end):
        s += time_table[i]
    return s

このアルゴリズムの計算量は、$${\mathcal{O}(n)}$$です。
でも、隣り合うやつの場合は1回じゃん！……と、お思いになるかもしれませんが、こういう時は「最悪の場合」を考えるものです。上界ですからね。

この計算を$${m}$$個の組に対して行うときには、計算量は$${\mathcal{O}(mn)}$$となります。

"賢い"データ構造を用いてみる

しかし、このアルゴリズムは、「ある駅からある駅までの所要時間」を知りたいときに、毎回`time_table`を順番に見ていくので、実は無駄が多いです。だまされたと思って、以下のようなデータ構造を考えてみましょう。これは、「0駅から何分かければi駅に着くか」を表しています。
例えば、0駅から3駅に行くには、0から1、1から2、2から3と行く必要がありますから、合計3+2+3=8分かかりますね。

time_table_cumという配列を用意して、time_table_cum[i]には、0駅目からi駅目までの所要時間の合計を持たせます。所要時間の表に少し手を加えただけといえます。例えば以下のように作れますね。

def make_cum(time_table):
    time_table_cum = [0]
    for i in range(len(time_table)):
        time_table_cum.append(time_table_cum[i] + time_table[i])
    return time_table_cum

このようなデータ構造を作っておくと、「ある駅からある駅までの所要時間」を知りたいときは、time_table_cum[end] - time_table_cum[start]を計算するだけで済みます。なぜって？0駅からend駅までが12分で、0駅からstart駅までが3分だったら、start駅からend駅までは9分ですよね。途中の駅に何分かかるとかは、実は余計な情報でした。

def cumsum(time_table_cum,start,end):
    return time_table_cum[end] - time_table_cum[start]

1回あたりの計算量はなんと$${\mathcal{O}(1)}$$、つまり定数時間！前処理のかかる時間は$${\mathcal{O}(n)}$$です。
つまり$${m}$$回繰り返した時の計算量は、$${\mathcal{O}(m+n)}$$となります。$${m}$$も$${n}$$も大きいときには、$${\mathcal{O}(mn)}$$と比べてかなり効率的ですね。

これは、データの持ち方を工夫することで、効率的なアルゴリズムが適用でき、計算量を減らすことができた例といえます。

データ構造というと、なにか複雑なライブラリや魔術を使うようなイメージがあるかもしれませんが、ここで使ったのは配列だけですし、配列でも工夫することで計算量を減らすことができることがわかります。

まとめ

• データ構造は、データを持つための方法

• 計算量を減らすために、データ構造を工夫する

• 工夫したデータ構造の上に、アルゴリズムを作る

次回の記事からは、初心者が知っておくべきデータ構造の土台を紹介します。まずはシンプルに、配列とリストから攻略していきましょう。