torutkのブログ

ソフトウェア・エンジニアのブログ

java.util.regexとString.substringの性能の違いはどれだけか(続)

java.util.regexとString.substringの性能の違いはどれだけか - torutkの日記の続きです。

短い時間を測定するなら、大量にループして測定して割り算すれば・・・

短い処理時間を測定するために、例えば1万回ループで繰り返し実行し、ループ回数で割り算するという方法も考えられます。

@Test public void 実行時間を測定() {
    long start = System.nanoTime();
    for (int i = 0; i < 10000; i++) {
        timestamp.parse("2011-12-11 01:08:14");
    }
    long stop = System.nanoTime();
    System.out.printf("parse: %d [ns]%n", (stop - start)/10000);
}

CPUは命令キャッシュ・データキャッシュを豊富に持つので、マイクロベンチマークのように非常に短い命令コード・データ(せいぜい数KB内)はすべて1次キャッシュ上に乗った状態で動作可能であり、これを測定してしまうと実際とはかけ離れた値になるのではないかと思います。

統計処理について

昨日の日記で参照しているIBM developerWorksの記事によると、2つのタスクの処理速度の優劣を比べるには、それぞれの平均値が3シグマ以上離れていることを確認すればよいそうです。

そこで、昨日の正規表現 V.S. 部分文字列の実行時間について標準偏差(シグマ)を取るため、事前に「暖気運転」を1500回、n=100(100回繰り返し)測定しました。

アルゴリズム 平均値(ns) 標準偏差(σ)
正規表現 2840 5058 15174
substring 1808 3717 11151

両者の平均は3シグマどころか1シグマ以内に存在します。統計的にはこれだけでは優劣がつきません。

次に、信頼区間を求めてみることにします。(t分布)

アルゴリズム 平均値(ns) 95%の信頼区間
正規表現 2840 [1836, 3844]
substring 1808 [1071, 2546]

ここから先の解釈は、統計学をちゃんと理解していないので自信がないですが、信頼区間が重なりあっているので、測定した実行時間の平均値(標本平均)が正規表現よりsubstringの方が優れているからといっても統計的には母平均も正規表現よりsubstringの方が優れているとは言えない、と解釈できるように思います。

Javaで統計処理をするライブラリ

平均、最大、最小、分散、標準偏差までは、それほど時間をかけずにそれぞれ数行で実装することができますが、信頼区間を求めるとなると、一筋縄ではいきません。
統計処理ライブラリがないかと探してみると、apache commons math を見つけました。

数学全般に関するライブラリですが、この中に統計処理パッケージが含まれています。
平均、分散、標準偏差などを算出するのに

  • org.apache.commons.math.stat.descriptive.SummaryStatistics

t分布による信頼区間を算出するのに

  • org.apache.commons.math.distribution.TDistribution

を使いました。

これらのクラスについて解説しているブログがありました。

Apache commons mathのインストール

本日時点では、Ver.2.2が最新です。ダウンロード後適当なディレクトリに展開します。
クラスライブラリのJARファイル、ソースファイルのJARファイル、JavadocファイルのJARファイルの3つが含まれています。クラスライブラリのJARファイルにクラスパスを通してコンパイル・実行します。

実行時間測定のコード例

まず、測定区間です。

@Test public void 暖気運転後実行時間を測定() {
    for (int i=0; i<1500; i++)
        timestamp.parse("2011-12-11 01:55");
    SummaryStatistics statistics = new SummaryStatistics();
    long start = System.nanoTime();
    timestamp.parse("2011-12-11 01:08:14");
    long stop = System.nanoTime();
    statistics.addValue(stop - start);
}

測定後、結果を出すコード例です。

System.out.printf("標本数:%d,最小:%f,最大:%f,平均:%f,標準偏差:%f%n",
    statistics.getN(), statistics.getMin(), statistics.getMax(),
    statistics.getMean(), statistics.getStandardDeviation());