[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[jfriends] Javaベンチマーク

ベンチマークを行なった時の結果です。

当時、雑誌とかを見ると、JavaはCに比べてだいたい15〜20倍ぐら
い遅い、となっていたので、本当かなあ、と思い試してみたのでした。

今なら、JITとかもありますし、また違う結果になると思いますが...

# 誰か計測してみませんか?

問題は以下の通りです。

「ビリヤードの玉(1〜15)を5個ネックレスのように輪にして繋ぐ。
  そこから隣同士連続したものならいくつ取っても良いとして、取っ
  た玉の数字の合計で 1〜21までの数ができるようにするためには、
  何番の玉をどのように繋げばよいか？」

# 某推理小説に出ていた問題です (^^;

この問題を力技で解くとすると(もちろんよりエレガントで、人力
で解ける方法があるのですが)、

・15個の玉から5個の玉を取り出すので、その順列のパターンは

  15! / (15 - 5)! = 360360

・その中から連続する玉を取り出す組合せは、開始点が5通りで玉
  の数が1〜5の 25通り。

これを掛け算したパターンだけ検証すれば良いことになります。ネッ
クレスなので循環と裏返しを省けば 1/10 になりますけど、今回そ
れは考えてません(よって解は10個出る)。

計測結果

1) Cの場合(-Oオプション付き)

3.0u 0.0s 0:08 33% 0+0k 0+0io 0pf+0w

2) Java ヒープ動的使用時(-Oオプション付き)

ひとつの順列の作成終了後、連続する玉を取り出すための配列(要
素数5)が必要ですが、それを毎回(360360回)ヒープにとる方式。
Javaのプログラミングでは、通常こちらのスタイルになるのではな
いかと思います。

130.0u 0.0s 2:55 74% 0+0k 0+0io 0pf+0w

3) Java ヒープ静的使用時(-Oオプション付き)

連続する玉を取り出すための配列を最初に一回だけヒープに取る方
式。本来ローカル変数にすべきものがクラスに行っちゃうんで美し
くない。

126.0u 0.0s 2:08 97% 0+0k 0+0io 0pf+0w

どこが 20倍やねん。

しかし、2)と3)の所要時間がそれほど変わらないのは驚きです。

以下、Javaプログラムのソースです(ヒープ動的確保版)。
実行していることがわかるように、順列を1000個チェックする毎に
"*"を表示しています。C の方は配列をグローバルに取っている以
外、だいたい同じものです。

# ベースのソースはCですし、VMの性能試験ですからCと条件を同じ
# にしなければならないわけで、staticの固まりになっています。
# OOPしてないぞ、と文句を付けないように(^^;

<ここから><ここから><ここから><ここから><ここから><ここから>
class Ball {
    static int [] pattern;
    static boolean [] used;
    static int  count;

    public static void main (String args[]) {
        pattern = new int [5];
        used = new boolean [16];

        count = 0;
        clearUsed();
        makePattern(0);
    }

    static void clearUsed() {
        int i;

        for (i = 0; i <= 15; i++) {
            used[i] = false;
        }
    }

    static void checkPattern() {
        int     start, len;
        int     i, pos;
        int     sum;
        boolean [] check;

        check = new boolean [100];

        for (i = 1; i <= 21; i++) {
            check[i] = false;
        }
        for (start = 0; start < 5; start++) {
            for (len = 1; len <= 5; len++) {
                sum = 0;
                pos = start;
                for (i = 0; i < len; i++) {
                    sum += pattern[pos];
                    if (pos < 4) {
                        pos++;
                    } else {
                        pos = 0;
                    }
                }
                check[sum] = true;
            }
        }
        for (i = 1; i <= 21; i++) {
            if (check[i] == false)
                break;
        }
        if (i == 22) {
            System.out.print("\n");
            for (i = 0; i < 5; i++) {
                System.out.print(pattern[i]);
            }
            System.out.print("\n");
        }
        count++;
        if (count % 1000 == 0)
            System.out.print("*");
    }

    static void makePattern(int depth) {
        int i;

        for (i = 1; i <= 15; i++) {
            if (!used[i]) {
                pattern[depth] = i;
                used[i] = true;
                if (depth < 4) {
                    makePattern(depth + 1);
                } else {
                    checkPattern();
                }
                used[i] = false;
            }
        }
    }
}
<ここまで><ここまで><ここまで><ここまで><ここまで><ここまで>

------------------------------------------------------------
  前橋 和弥                             maebashi@xxxxxxxxxx
  中部ソフトエンジニアリング(株)
    〒450 名古屋市中村区名駅4-10-25(名駅IMAIビル 5F)
    Tel:(052)583-4511(代) 内線 252 Fax:(052)583-4566
------------------------------------------------------------