AMG Solution

Javaのオブジェクトを探せ!基本アルゴリズムの二分探索で高速化しよう。

こんにちは。ぐっさんです。

ORマッピングがデータベースアクセスの主流となってきた昨今ですが、大量データを取得し、その中から対象のオブジェクトを抽出するということが増えてきたと思います。

データが増えれば増えるほど、抽出ロジックがボトルネックになってきます。
二分探索は、データが増えれば増えるほど効果が表れてきます。

二分探索
ソート済みのリストや配列に入ったデータ(同一の値はないものとする)に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。

 wikipedia「二分探索」

そこで、二分探索と通常の抽出の時間を比較したサンプルを作ってみました。

二分探索と通常の抽出の比較サンプル

1000万件のデータリストの中から、ランダムで選択されたIDのオブジェクトを抽出するサンプルです。

実行結果は、下記の通りです。

Target : 7706200
=========== NORMAL SEARCH ===========
Result ID : 7706200
Result Label : label7706200
Time : 7706200
Time : 64ms
=========== BINARY SEARCH ===========
Result ID : 7706200
Result Label : label7706200
Time : 0ms

おお!実行時間が全然違いますね。
通常の探索だと64msかかっているところが、二分探索だと0msです。

サンプルの50行目から67行目が実際の二分探索のロジックになります。
idの値が、中間インデックスのデータと比較して、リストの前後のどちらにあるか判定します。
その判定をもとに、開始インデックスもしくは終了インデックスを調整することがポイントです。
また、二部探索を使う場合は、ソートしている必要があるので注意が必要です。

まとめ

基本アルゴリズムの二分探索ですが、いろいろな抽出に応用できます。
大量データを扱う際には、是非試してみてください。

YAMAGUCHI'S BLOG

山口博史の記事

山口博史の記事の最新情報をお届けいたします。

SAME CATEGORY BLOG

この記事と同様のカテゴリー記事

新卒採用
はじめました。
LOADING