計算量最適化でバッチ処理時間を90%改善した話

sonoha / 2022.10.28

こんにちは。システム開発部のsonohaです。ニフティ温泉のWEBサイトの開発全般を担当しています。

先日、ニフティ温泉で使用しているバッチの処理速度を改善しました。
データ構造やシステム構成、マシンスペックなどは変更せずに、計算量が小さくなるようなアルゴリズムに変更しただけで最大90%以上も処理時間を短縮できました。次に示すのは改善された処理速度の一例です。

	データ数	改善前の処理時間	改善後の処理時間
処理A	約35万×約35万の組み合わせ	300分以上	約6分
処理B	約35万×約35万の組み合わせ	約300分	約40分
処理C	約15万×約15万の組み合わせ	約180分	約33分
処理D	約15万×約15万の組み合わせ	約180分	約32分

今回はこれを実現した、時間計算量に関するアルゴリズム改善についてご紹介していきます。

時間計算量（Time complexity）とは

プログラムが行う処理（挿入、取得、計算、比較、削除、など）の回数やステップ数のことを時間計算量（Time complexity）と呼びます。一般に、使用しているアルゴリズムの時間計算量が大きいほど、全体の処理時間も大きくなります。

時間計算量は、処理対象の要素数に応じて変化することがほとんどです。次に具体例を挙げます。

1から10までの数が入った配列の中から偶数を取り出そうとして、次のような処理を記述しました。（言語はRubyです。）

[1,2,3,4,5,6,7,8,9,10].select { |n| n % 2 == 0 }

この処理は全ての要素をチェックしていくので、時間計算量は要素数10に比例します。もしこれが1から100までの数を含む配列になったとしたら、要素数が10倍になるため時間計算量も10倍に膨らみます。

要素数に応じた時間計算量の規模感を表す方法として、しばしばオーダー記法（ランダウ記法）が用いられます。
先の例では、要素数nに比例した時間計算量をもつため、これはオーダー記法でO(n)と表します。もしn²に比例した時間計算量を持つならばO(n²)と表します。

時間計算量がO(n²)やO(2ⁿ)の場合は、要素数が大きくなった際に計算量が爆発的に増えます(上記グラフの左から2番目の曲線)。その際、トータルの処理時間も非常に大きくなることが予想されます。
処理対象の要素数が大きくなる場合には上手くアルゴリズムを組み、いかに時間計算量を抑えるかが重要となってきます。

時間計算量を減らすには

ニフティ温泉で取り組んだ今回のバッチ改修と似たケースを想定して、時間計算量の削減を考えてみましょう。

課題設定

本の情報を持つBookオブジェクトと、帯の情報を持つBandオブジェクトが存在するとします。データの構造は以下のようなイメージです。

Book: {
  id: 1234,
  isbn_code: 'ISBNnnn-x-aaaa-bbbb-c',
  title: 'example book',
  author: 'ontama-chan',
  ...
}

Band: {
  id: 5678,
  book_id: 1234,
  color: 'blue',
  text: 'Discover more than you can imagine!',
  ...
}

BookとBandは1対1対応ですが、Bookに対してBandが存在しないこともあります。

いま、「すべての本を含んだ配列」と「青色の帯のみを含んだ配列」が存在します。
これらは何らかの事情により事前にJOINすることはできず、別々の配列として宣言されています。

all_books_array = [book1, book2, book3, ...]
print (all_books_array.size >= 1000000) # true

blue_bands_array = [band1, band2, band3, ...]
print (blue_bands_array.size >= 500000) && (blue_bands_array.size < 1000000) # true

これらを使って「青色の帯を持つ本のIDとタイトルの一覧を生成したい」とします。
既存のコードでは次のような処理が書かれていました。

# 結果格納用の配列
result_array = []

# すべての本をループ
all_books_array.each { |book|
  # すべての青い帯をループ
  blue_bands_array.each { |band|
    # IDが合致したら「青色の帯を持つ本」なので、本のIDとタイトルを配列に格納
    if (book.id == band.book_id) {
      result_array << [book.id, book.title]
    }
  }
}

# 結果を出力
print result_array # [[1234, 'example book'], ...]

配列の二重ループになっているので、こちらの時間計算量はO(n²)です。

バッチのリリース当初はデータ数が少なくて問題なかったこの処理も、その後データが増えたことにより非常に時間がかかるようになってしまいました。
この計算量を削減し、処理を高速化することを考えます。

次の方法を試してみましょう。

ループの順番を変えてみる
continueを追加する
ハッシュテーブルを活用する

× ループの順序を変えてみる

all_books_arrayはblue_bands_arrayよりも大きいので、all_books_arrayのループが外側にあることでなんとなく計算量が多くなっている気がします。試しにループの順番を変えてみましょう。

# 帯のループの中で
blue_bands_array.each { |band|
  # 本のループを回してみる
  all_books_array.each { |book|
    if (book.id == band.book_id) {
      result_array << [book.id, book.title]
    }
  }
}

結論から言うと、これでは計算量は何も変わりません。

縦×横を横×縦に変えただけのようなものなので、依然、時間計算量はO(n²)のままです。

△ continueを追加してみる

次に思いつくのは、途中でループを切り上げることです。
今回はBookとBandが1対1対応なので、Bookに対応するBandを見つけてしまえばそれ以降のBandを探索する必要はありません。

Rubyではcontinueにあたる構文はnextなので、追記してみます。

