アルゴリズムの教科書、実は半分ウソ？
大学でコンピューターサイエンスを学ぶと、まあ、最初に叩き込まれるのが「ビッグオー記法」だよね。マージソートはO(n log n)で、二分探索はO(log n)。そしてバブルソートはO(n²)だから絶対使うな、とか。僕もそう覚えてた。
でも、実際にコードを書いて、パフォーマンスチューニングとかやってると、「あれ？」ってなることが結構ある。理論上はこっちが速いはずなのに、なぜか実行すると逆の結果が出たりする。正直、ビッグオー記法だけ見てると、現実のパフォーマンスの半分も見えてないんだよね。
なんでかっていうと、今のCPUってめちゃくちゃ賢くて、そして複雑だから。メモリの階層構造とか、命令の先読み（パイプライン）、分岐予測、並列処理…こういうハードウェア側の事情が、実際の速度にすごく影響してくる。今日はその「理論と現実のギャップ」について、ちょっとメモがてらまとめてみたい。
【衝撃】理論が負ける瞬間：いくつかの実例
百聞は一見に如かず、だよね。まずは、常識がひっくり返るいくつかのケースを見ていこう。
ケース1：線形探索 vs. 二分探索
これ、一番わかりやすい例。理論上の計算量はこう。
- 線形探索:
O(n) - 二分探索:
O(log n)
データが大きくなればなるほど、二分探索が圧勝するはず。でも、実際に小さい配列で試すと…あれ？
例えば、整数の配列で試すと、要素が10個とかだと、なんと線形探索のほうが速い。マジで。データが50個とか70個くらいになって、やっと二分探索が有利になってくる感じ。
これ、なんでかっていうと、CPUの気持ちになって考えればわかる。線形探索って、やってることは超単純で、メモリの先頭から順番に見ていくだけ。これがCPUにとっては「予測しやすくて」すごく都合がいいんだよね。分岐予測が当たりまくるし、キャッシュにも乗りやすい。逆に二分探索は、次はあっち、その次はこっちってメモリ上を飛び回るから、小さいデータだとその準備運動のコストのほうが高くついちゃう。
ケース2：挿入ソート vs. クイックソート
これも面白い。ソートアルゴリズムの代表格。
- 挿入ソート:
O(n²) - クイックソート: 平均
O(n log n)
クイックソート、名前からして速そうなのに、これも小さい配列（例えば要素が100個未満とか）だと、あのO(n²)のはずの挿入ソートに負ける。
これもさっきと理由が似てて、挿入ソートの単純な構造が、CPUの命令パイプラインとかに優しいから。ほとんどソート済みのデータに対しては爆速だったりもするしね。
ちなみに、この事実はプロの世界では常識で、多くの言語の標準ライブラリのソート関数（例えばC++のstd::sortとか）は、実は単一のアルゴリズムじゃない。大きい範囲はクイックソートで分割して、ある程度小さくなったら挿入ソートに切り替える、みたいなハイブリッドなソートになってることが多い。賢いよね。
じゃあ、何が本当の速度を決めてるの？
ビッグオー記法が絶対じゃないなら、一体何がパフォーマンスを左右してるのか。いくつかキーワードを挙げてみる。
メモリ階層（Memory Hierarchy）
これが一番大きいかも。現代のコンピュータのメモリは、一様じゃない。CPUのすぐ近くにいる超高速だけど容量が小さい「キャッシュメモリ」と、遠くにいる低速だけど大容量の「メインメモリ（RAM）」みたいに、階層構造になってる。
CPUから見ると、アクセスの速さはこんなイメージ。
- CPUレジスタ（机の上）: 瞬殺
- L1/L2キャッシュ（引き出し）: 超速い
- L3キャッシュ（部屋の棚）: まあまあ速い
- メインメモリ（RAM）（隣の部屋）: ちょっと待つ
- SSD（倉庫）: かなり待つ
アルゴリズムが、この「引き出し」や「部屋の棚」にうまく収まるデータだけで作業できるなら、たとえ計算回数が多くても速い。逆に、毎回「倉庫」までデータを取りに行くようなアルゴリズムは、計算回数が少なくても遅くなる。これが「キャッシュ効率」ってやつ。
分岐予測とパイプライン処理
今のCPUは、次に実行する命令を「予測」して、先回りして準備を始める（パイプライン処理）。この予測が当たれば超高速で処理が進むんだけど、外れると「あ、違った！」ってなって、準備したものを全部捨ててやり直すペナルティが発生する。
さっきの線形探索が速かったのは、単純なループだから「次はループのこの処理でしょ」って予測がほぼ100%当たるから。逆に、if文が複雑に絡み合うコードは予測が外れやすくて、思ったより速度が出ないことがある。
SIMD（単一命令複数データ）
「Single Instruction, Multiple Data」の略。要するに、1つの命令で、複数のデータを一気に処理する機能。例えば、「4つの数値をそれぞれ足し算する」んじゃなくて、「4つの数値が入ったパックに、一気に足し算ビームを当てる」みたいなイメージ。これが使えるとめちゃくちゃ速くなる。
単純な配列の合計値を計算する、みたいなコードは、最近のコンパイラが自動でこのSIMD命令に変換してくれたりする。逆に、ループの中にif文があったりすると、この自動ベクトル化が効かなくなって遅くなる原因になったりもする。
並列処理
もうこれは言うまでもないけど、今のCPUはマルチコアが当たり前。ビッグオー記法は基本的にシングルコアで動く前提の計算だから、並列化できるかどうかは全く考慮されてない。たとえO(n)のアルゴリズムでも、32コアで並列処理できれば、並列化できないO(log n)のアルゴリズムより現実の時間ではずっと速い、なんてこともザラにある。
じゃあ、どう使い分ければいいの？
「じゃあビッグオー記法はもういらないの？」って言うと、そんなことはない。あくまで「大きな地図」として、アルゴリズムの大まかな性質を理解するためには必須。その上で、ハードウェアの特性を考慮に入れるのが大事ってこと。
個人的な感覚だと、こんな感じで使い分けを考えることが多いかな。
| 入力サイズ (n) | 選ぶべきアルゴリズムの傾向 | 理由とか具体例 |
|---|---|---|
| ～数十件 | 「え、これでいいの？」ってくらい単純なやつ。 | アルゴリズムの複雑さより、命令の単純さや分岐の少なさが効く。線形探索とか挿入ソートが輝く場面。下手に凝ったことしない。 |
| 数百～数万件 | 教科書通りの効率的なアルゴリズム。 | この辺からビッグオー記法がちゃんと意味を持ち始める。クイックソートとかヒープソートとか、定番どころが安定して強い。 |
| 数十万～数百万件 | キャッシュ効率を意識した実装。 | 計算量も大事だけど、いかにメモリへのアクセスを減らすかが勝負。同じO(n³)でも、行列積の計算順序を変えるだけで何倍も速くなったりする領域。 |
| 一千万件～ | 並列化できるアルゴリズムが正義。 | もうシングルコアでどうこうするレベルじゃない。いかに処理を分割して、たくさんのコアに仕事をばらまけるかが全て。MapReduce的な考え方が必要になる。 |
でも、いきなり最適化は危険
ここまで色々話してきたけど、一番大事なのは「推測するな、計測せよ」ってこと。本当に。
「ここは小さい配列だから挿入ソートのほうが速いはず…」とか頭で考える前に、まずプロファイラを回して、プログラムのどこが本当にボトルネックになってるかを確認するのが先。だいたいの場合は、全然予想してなかった場所が遅かったりするからね。
日本の技術ブログ、例えばQiitaの記事とかでも、この「std::sortの中身」を解説してるのよく見るよね。あれは、多くのC++プログラマが興味を持つくらい、ライブラリレベルで最適化が作り込まれている良い例。一方で、海外だと、例えばAgner Fogのマニュアルみたいな超ディープなCPU最適化ガイドでも、こういうハードウェアの挙動は定番のトピック。つまり、世界中のローレベルを意識するエンジニアにとって共通の課題なんだよね。
まとめ：理論と現実の付き合い方
結局、ビッグオー記法は「天文学的なスケールで見たときの成長率」を示してるに過ぎない。すごく大きな地図みたいなもので、大まかな方向性を知るには絶対に必要。でも、実際に道を歩くときには、目の前の道の舗装状況（キャッシュ効率）とか、信号のタイミング（分岐予測）とか、車線の数（並列化）が大事になってくる。
だから、僕らの仕事は、大きな地図で方向性を確認しつつ、実際の道路状況に合わせて最適な乗り物を選ぶ、みたいな感じかな。理論だけ、あるいは目の前の現実だけじゃなくて、両方を見ることが、本当に速いコードを書くための鍵なんだと思う。
あなたが普段書くコードで、この「理論と現実のギャップ」を感じたことありますか？もし面白い例があったら、ぜひ教えてほしいな。
