- 物理機リージョン/AZ
- ハイパーバイザVM exit で捕まえる
- VMゲストOS
- コンテナnamespace / cgroup
- プロセスアプリ / DB今ここ
第11期の初回です。ここまでは装置と層を見てきました。この期は、その上で動くプログラム自身の性質、つまりデータの置き方と手順の選び方を扱います。
まず結論
秒数は機械や状況で変わりますが、n を増やしたときの増え方は変わりません。だから計算量は、機械をまたいで持ち運べる比較の道具になります。
ただし増え方だけを残して定数倍を捨てているので、「どちらが速いか」の答えにはなりません。第11期では、この道具で何が言えて何が言えないかを、公式文書と実測の両方から確かめます。
1000個の要素から1つを探します。片方は O(n) の線形探索、もう片方は平均 O(1) のハッシュ。速いのはどちらでしょうか。
当てることが目的ではありません。外した予測ほど記憶に残るので、直感で選んでください。
秒数は持ち運べないが、増え方は持ち運べる
「この処理は 3ミリ秒です」という報告は、それだけでは他の場面に持ち出せません。機械が違えば変わり、同じ機械でも他の仕事が走っていれば変わります。
そこで測る対象を取り替えます。秒数ではなく、入力の件数 n を増やしたときに手間がどう増えるかを見ます。件数を10倍にしたとき、10倍になるのか、100倍になるのか、ほとんど増えないのか。この増え方は、機械が速くても遅くても同じ形になります。持ち運べるのはこちらです。
O記法はその増え方を書く道具です。n に比例して増えるなら O(n)、n を増やしてもほぼ変わらないなら O(1)、と書きます。これは増え方の上界を示す書き方で、係数は残しません。2倍の手間も100倍の手間も、n に比例していれば同じ O(n) です。
ここから重要な帰結が出ます。O記法は比較の道具であって、予測の道具ではありません。 増え方は比べられますが、「何秒で終わるか」も「どちらが速いか」も、そこからは出てきません。
同じ2つを比べて、差が消える条件と4万倍になる条件
実物で確かめます。Python の list(線形探索・O(n))と set(平均 O(1))に同じ件数を入れ、in で1つ探す時間を測りました。
--- n = 1000 ---条件 list in (ns) set in (ns) 比先頭 21 20 1.03x中間 2617 24 110x末尾 5196 24 219x不在 5457 20 271x--- n = 200000 ---条件 list in (ns) set in (ns) 比先頭 18 19 0.95x中間 490359 23 21284x末尾 1017336 24 42478x不在 971035 20 49724x
測定環境: Apple Silicon 上の Docker、コンテナ内は Python 3.12.14 / Linux 6.10.14-linuxkit-aarch64。timeit で数千回以上繰り返し、1回あたりに割り戻した値です。1回だけ測ると計時器の刻み(約42ns)しか読めません。 絶対値は一般則ではありません。比は丸める前の値から計算したので、表の ns どうしを割るとずれます(不在の行は 48,552)。
先頭の行を見てください。n=1000 で先頭を探すと list が 21ns、set が 20ns。比は1.03倍で、差は1割もありません。 set はハッシュ値の計算から始まりますが、list は1個目で当たれば1回の比較で終わります。この条件では O(n) と平均 O(1) の差が誤差に埋もれます。
同じ2つを n=200000 の末尾で比べると42478倍。比は0.95倍から49724倍まで動きます。 だから「線形探索とハッシュは何倍違う」という一文は、n と探した位置を書かないかぎり意味を持ちません。
「ハッシュ表の操作は O(1) です」という説明を、C++ の標準規格の書き方と照らすとどう評価できますか。
規格は3つの言葉を書き分けている
「O(1) だから速い」が成り立たない例を見ました。規格の側は、もっと慎重な書き方をしています。
C++ 標準ドラフトの [unord.req.general] は、ハッシュ表についてこう述べています。
The worst-case complexity for most operations is linear, but the average case is much faster.
同じ操作について、最悪は線形、平均はずっと速いと2つ並べています。「ハッシュは O(1)」という一語の要約は、規格が分けている2つを1つにつぶしたものです。
さらに同じ規格の [sequence.reqmts] には、第3の語が出てきます。
Operations other than prepend_range and append_range are implemented so as to take amortized constant time.
amortized constant time、ならし定数時間です。worst-case / average case / amortized の3語が、すべて規格の本文に実在します。 平均は入力の分布を仮定した話、ならしは操作列の合計を回数で割った話で、前提が違います。混ぜて使えません。
- ・O記法まで残るのは増え方だけ。所要時間は復元できない
- ・3語のどれかを書かずに O(1) とだけ言うと、成り立つ条件が消える
では増え方は、本当に持ち運べるのか
捨ててよいものを捨てた結果、何が残るのかを同じ実測で見ます。n を変えて同じ操作を測ったものです。
== set in を n を変えて: 増えないことを見る ==n set in (ns)1000 25.110000 24.2100000 23.61000000 23.5== list in (末尾) を n を変えて: n に比例することを見る ==n list in (ns) 前のnからの倍率1000 4961 -10000 48785 9.8x100000 488708 10.0x1000000 4767313 9.8x
n を1000倍にしても、set は 25.1ns から 23.5ns。 list は 4961ns から 4767313ns で、約961倍です。
右端の列が肝心です。n を10倍するたびに 9.8倍、10.0倍、9.8倍。 読み取るのは係数ではなく、「10倍にしたらおよそ10倍」という関係が3回とも保たれたこと。この関係は機械を替えても形が残ります。23.5ns や 42478倍という値は残りません。
第4期『AIはなぜ次の語を選べるのか — 確率分布から1つを取り出す』で、Transformer の自己注意層の計算量を O(n² · d) と引きました。あれも同じ道具です。増え方は言えますが、そこから何秒かかるかは出てきません。
「この改良で計算量は変わらないが、実際の速さは大きく変わる」という言い方は成り立ちますか。
n=1000・先頭を探す
件数が小さく、探す対象が先頭にある場合です。list は1回の比較で当たり、set はハッシュ値の計算から始まります。計算量は O(n) 対 平均 O(1) ですが、実測の差は1割もありませんでした。
構造 計算量 実測 結果list in O(n) 21ns ほぼ同じset in 平均 O(1) 20ns ほぼ同じ
n=200000・末尾を探す
件数が200倍になり、探す対象が末尾にある場合です。list は末尾まで全部たどり、set は n が増えてもほぼ変わりません。計算量の差が、そのまま実測の差として現れます。
構造 計算量 実測 結果list in O(n) 1017336ns 遅いset in 平均 O(1) 24ns 速い
同じ list と set を比べているのに、一方では差が1割も出ず、もう一方では set が42478倍速い。この2つから言えることは何でしょうか。
2つの表で変わっているのは計算量の欄ではなく、条件のほうです。
この章のまとめ
- 秒数は機械と状況で変わるが、n を増やしたときの増え方は変わらない。だから計算量は比較の道具として持ち運べる。
- 増え方を残すかわりに定数倍を捨てている。Python の TimeComplexity ページ自身が、計算量は変わらないのに実際の速さは大きく変わる例を記している。
- O記法は「どちらが速いか」を答えていない。 実測では、n=1000 の先頭で O(n) の list と平均 O(1) の set に1割の差も出なかった(21ns 対 20ns)。同じ2つの比は0.95倍から49724倍まで動く。
- 最悪・平均・ならしは別物で、C++ 標準ドラフトはこの3語を書き分けている。どれの話かを書かずに O(1) と言うと、成り立つ条件が消える。
- 倍率を引用するときは、n と条件を必ず添える。条件を外した倍率は、当てはまらない場面へ持ち込まれる。
自分の現場で確かめる
読んだだけでは身につきません。手元の環境で実際に見てみてください。
理解度チェック
読んだ直後は「分かった」と感じやすいものです。実際に解いて確かめてください。
「線形探索とハッシュでは7000倍の差が出ます」という一文の問題点はどれですか。
用語集(5語)
- 計算量 (O記法)
- 入力の大きさ n を増やしたとき手間がどう増えるかを表す書き方。増え方の上界を示すもので、定数倍は含まない。本教材では形式的な定義に立ち入らない。
- 最悪計算量 (worst-case)
- どんな入力でもこれより悪くはならないという上限。C++ 標準ドラフトはハッシュ表のほとんどの操作の最悪は線形だと述べている。
- 平均計算量 (average case)
- 入力の分布に仮定を置いたときの計算量。何を仮定したかを添えないと意味が定まらない。ハッシュ表の平均 O(1) はこちら。
- ならし計算量 (amortized)
- 操作列の合計を操作の回数で割ったもの。C++ 標準ドラフトが amortized constant time という語で使っている。平均とは前提が違う。
- 定数倍
- 計算量が捨てている係数。同じ計算量でも実際の所要時間を大きく変えうる部分で、体感の速さはここに入る。