all_books_array.each { |book|
  blue_bands_array.each { |band|
    if (book.id == band.book_id) {
      result_array << [book.id, book.title]
      next # 該当の本を見つけたので、内側のループを抜ける
    }
  }
}

1行足しただけですが、これで処理の回数はおよそ半分になることが予想されます。

しかし、まだ二重ループが存在するので時間計算量のオーダーは変わらずO(n²)のままとなります。
実際の処理時間においてはある程度改善することが見込めますが、データ量の増加に伴って処理時間が大幅に増える状況は変わらず、劇的な処理時間の改善は見込めません。

○ ハッシュテーブルを活用してみる

さて、ここからが本題です。時間計算量のオーダーを小さくするには、二重ループを解消するほかありません。そこで活躍するのがハッシュテーブルです。

ここではハッシュテーブルの詳しい解説は省きますが、重要なのは次の点です。
配列の探索（ある要素が存在するか）の時間計算量はO(n)であるのに対し、ハッシュテーブルの探索の時間計算量はO(1)、すなわち要素数によらず一定値となるように設計されています。
この性質をうまく利用することで、二重ループを解消して時間計算量のオーダーを下げることができます。

Rubyにおいては、HashまたはSetでハッシュテーブルを利用することができます。
Hashを用いて二重ループを解消すると次のようになります。

# すべての本の配列から必要な情報を抜き出し、Hashを生成
all_books_hash = all_books_array.to_h { |book| [book.id, book.title] } # O(n)

# すべての青い帯をループ
blue_bands_array.each { |band| # O(n)
  # Hashに該当のIDが存在したら「青色の帯を持つ本」なので、本のIDとタイトルを配列に格納
  if (all_books_hash.include(band.book_id)) { # O(1)
    result_array << [band.book_id, all_books_hash[band.book_id]]
  }
}

Hashが特定のキーを含むかの探索include(key)の時間計算量がO(1)であることによって、それをラップしているblue_bands_arrayのループ全体の時間計算量はO(n)で済みます。

また、Setを用いて二重ループを解消すると次のようになります。

# すべての青い帯の配列から必要な情報を抜き出し、Setを生成
blue_bands_set = blue_bands_array.to_set { |band| band.book_id } # O(n)

# すべての本をループ
all_books_array.each { |book| # O(n)
  # Setに該当のIDが存在したら「青色の帯を持つ本」なので、本のIDとタイトルを配列に格納
  if (blue_bands_set.include(book.id)) { # O(1)
    result_array << [book.id, book.title]
  }
}

同様に、Setが特定の要素を含むかの探索include(key)の時間計算量がO(1)であることによって、それをラップしているall_books_arrayのループ全体の時間計算量はO(n)で済みます。

ハッシュテーブルを用いて二重ループをループ2つに分解することで、時間計算量のオーダーをO(n²)からO(n)に下げることに成功しました。

実際のニフティ温泉のバッチ処理については、この方法により、300分以上かかっていた処理が10分以内に収まるようになりました。

様々なデータ構造を用いた場合の時間計算量

先の例ではRubyを用いて説明しましたが、時間計算量はプログラミング言語によらないアルゴリズムの話です。
データの構造とそれに対する操作の組み合わせで、一般的な時間計算量のオーダーがある程度決まっています。

Big-O Cheat Sheetでは、データ構造と操作の組み合わせによってどんな時間計算量を得るか、有志のメンバーによって作成されたチートシートを確認できます。

このチートシートにはビッグ・オーOによるオーダー記法だけでなく、ビッグ・シータΘやビッグ・オメガΩによるオーダー記法も登場します。ビッグ・オーは上限を、ビッグ・オメガは下限を、ビッグ・シータは下限と上限の両方を表現するものですが、実務においてはその違いはさほど重要ではありません。

おおよその時間計算量のオーダーを知っておくことで、プログラムのパフォーマンスチューニング等に役立てることができます。

空間計算量に関する注意事項

今回は時間計算量（Time complexity）に注目して説明していきましたが、同じくパフォーマンス向上に重要な概念として空間計算量（Space complexity）があります。

空間計算量とは、プログラムが処理を実行するにあたって必要なリソース（メモリ、CPU、ディスクなど）のことを指します。

時間計算量を小さくしようとすると、逆に空間計算量が増えてしまうことがあります。
例えば、データの並べ替えに関して、マージソートは要素数が増えても時間計算量のオーダーが小さい優秀なソート方法ですが、シンプルなバブルソートに比べるとメモリの消費が大きいです。

パフォーマンスチューニングのために時間計算量を減らすようなアルゴリズム変更を行う際は、空間計算量が急増していないか必ずリソース状況やマシンスペックをチェックしましょう。
メモリやCPUが不足してしまい思ったほどパフォーマンスが改善しなかったり、オーバーフローでサービスが落ちるような思わぬ事故が発生したりすることを未然に防ぐことができます。

まとめ

ニフティ温泉では、あるバッチ処理の中に存在していた大きな配列の二重ループ処理について、ハッシュテーブルを用いて二重ループを解消し時間計算量を小さくすることで、最大90%以上のパフォーマンス改善に成功しました。

計算量については基本情報技術者試験にも出てくるような内容ではありますが、その知識を実際に実務で活かしてこそ真価が発揮されると考えます。

今後もパフォーマンスを意識した実装やレビューを行い、皆さまに便利なサービスをお届けできるよう努めてまいりますので、どうぞご期待ください！

最後までお読みいただきありがとうございました！

掲載内容は、記事執筆時点の情報をもとにしています。