RubyistのためのBig-O記法入門 ― 計算量をやさしく理解する

コンピュータサイエンスの学位を持たない開発者は、Rubyコミュニティにもたくさんいます。私もその一人です。そのため長い間、Big-O記法の学習を避けてきました。どう見ても高度な数学にしか見えなかったのです。だって、O(N^2)ですよ。無理だと思いませんか？

そこで私は、代わりにこうした経験則を学んできました。

• 特定の要素を探すなら、ArrayよりもHashの方が速い
• ネストしたループは避ける
• ビューでリストを生成する際、意図しないDBクエリが発生していないか注意する

これらのルールは確かに便利ですが、なぜそれが機能するのかを理解していなければ、ミスをしたり、原因不明のパフォーマンス問題に悩まされたりすることになります。

なぜBig-O記法が重要なのか？

Big-O記法とは、コードのパフォーマンスが処理するデータ量によってどう変化するかを表すための表現方法です。

パフォーマンスには2つの側面があります。速度とメモリ使用量です。コンピュータサイエンスの授業では、それぞれ「時間計算量」「空間計算量」と呼びます。Big-O記法はどちらにも使われますが、この記事ではより一般的な「速度」に焦点を当てて説明します。

100件の配列を処理する方が10件の配列より遅くなるのは当然予想できます。しかし、具体的に何倍遅くなるのでしょうか？10倍？100倍？それとも1000倍？

データセットが小さいうちは大した問題ではありませんが、DBの行が増えるごとにアプリケーションが指数関数的に遅くなるようなら、あっという間に深刻な問題になります。

詳細に入る前に、よく使われるBig-Oの一覧を、データが拡大したときの気分を絵文字で表した早見表としてまとめました。

Big-O	ランク	意味
O(1)	😎	速度がデータセットのサイズに依存しない
O(log n)	😁	データが10倍になると、所要時間は2倍
O(n)	😕	データが10倍になると、所要時間も10倍
O(n log n)	😖	データが10倍になると、所要時間は約20倍
O(n^2)	😫	データが10倍になると、所要時間は100倍
O(2^n)	😱	ダイリシウム結晶が崩壊し始める！（もはや絶望的）

つまり、「Array#bsearchはO(log n)で、Array#findはO(n)だから前者の方が優れている」と誰かが言ったとき、😁と😕を比べるだけで、なるほど一理あるなと判断できるわけです。

もう少し本格的に学びたい方は、Big-O Cheat Sheet（Big-Oチートシート）をチェックしてみてください。

記法の読み解き方

すべてのBig-Oの値を暗記する必要はありません。記法の仕組みさえ理解すれば十分です。

例として、恐ろしく恐ろしいO(2^n)を見てみましょう。これをRubyで表現すると、次のようになります。

# O(2^n) をRubyで表すと
def o(n)
  2 ** n  # Rubyにおける 2^n の書き方
end

まだピンとこないでしょうか？メソッド名と引数をもっと分かりやすい名前に変えてみましょう。

# O(2^n) をより読みやすいRubyで表すと
def execution_time(size_of_dataset)
  2 ** size_of_dataset
end

他の記法も同じように表せます。

# O(1)
def o1_execution_time(size_of_dataset)
  1
end

# O(n)
def on_execution_time(size_of_dataset)
  size_of_dataset
end

# O(n^2)
def on2_execution_time(size_of_dataset)
  size_of_dataset * size_of_dataset
end

# ...などなど

記法の仕組みが分かったところで、典型的なRubyコードがどれに該当するのか見ていきましょう。

O(1)

O(1)ということは、その速度がデータセットのサイズに依存しないということです。

例えば、Hashの参照時間はハッシュのサイズに影響されません。

# 以下はすべて同じ時間で実行される
hash_with_100_items[:a]
hash_with_1000_items[:a]
hash_with_10000_items[:a]

大きなデータセットに対しては配列よりもハッシュの方が速い、と言われる理由はまさにここにあります。

O(n)

