リアルタイムに最大値・最小値を求めたい~Commons Collections vs Esper
私は新横浜に住んでいるのですが、サッカー好きなので、近所に日産スタジアムがあったり、電車で10分以内に三ツ沢球技場の最寄り駅に着く環境は結構便利です。今日も日産スタジアムではマリノスvsアントラーズ戦が行われているのですが、目の前を通り過ぎて行くサポーターを見ながら、こんなブログを書いています。
add,removeするだけで、最大値や最小値を計算してくれるコレクション~まずは自作
皆さんは「add,removeするだけで、最大値や最小値を計算してくれるコレクション」が欲しいと思ったことはありませんか?
Javaの標準APIでSortedXXXを探して見ると、SortedMapやSortedSetはあるのですが、SortedListが無いんですよね。「コレクションに同じ値を複数格納したい」という条件を付けると、MapやSetは使えないので、これでは困ります。
そこで、自作してみました。それが以下のSimpleTreeMapです。
package jp.gr.java_conf.snuffkin.sandbox.treemap; import java.util.TreeMap; public class SimpleTreeMap<T> { /** key=保持する値, value=同一の値の個数 */ private TreeMap<T, Integer> treeMap = new TreeMap<T, Integer>(); public void add(T entry) { Integer value = treeMap.get(entry); if (value == null) { treeMap.put(entry, 1); } else { treeMap.put(entry, value + 1); } } public void remove(T entry) { Integer value = treeMap.get(entry); if (value != null && value == 1) { treeMap.remove(entry); } else if (value != null) { treeMap.put(entry, value - 1); } } }
とっても、素朴に書いてみました。TreeMapを利用して「key=保持する値, value=同一の値の個数」とすることで、複数個の値を持つことができます。まあ、誰でも思いつきそうな実装ですね。
こういうクラスは既に存在するのでは?
でも、こういうクラスは世界中で多くの人が欲しがっているのでは?カジュアルに使うならこれで良いのかもしれないけれど、「秒間数百万イベントを処理する世界で格闘するには、性能を追求したい」とかって欲求を満たすためには、これでは心細いですね。
そこでちょっと探してみると、、、やはり、ありました! 私が見たところ、安心して使えそうなものが2個ありました(他にも良いものがあったらごめんなさい)。
ひとつはApacheから出ているCommons Collections。ここにTreeBagってのがあるじゃないですか。同じ値を複数個保持できるコレクションBagのSortedな実装です。これは使えそうですね。
もうひとつは、OSSのCEPエンジンEsperが最大値・最小値計算に利用しているクラスSortedRefCountedSet。TreeMapをベースにしていて、実装の考え方はSimpleTreeMapとほとんど同じですね。
で、どれが速いの?
とまあ、いつくか選択肢はあるのですが、気になることがありますよね? そう、どれが一番高速なのでしょうか。気になりますね。そこで、以下のプログラムで測定してみました。
package jp.gr.java_conf.snuffkin.sandbox.treemap; import java.util.Random; import org.apache.commons.collections.bag.TreeBag; import com.espertech.esper.collection.SortedRefCountedSet; /** * TreeMapの性能測定クラス。 * * 事前にDATA_SIZE個のデータをコレクションにaddしておく。 * ATTEMPT回のadd,removeを繰り返す。 * add,removeするデータは0からMAX_VALUEまでのintとする。 */ public class TreeMapBenchmarker { /** 事前にコレクションにaddしておくデータの個数 */ private static final int DATA_SIZE = 100; /** add,removeするデータの最大値 */ private static final int MAX_VALUE = 100; /** データのadd,removeを繰り返す回数 */ private static final int ATTEMPT = 100000000; private Random rand = new Random(); /** * 自作のSimpleTreeMapの性能測定 */ public void benchmarkSimpleTreeMap() { System.out.println("SimpleTreeMap"); // SetUp SimpleTreeMap<Integer> collection = new SimpleTreeMap<Integer>(); for (int index = 0; index < DATA_SIZE; index++) { collection.add(rand.nextInt(MAX_VALUE)); } // Exercise long startTime = System.nanoTime(); for (int counter = 1; counter <= ATTEMPT; counter++) { collection.add(rand.nextInt(MAX_VALUE)); collection.remove(rand.nextInt(MAX_VALUE)); // Measure if (counter % 10000000 == 0) { double time = (System.nanoTime() - startTime)/ 1000000000.0; System.out.format("counter=%9d, time(sec)=%12.9f\n", counter, time); } } System.out.println(); } /** * Commons CollectionsのTreeBagの性能測定 */ public void benchmarkTreeBag() { System.out.println("TreeBag"); // SetUp TreeBag collection = new TreeBag(); for (int index = 0; index < DATA_SIZE; index++) { collection.add(rand.nextInt(MAX_VALUE)); } // Exercise long startTime = System.nanoTime(); for (int counter = 1; counter <= ATTEMPT; counter++) { collection.add(rand.nextInt(MAX_VALUE)); collection.remove(rand.nextInt(MAX_VALUE), 1); // Measure if (counter % 10000000 == 0) { double time = (System.nanoTime() - startTime)/ 1000000000.0; System.out.format("counter=%9d, time(sec)=%12.9f\n", counter, time); } } System.out.println(); } /** * EsperのSortedRefCountedSetの性能測定 */ public void benchmarkSrsc() { System.out.println("SortedRefCountedSet"); // SetUp SortedRefCountedSet<Integer> collection = new SortedRefCountedSet<Integer>(); for (int index = 0; index < DATA_SIZE; index++) { collection.add(rand.nextInt(MAX_VALUE)); } // Exercise long startTime = System.nanoTime(); for (int counter = 1; counter <= ATTEMPT; counter++) { collection.add(rand.nextInt(MAX_VALUE)); collection.remove(rand.nextInt(MAX_VALUE)); // Measure if (counter % 10000000 == 0) { double time = (System.nanoTime() - startTime)/ 1000000000.0; System.out.format("counter=%9d, time(sec)=%12.9f\n", counter, time); } } System.out.println(); } public static void main(String... args) { TreeMapBenchmarker benchmarker = new TreeMapBenchmarker(); benchmarker.benchmarkSimpleTreeMap(); benchmarker.benchmarkTreeBag(); benchmarker.benchmarkSrsc(); } }
すると、結果は以下の通りでした。(Core2DuoのMac Book Airで測定したので、最近のマシンならもっと速いです)
SimpleTreeMap counter= 10000000, time(sec)= 4.274583350 counter= 20000000, time(sec)= 8.392179747 counter= 30000000, time(sec)=12.463048036 counter= 40000000, time(sec)=16.720558747 counter= 50000000, time(sec)=20.822315714 counter= 60000000, time(sec)=24.889912523 counter= 70000000, time(sec)=29.055593668 counter= 80000000, time(sec)=33.289640864 counter= 90000000, time(sec)=37.457229133 counter=100000000, time(sec)=41.541354162 TreeBag counter= 10000000, time(sec)= 2.637634968 counter= 20000000, time(sec)= 5.240925183 counter= 30000000, time(sec)= 7.845597939 counter= 40000000, time(sec)=10.425084652 counter= 50000000, time(sec)=13.020404733 counter= 60000000, time(sec)=15.613922938 counter= 70000000, time(sec)=18.194127095 counter= 80000000, time(sec)=20.729887176 counter= 90000000, time(sec)=23.281510931 counter=100000000, time(sec)=25.821683679 SortedRefCountedSet counter= 10000000, time(sec)= 4.430119437 counter= 20000000, time(sec)= 8.851078509 counter= 30000000, time(sec)=13.380416856 counter= 40000000, time(sec)=17.785055448 counter= 50000000, time(sec)=22.205714207 counter= 60000000, time(sec)=26.733082063 counter= 70000000, time(sec)=31.108994779 counter= 80000000, time(sec)=35.716570925 counter= 90000000, time(sec)=40.037819565 counter=100000000, time(sec)=44.373036878
おおっ~、Commons Collectionsがぶっちぎりで最速。私 vs Commons Collections vs Esperは、Commons Collectionsが勝利。
数値的には、Commons CollectionsはSimpleTreeMapより61%速く、SortedRefCountedSetより72%速い、という結果。
Commons Collectionsは「保持している個数をMutableIntegerというクラスで表現していて、個数を更新する際にputしない」とか、高速化の工夫が見られます。こういうのは好きですね。通常の使い方ではあまりやらないことですが、速度を追求する世界だとこういう工夫の積み重ねが大きな差を生みます。
Esperも随所に工夫がみられる良いOSSだと思いますが、(局所的な)このポイントについてはCommons Collectionsに軍配が上がりました。
そうこうしているうちに、日産スタジアムではマリノスが勝ったようです。Twitter等を通じてリアルタイムに情報が伝わるのは、こういう類の技術が裏で支えているからなんですよね。なんとなく、目の前の人波とのつながりを感じました。