第九の巻 計算量を体感せよ

師範 / 目安 35分

カメ師範が、九本目の巻物を広げました。ここからが師範の段です。

「知識で知るのと、待たされて知るのは違う。同じ答えを出す二つのやり方で、商店街の売上に重複があるかを調べよ。一つは総当たり。もう一つは、先に並べ替えてから隣だけを見る。そして、それぞれが何回比べたかを数えて持ってこい」

なぜ時間ではなく回数なのか。師範はこう言いました。「時は測るたびに違う顔をする。機械の機嫌にも左右される。比べた回数は嘘をつかん。同じ入力なら、いつ数えても同じ数じゃ。ゆえにこれは、腕を測る物差しになる」

総当たりは、すべての二つ組を一度ずつ比べます。100件なら4950回。件数を2倍にすると、回数はおよそ4倍に膨れます。これが O(n の2乗) の重さです。

並べ替えてから隣を見るやり方は違います。同じ値は並べ替えれば必ず隣り合うので、隣だけを見れば足ります。件数から1を引いた回数で済みます。並べ替え自体の手間を足しても、総当たりの膨らみ方には遠く及びません。

2000件でこの2つを走らせたとき、数がどれだけ離れるか。それを自分の目で見てください。

完成条件

countCompares という関数を1つ定義してください。どの言語で解いても関数名は countCompares にしてください。Python でも snake_case ではなく、この綴りのまま使います。

引数は1つ、調べる件数 n です。

ひな形が売上データをその場で作ります。i 番目の売上は (i * 37) % 1000 です。i は 0 から n - 1 まで動きます。どの言語で書いても同じ並びになる決め方なので、生成部分はそのまま使ってください。

そのうえで、次の2つを実装してそれぞれの比較回数を数えます。

1. 二重ループ — 添字 i と、それより後ろの添字 j のすべての組み合わせについて、値が等しいかを1回比べます。比べるたびに回数を1つ増やします
2. 整列後の隣接比較 — 売上を昇順に並べ替えたあと、隣り合う2つが等しいかを先頭から順に比べます。ここも比べるたびに回数を1つ増やします

並べ替えそのものは、各言語の標準の並べ替えをひな形に用意しています。数えるのは、重複を探すための比較だけです。並べ替えの内部で起きる比較は数えません。

返すのは次の形をした1つの文字列です。

二重ループ 1999000回 / 整列後 1999回

n が 0 や 1 のときは、どちらの比較も起きません。回数はどちらも 0 になります。件数から1を引いた値をそのまま使うと、n が 0 のときに負の数になります。そこだけ気をつけてください。

進め方

ひな形の「課題」と書かれた部分から始めてください。初期化や補助処理は完成済みです。手が止まったらヒントを開けます。ヒントは3段階で、①方針、②使う構文、③部分解の順に出ます。ヒントは必要に応じて使い、書いた処理を自分で追えることを目標にします。

開かずに10分粘って進まないなら、①だけ開けてください。粘る時間そのものには価値がありません。価値があるのは、自分で書いた行が動いた瞬間です。

通ったら、n に 100、200、400 を入れて二重ループの回数がどう伸びるかを見てください。件数が2倍になるたび、回数はおよそ4倍です。一方の整列後は、素直に2倍にしかなりません。この差の記憶が、これからのあなたの設計を変えます。

組を一度ずつ数える足場

別の題材として、3人 A・B・C の握手を数えると、組は AとB、AとC、BとC の3つです。AとA は数えず、BとA も数え直しません。外側の i に対し、内側は j = i + 1 から始めます。端を含めない範囲の例は次のとおりです。

Python

for seat in range(1, 4):
    # seat は 1、2、3
    pass

JavaScript

for (let seat = 1; seat < 4; seat++) {
  // seat は 1、2、3
}

TypeScript

for (let seat = 1; seat < 4; seat++) {
  // seat は 1、2、3
}

Java

for (int seat = 1; seat < 4; seat++) {
    // seat は 1、2、3
}

データ生成・数値ソート・カウンタ初期化・外側の i のループ・出力整形は渡しています。課題は総当たりの内側ループと、整列後の隣接比較ループの2か所です。sameValue(left, right) は2つの値が等しいかを調べる補助関数です。1組を比べるたびにこれを呼び、対応するカウンタを1増やします。今回は比較の真偽を出力せず、回数だけを返します。

提供済みの生成式の % は割った余りを求める記号で、たとえば 17 % 5 は 2 です。標準ソートも完成済みで、JavaScript と TypeScript の比較関数 a - b は小さい数を先に並べる指定です。これらを書く必要はありません。n は 0〜2000 の整数です。0件や1件は比較する組が無いため、両方の回数が0になります。

1. 関数名は4言語すべてで countCompares にすること(Python も snake_case にしない)
2. 引数は調べる件数 n の1つ
3. 売上データは i 番目が (i * 37) % 1000 となるように、i を 0 から n-1 まで動かして作る提供済みのコードを使うこと
4. 二重ループは、添字 i とそれより後ろの添字 j のすべての組み合わせを1回ずつ比べ、そのたびに回数を1つ増やすこと
5. 整列後は昇順に並べ替えたあと、隣り合う2つを先頭から順に比べ、そのたびに回数を1つ増やすこと
6. 並べ替えは各言語の標準の並べ替えを使ってよいが、その内部で起きる比較は数えないこと
7. 戻り値は「二重ループ ○回 / 整列後 ○回」の形をした1つの文字列であること
8. n が 0 や 1 のときはどちらの回数も 0 にすること(負の数にしない)
9. ひな形の補助処理と出力整形を使い、総当たりの内側ループと整列後の隣接比較を書くこと
10. n は 0〜2000 の整数です。比較の真偽は出力せず、全ての比較回数を数えること