何万回、何百万回と範囲検索を行う必要がある場合、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と国をひもづけるための
範囲検索を、大量に高速に行う場合などに、大幅な速度向上が出来ることがあります。

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

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

実装

使い方

用途