一方、Array#findはO(n)です。つまり、Array#findの所要時間は配列の要素数に比例します。要素数100の配列は、要素数1の配列の100倍の時間がかかるのです。

配列をイテレートする多くのコードは、O(n)のパターンに従います。

(0..9).each do |i|
  puts i
end

# 要素数が2倍なので、前の例の半分の速さでしか実行できない
(0..19).each do |i|
  puts i
end

O(n^2)

O(n^2)の特性を持つコードは、ネストしたループを含む傾向があります。考えてみれば当然です。1つのループでO(n)になり、そこに2つ目のネストしたループを加えるとO(n^2)になります。もし――悪魔的な理由で――5段階のネストループを書いてしまえば、それはO(n^5)です。

data = (0..100)
data.each do |d1|
  data.each do |d2|
    puts "#{ d1 }, #{ d2 }"
  end
end

O(n log n)

O(n log n)のコードは、本来O(n^2)になってしまうアルゴリズムの作業量を、賢い工夫で削減した結果であることが多いです。

コードを見ただけでO(n log n)だと判断することはできません。ここから先は高等数学の領域なので、私の出番はここまでです。

しかし、O(n log n)について知っておくことは重要です。一般的なソート・検索アルゴリズムの多くがこの分類に該当するからです。RubyのArray#sortは古くからあるクイックソートアルゴリズムを使用しており、平均的にはO(n log n)、最悪の場合はO(n^2)となります。

クイックソートに馴染みがない方は、分かりやすいデモ動画などで仕組みを確認してみてください。

実践編：データベースとの付き合い方

新しいWebアプリケーションによくある問題の一つが、開発者のマシン上では快適に動くのに、本番環境ではどんどん遅くなるという現象です。

これは、データベースのレコード数が時間とともに増えていく一方で、コードがスケールしない操作――つまりO(n)以上のコストのかかる操作――をDBに要求し続けているために起こります。

例えば、Postgresではcountクエリが常にO(n)になることをご存知でしたか？

# これはDBにUsersテーブルの全行を走査させます
# ...Railsのカウンタキャッシュを使っていない限りは。
Users.count

これはPostgresのexplainコマンドで確認できます。以下では、countクエリの実行プランを取得しています。ご覧の通り、テーブル内の104,791行すべてに対してシーケンシャルスキャン（要するに全行ループ）を実行する予定になっています。

# explain select count(*) from users;
                           QUERY PLAN
-----------------------------------------------------------------
 Aggregate  (cost=6920.89..6920.90 rows=1 width=0)
   ->  Seq Scan on users  (cost=0.00..6660.71 rows=104701 width=0)
(2 rows)

Railsの一般的なイディオムの多くは、データベースを意識的に最適化しない限り、意図しないシーケンシャルスキャンを引き起こす可能性があります。

# これはDBに`products`テーブル全体のソートを要求します
Products.order("price desc").limit(1)

# `hobby`にインデックスがない場合、DBはUsersの各行をループして検索します
User.where(hobby: "fishing")

こちらもexplainコマンドで確認できます。下の例では、テーブル全体に対するソート（おそらくクイックソート）が実行されています。メモリに制約がある場合は、異なる性能特性を持つ別のソートアルゴリズムが選択されることもあります。

# explain select * from users order by nickname desc limit 1;
                               QUERY PLAN
-------------------------------------------------------------------------
 Limit  (cost=7190.07..7190.07 rows=1 width=812)
   ->  Sort  (cost=7190.07..7405.24 rows=104701 width=812)
         Sort Key: nickname
         ->  Seq Scan on users  (cost=0.00..6606.71 rows=104701 width=812)

そして、これらの問題への答えは、もちろんインデックスです。データベースにインデックスを使わせるのは、Rubyで配列の線形探索O(n)の代わりにハッシュ参照O(1)を使うのと同じ発想です。

まとめ

この記事が、Big-O記法の基礎と、それがRuby開発者としてのあなたにどんな影響を与えるかを理解するきっかけになれば幸いです。質問があれば、Twitter（X）の@StarrHorneまでお気軽にどうぞ！