0. はじめに

私は普段プラットフォームチームで開発を行なっており、比較的大量のデータを扱うことがあります。
その際、以下のような問題に直面することがあります。

「特定の処理だけが異常に遅く、なぜか時間がかかってしまう」
「データが少ないときは問題ないが、データ量が増えると急に動作が重くなる」

こうしたパフォーマンス問題は「指数的な爆発」による可能性があります。指数的な爆発とは、処理にかかる時間がデータサイズに対して急激に増大する現象です。本記事では、Rubyでの指数的な爆発を防ぐための基本概念から実践的なテクニックまでを解説します。

ちなみに「指数的な爆発」や計算量についての解説は以下の書籍を参考にさせていただきました。

1. 計算量って何？ - プログラムの効率を見極める目安

「計算量」とは、アルゴリズムがデータを処理するのに必要な時間やメモリの量を示す指標です。計算量を考慮しないコードは、データが増えると急激に遅くなり、結果的にシステム全体のボトルネックとなります。

計算量の種類とその特徴

計算量	特徴	例
(O(1))	データサイズに依存せず、一定時間で終了	配列の特定のインデックスにアクセス
(O(n))	データサイズに比例して処理時間が増える	配列全体のループ処理
(O(n^2))	データサイズに比例して二乗の時間が必要	2重ループ処理
(O(2^n))	入力サイズが増えるたびに処理時間が倍々に増える	再帰的な組み合わせ処理

具体例: フィボナッチ数列の計算時間

以下は、データサイズ (n) と処理時間の関係を示す表です（相対値）。

(n)	(O(n))	(O(n^2))	(O(2^n))
10	10	100	1,024
20	20	400	1,048,576
30	30	900	約10億

指数的な爆発が発生するコードでは、データが少し増えただけで処理時間が急激に増加します。

2. 再帰処理の落とし穴を理解しよう - フィボナッチ数列の例

指数的な爆発の典型例として、フィボナッチ数列を再帰で計算するコードを見てみましょう。

def fibonacci(n)
  return n if n <= 1
  fibonacci(n - 1) + fibonacci(n - 2)
end

puts fibonacci(35) # 35を計算するのに非常に時間がかかる

このコードでは、再帰呼び出しのたびに同じ計算が何度も繰り返されます。計算量は (O(2^n)) で、fibonacci(35) を計算するのに数秒、fibonacci(50) では数分かかる場合があります。

3. メモ化で効率化しよう - 再利用可能な計算結果を保存

再帰処理を高速化するための基本的な手法が「メモ化」です。メモ化では、一度計算した結果を保存して再利用します。

def fibonacci(n, memo = {})
  return n if n <= 1
  memo[n] ||= fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
end

puts fibonacci(35) # 劇的に高速化される

このコードでは、memo ハッシュに計算済みの結果を保存します。同じ計算を繰り返さないため、計算量が (O(n)) に改善されます。

実行時間の比較

require 'benchmark'

Benchmark.bm do |x|
  x.report("Without Memoization:") { fibonacci(35) }
  x.report("With Memoization:") { fibonacci(35, {}) }
end

結果例:

Without Memoization: 11.231089 sec
With Memoization:    0.001251 sec

4. ネストループを効率化しよう - ハッシュを活用

非効率なコード例: 2重ループでペアを探す

data = [10, 15, 3, 7]
target_sum = 17

data.each do |i|
  data.each do |j|
    if i + j == target_sum
      puts "#{i} + #{j} = #{target_sum}"
    end
  end
end

このコードは (O(n^2)) の計算量で、データ量が増えると処理速度が著しく低下します。

効率化: ハッシュを使ったルックアップ

def find_pairs(data, target_sum)
  seen = {}
  pairs = []

  data.each do |num|
    complement = target_sum - num
    pairs << [complement, num] if seen[complement]
    seen[num] = true
  end

  pairs
end

# 実行例
data = [10, 15, 3, 7]
target_sum = 17
puts find_pairs(data, target_sum).inspect

このコードの計算量は (O(n)) に改善され、大規模データでも効率的に動作します。

5. パフォーマンス測定で改善効果を確認しよう

RubyのBenchmarkモジュールを使って、改善前後の処理時間を確認できます

実行例

require 'benchmark'

def find_pairs(data, target_sum)
  seen = {}
  pairs = []

  data.each do |num|
    complement = target_sum - num
    pairs << [complement, num] if seen[complement]
    seen[num] = true
  end

  pairs
end

def nested_pair_search(data, target_sum)
  pairs = []

  data.each do |i|
    data.each do |j|
      pairs << [i, j] if i + j == target_sum
    end
  end

  pairs
end

data = [10, 15, 3, 7]
target_sum = 17

Benchmark.bm do |x|
  x.report("Nested Loop:") { nested_pair_search(data, target_sum) }
  x.report("Optimized Hash Search:") { find_pairs(data, target_sum) }
end

結果例:

6. まとめ

この記事では、Rubyで「指数的な爆発」を防ぐ方法を解説しました。
アルゴリズムによってはデータ量が多くなるにつれてパフォーマンスが著しく悪化してしまいます。
その際は内部でどのような計算が行われているか確認してみてください。