Javaで二分探索法を使って高速に範囲検索を行う

何万回、何百万回と範囲検索を行う必要がある場合、DBを使って検索を行うと、遅すぎて話にならないことがあります。
そんな時は、二分探索法というやり型を実装すると、大幅な速度アップが見込める場合があります。

そんな二分探索法をJavaで実装してみました。

一応Githubにもコミットしてあります。
https://github.com/2KB/range-search/tree/master/range-search

参考にさせて頂いたサイト：
http://blog.akagi.jp/archives/179.html
https://www.grapecity.com/tools/support/powernews/column/clang/054/page03.htm

#実装

範囲データ保持クラスのインターフェース

RangeSearchInterface.java

/**
 * 範囲検索をするためのメソッドを定義したインターフェース
 */
public interface RangeSearchInterface {

	/**
	 * From値を取得
	 * @return
	 */
	abstract long getFromValue();
	
	/**
	 * To値を取得
	 * @return
	 */
	abstract long getToValue();
}

二分探索部分

RangeSearchUtil.java

/**
 * 二分探索法を使って範囲検索してマッチした値を取得する
 */
public T getVal(long searchVal) {

	// 検索中の最小Index
	int lowid  = 0;
	
	// 検索中の最大Index
	int highid = rangeSearchList.size() - 1;
	
	// 検索中の最小indexの値が、最大indexの値以下である間は繰り返す
	while(lowid <= highid){

		// 中間Index
		int midid = (lowid + highid) / 2;
		
		// 中間の値を取得
		T midResult = rangeSearchList.get(midid);
		long midFromVal = midResult.getFromValue();
		long midToVal = midResult.getToValue();
		
		if(midFromVal <= searchVal && searchVal <= midToVal){
			// 取得した中間値が検索値内だったら、取得した値を返す
			return midResult;
		}else if(midToVal < searchVal){
			// 取得した中間値の上限値が検索値より小さかった場合は、最小Indexを今回の中間Indexより大きくする
			lowid = midid + 1;
		}else{
			// 取得した中間値の上限値が検索値より大きかった場合は、最大Indexを今回の中間Indexより小さくする
			highid = midid - 1;
		}
	}

	// 検索範囲内には含まれなかった場合
	return null;
}

#使い方

• RangeSearchInterfaceをimplementしたクラスを用意します。

RangeSearchTestDto.java

public class RangeSearchTestDto implements RangeSearchInterface{
	@Override
	public long getFromValue() {
		return fromVal;
	}

	/**
	 * To値を取得
	 */
	@Override
	public long getToValue() {
		return toVal;
	}

• そのクラスに範囲データを設定してリストにします。範囲データは値の昇順にします。

List<RangeSearchTestDto> rangeList = new ArrayList<RangeSearchTestDto>();
rangeList.add(new RangeSearchTestDto(100, 199));
rangeList.add(new RangeSearchTestDto(200, 299));
rangeList.add(new RangeSearchTestDto(300, 499));

• 範囲データをコンストラクタにわたし、RangeSearchUtilのインスタンスを生成します。

RangeSearchUtil<RangeSearchTestDto> rangeSearchUtil = new RangeSearchUtil<RangeSearchTestDto>(rangeList);

• 生成したインスタンスに検索したい値を渡し、検索値を取得します。

RangeSearchTestDto result = rangeSearchUtil.getVal(100);

実行例

RangeSearchMain.java

// 範囲データ取得
List<RangeSearchTestDto> rangeList = getRangeListOrderByFromVal();
// 範囲データを元に、範囲検索Utilを作成
RangeSearchUtil<RangeSearchTestDto> rangeSearchUtil = new RangeSearchUtil<RangeSearchTestDto>(rangeList);

// 範囲検索実行
{
	long searchVal = 100;
	// 範囲検索Utilを使って範囲検索実行
	RangeSearchTestDto result = rangeSearchUtil.getVal(searchVal);
	System.out.println("searchVal : " + searchVal + " resultfrom : " + result.fromVal + " resultTo : " + result.toVal);
}
{
	long searchVal = 201;
	RangeSearchTestDto result = rangeSearchUtil.getVal(searchVal);
	System.out.println("searchVal : " + searchVal + " resultfrom : " + result.fromVal + " resultTo : " + result.toVal);
}

出力結果

searchVal : 100 resultfrom : 100 resultTo : 199
searchVal : 201 resultfrom : 200 resultTo : 299
searchVal : 1999 resultfrom : 1000 resultTo : 1999
searchVal : 3500 resultfrom : 3000 resultTo : 3990
searchVal : 2000 Not found.
searchVal : 9999 Not found.

#用途
最初の参考リンクにもありましたが、大量のアクセスログデータに対し、大量のIPから国を引いたりするときなどに便利です。

IPの範囲と国のマッピングデータを作っておき、そのマッピングデータから、アクセス元IPと国をひもづけるための
範囲検索を、大量に高速に行う場合などに、大幅な速度向上が出来ることがあります。

そんな人は少ないと思いますが、大量の範囲検索がある処理で、パフォーマンスに困っている人は参考にしてみてください。