snuffkinの遊び場

IT関係、スポーツ、数学等に関することを、気が向いたときに書いてます。

リアルタイムに最大値・最小値を求めたい~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等を通じてリアルタイムに情報が伝わるのは、こういう類の技術が裏で支えているからなんですよね。なんとなく、目の前の人波とのつながりを感じました。