まず、よく見かける高速化の方法とは、次のようなものである。
x = x >> 1;
これが「2で割る」という処理の高速版として紹介されている。「計算速度が2倍になった」とか「これをやらない手はない!300%の高速化!」みたいなことが書いてある(主に英語のサイトなので、TORITORIが勝手に意訳しています)。仮にこれが本当だとしても、注意すべきことがある。
- xは整数でなければならない。整数以外でも動作をするが、計算結果は整数になる。
- 負の数の場合、結果が異なる。var a:int = -11 / 2では、a=-5となる。一方、var b:int = -11 >> 1では、b=-6となる。
- 演算の優先順位が異なる。割る(/)は加法・減法よりも優先される。しかし、この代替演算は、加法・減法よりも優先順位が低い。上記二点を理解した上で、単純に割る2の記号(/2)をビットシフトの演算(>>1)に置き換えても、だめである。括弧でくくる必要がある。例えば16 / 2 + 1 と 1 + 16 / 2はどちらも答えは9である。これの/2を単純に>>1に置き換えると、前者は4に後者は8になる。
ややこしいことを書いたが、これだけ注意すべきことがあるということは、書き換えるにはかなり注意が要るということを意味する。単純に機械的な置き換えができないからだ。それでも、2倍3倍に高速化されるなら、やるだけの価値があるかもしれない。
そこで、演算時間を実際に計ってみた。まず、計測に用いたソースコード、次に結果のグラフを載せている。
package {
import flash.display.Sprite;
import flash.utils.getTimer;
public class BitShiftApp extends Sprite {
private var _max:int = 1000000;
public function BitShiftApp() {
var value:int = -11; //Try
trace(value / 2, value * .5, value >> 1);
var result1:int;
var result2:int;
var result3:int;
trace("division,multiplication,bit_shift");
for(var i:int = 0;i < result1 =" division(value)" result2 =" multiplication(value);" result3 =" bitshift(value);" color="#cc6666"> trace(result1,",", result2,",", result3);
}
}
private function division(value:int):int {
var now:int = getTimer();
var result:Number;
for(var i:int = 0;i < result =" value/2;" color="#0033FF"> return getTimer() - now;
}
private function multiplication(value:int):int {
var now:int = getTimer();
var result:Number;
for(var i:int = 0;i < result =" value*.5;" color="#0033FF"> return getTimer() - now;
}
private function bitshift(value:int):int {
var now:int = getTimer();
var result:Number;
for(var i:int = 0;i < result =" value">> 1;
}
return getTimer() - now;
}
}
}
「割る2(/2)」と「かける0.5(*.5)」と「右にシフト(>>1)」で比べたものである。それぞれ、10万回の計算にかかる時間である。それぞれ40回行っての平均を比べている。40回のうちの、最初の1回の結果は、計測に用いてない。リソースの利用状況が不安定な場合があるからだ。結果は、ご覧のように、2倍、3倍の差はないのである。
では、なぜ、2倍3倍になったなどという結果が報告されているのだろう?想像するに、1回しか計測していないと思われる。そして、1つのプログラムの中で、最初に通常の割り算、次にビットシフトの順で計算していると思われる。このことから、最初に処理される通常の割り算は、プログラムの起動処理と重なり、処理に時間がかかったように常に見えるのではないだろうか?
これは、以下のような2つのプログラムで簡単に実験できる。最初行われた計算の方が常に遅い。こういったプログラムでは、最初に普通の書き方、次に特殊な書き方で、速度を調べたくなるのが人情なのかもしれない。それぞれ実行してみれば、常に、最初の計算方法の方が遅いという結果が出る。
最初に割り算、次にビットシフトの演算速度を検証しようとするプログラム例
package {
import flash.display.Sprite;
import flash.utils.getTimer;
public class FirstDivNextBit extends Sprite {
public function FirstDivNextBit() {
var max:int = 1000000;
var i:int;
var value:int = 10;
var half:int;
var now:int;
now = getTimer();
for(i = 0;i < max;i++) {
half = value / 2;
}
trace(getTimer() - now);
now = getTimer();
for(i = 0;i < max;i++) {
half = value >> 1;
}
trace(getTimer() - now);
}
}
}
最初にビットシフト、次に割り算の演算速度を検証しようとするプログラム例
package {
import flash.display.Sprite;
import flash.utils.getTimer;
public class FirstBitNextDiv extends Sprite {
public function FirstBitNextDiv() {
var max:int = 1000000;
var i:int;
var value:int = 10;
var half:int;
var now:int;
now = getTimer();
for(i = 0;i < max;i++) {
half = value >> 1;
}
trace(getTimer() - now);
now = getTimer();
for(i = 0;i < max;i++) {
half = value / 2;
}
trace(getTimer() - now);
}
}
}