シフト演算と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 |
全然違う。
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 |
それでもシフト演算の方が速いのだが、test2との違いは何だろう‥ソースを追おうにもnativeメソッドだし‥謎だ‥