複数のCIDR形式で記されたネットワークに該当するか、複数の定義された時間帯に現時刻が該当するか、などなどRange検索をしたい事がそれなりにあります。
単純なRange検索であれば、from <= v && v <= toのような単純なコードで判定できますが、Rangeの定義が複数ある場合、愚直に実装するとO(N)になります。それはとても嫌なのでO(log N)で判定できるようにします。全部自前で書いてやろうと思ったのですが、ライブラリに任せることにしました。
Guavaのコードを見ると、追加するたびにRangeをMergeするという方法を取っていました。あるクエリにHitする定義はどれだみたいな事は出来ないのですが、今回は含まれるか(contains)を判定できれば良いので妥協します。
実際のコード その1
ライブラリはデータ構造としてguavaのRangeSet、CIDRの扱いとしてcommons-netのSubnetUtilsを使います。コードの記述を減らすためにLombok、JSONの処理にはgsonを使いました。
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" |
public class App { |
実際のコード その2
Intで扱わない場合です。RangeクラスはComparatorの実装を要求しますがInetAddrクラスは実装していないので、ラッパークラスを作成します。
またCheckerクラスを汎用的に実装し、FunctionクラスによってKeyの変換も定義します。今回はStringからComparableInetAddrに変換する関数を定義します。
|
差分のコードだけ。ComparableIntAddrをRangeクラスに入れるようにした
List<Range<ComparableInetAddr>> ranges = ipRanges.getPrefixes().stream() |
時間の範囲を判定する場合
例えば、1日のうちの10時から12時と14時から16時。とか。1週間のうちの月曜日の午前中と火曜日の午前中とか。前者の場合は0から86400の整数として扱えば良いし、後者は月曜始まりの0時を0とした整数として扱うとかすれば良いと思います。
もしくは上記のコードでComparableが実装されているDate系のクラスを使えば良いと思います。
その他
今回はImmutableRangeSetを使いましたが、他にもTreeRangeSetの実装があります。こっちはInstanceを生成後にRangeを追加することができます。個人的にはIntegerではなくPrimitiveのintで扱いたいです。
RangeがMergeされるのを確認したコード
|
参考
CIDRに限ってしまえばもっと高速にできるみたいです。
