読者です 読者をやめる 読者になる 読者になる

HHeLiBeXの日記 正道編

日々の記憶の記録とメモ‥

シフト演算とMath.pow(2, n)と(+Math.pow(2, n)の怪)

自分が時々やらかしてしまうのでメモ。

環境は、CentOS 7(VM)上のOpenJDK 1.8.0_111。

2のべき乗(整数値)が欲しい場合はシフト演算

2のべき乗(整数値)が欲しいときに時々やらかしてしまうのが、以下のようなコードを書いてしまうこと。

for (int i = 0; i < 63; ++i) {
    long tmp = (long)Math.pow(2, i);
}

基数が2以外だったり指数が整数でなかったりdouble値が欲しかったりlongのMAX_VALUEを超える場合だったり、そんな場合は仕方がないのだが、2のべき乗(整数値)が欲しい場合はシフト演算の方が断然速い。

for (int i = 0; i < 63; ++i) {
    long tmp = 1L << i;
}

どれくらい速いのか、実際に計ってみた。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        long S;
        long G;

        int cnt;

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        System.out.print(n);

        S = System.currentTimeMillis();
        test1(n, m);
        G = System.currentTimeMillis();
        System.out.print("," + (G - S));

        S = System.currentTimeMillis();
        test2(n, m);
        G = System.currentTimeMillis();
        System.out.print("," + (G - S));

        S = System.currentTimeMillis();
        test3(n, m);
        G = System.currentTimeMillis();
        System.out.print("," + (G - S));

        System.out.println();
    }
    private static void test1(int n, int m) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 63; ++j) {
                long tmp = 1L << j;
            }
        }
    }
    private static void test2(int n, int m) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 63; ++j) {
                long tmp = (long)Math.pow(2, j);
            }
        }
    }
    private static void test3(int n, int m) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < 63; ++j) {
                long tmp = (long)Math.pow(2, m);
            }
        }
    }
}

test1が「Math.pow(2, n)」、test2が「シフト演算」を使ったケース。

test3は後で使うので後述。

実行は以下のような感じ。

for i in 100 250 500 1000 2500 5000 10000 25000 50000 100000 250000 500000 1000000 ; do
    echo $i 62 | java Main
done

実行結果のうち、test1とtest2を抜き出したものは以下の通り。単位はミリ秒。

n test1 test2
100 0 1
250 0 2
500 0 3
1000 1 5
2500 3 16
5000 5 30
10000 9 54
25000 10 121
50000 12 233
100000 13 458
250000 21 1142
500000 31 2260
1000000 54 4513

f:id:hhelibex:20161220232156p:plain

全然違う。

Math.pow(2, n)の怪

検証している最中に妙なことに気付いたのでついでにメモ。

上記プログラムのtest1とtest3を使う。

test3のポイントは、「Math.pow(2, m)」とループの最中に変わることがない値を指数に指定していること。

実行結果のうち、test1とtest3を抜き出してみる。単位はミリ秒。

n test1 test3
100 0 0
250 0 1
500 0 3
1000 1 8
2500 3 18
5000 5 31
10000 9 37
25000 10 37
50000 12 40
100000 13 45
250000 21 59
500000 31 83
1000000 54 130

f:id:hhelibex:20161220232701p:plain

それでもシフト演算の方が速いのだが、test2との違いは何だろう‥ソースを追おうにもnativeメソッドだし‥謎だ‥