データが増えると何倍かかるか：実践データ構造とアルゴリズムのレッスン

試験では速かったのに

ある市役所で、住民データの重複を調べるプログラムを作りました。テスト用の100件では、一瞬で終わりました。

ところが本番の10万件で動かすと、朝になっても終わりません。

データが1,000倍になっただけなのに、なぜでしょうか。今日は、データが増えたときに手間がどう増えるかを比べます。

このレッスンのゴール

メモ

データが増えたとき、二つのアルゴリズムの手間の増え方を比べることができる。

キーワード

ことば	いみ	れい
手順の数	プログラムが比べたり足したりする回数です。
計算量	データが増えたときの手間の増え方です。
比例	データが2倍なら、手間も2倍になる増え方です。
二乗	データが2倍なら、手間が4倍になる増え方です。
n	データの数を表す文字です。	n = 1000

学生が入力するセルは、このプレビューでは空白です。

秒ではなく手順の数で比べる

同じプログラムでも、パソコンによってかかる秒数は変わります。だから、速さは手順の数で比べます。

大事なのは、データの数 n が増えたときに、手順の数がどう増えるかです。これを計算量と呼びます。

下のコードで、三つのやり方の手順を数えてみましょう。

やってみよう: 手順を数える

コード: python

# データの数 n を変えて、手順の数を数えます。
n = 1000

# 1) 合計を出す: 一つずつ足すので、n 回
steps_sum = 0
for i in range(n):
    steps_sum = steps_sum + 1

# 2) 二分探索: 範囲を半分にし続ける
steps_half = 0
size = n
while size > 1:
    size = size // 2
    steps_half = steps_half + 1

# 3) 重複チェック: すべての組を比べる
steps_pairs = 0
for i in range(n):
    for j in range(n):
        steps_pairs = steps_pairs + 1

print("n =", n)
print("合計:", steps_sum, "回")
print("半分ずつ:", steps_half, "回")
print("全部の組:", steps_pairs, "回")

# n を 2000 に変えて、三つの数がそれぞれ何倍になるか見ましょう。

増え方には名前がある

データが増えても手間が変わらないものを、一定と言います。辞書でキーを引くのがその例です。

手間がデータと同じ割合で増えるのが比例です。線形探索や合計がそうです。

二分探索は半分ずつなので、データが2倍でも1回増えるだけです。

全部の組を比べると二乗で増えます。データが10倍なら、手間は100倍です。

例: データの数と手順の数

データの数 n	一定	半分ずつ	比例	二乗
10	1	約3	10	100
100	1	約7	100	1万
1,000	1	約10	1,000	100万
10万	1	約17	10万	100億

学生が入力するセルは、このプレビューでは空白です。

よくある間違い

注意

「遅いプログラムは、速いパソコンに替えれば解決する」と考える人がいます。パソコンが2倍速くなっても、二乗で増える手間はデータが少し増えるだけで追いつきます。データが多い仕事では、まず増え方の小さいやり方を選びます。

木とグラフはこの先で学ぶ

リスト、辞書、集合のほかにも、よく使うデータ構造があります。

木は、組織図やフォルダのように、上から枝分かれする形です。グラフは、駅と路線や配送ルートのように、点と点をつなぐ形です。

どちらも、この先の学習で扱う内容です。今日は名前と形だけ覚えておきましょう。