JavaのIntegerクラスgetCharsメソッドがおもしろい。このメソッド自体はpackage privateなので直接呼び出すことはできないが、Integer.toStringのメイン処理が実装されている。
メソッドのシグネチャはgetChars(int i, int index, char[] buf)で整数iを表す文字列をbufに格納するというもの。このとき文字列はindexから0の方向にLSB -> MSBの順で埋められていく。
これだけ聞くと簡単そうに聞こえるが、高速化のためにおもしろい処理がされている。
とりあえず実装を載せておく。
static void getChars(int i, int index, char[] buf) {
int q, r;
int charPos = index;
char sign = 0;
if (i < 0) {
sign = '-';
i = -i;
}
// Generate two digits per iteration
while (i >= 65536) {
q = i / 100;
// really: r = i - (q * 100);
r = i - ((q << 6) + (q << 5) + (q << 2));
i = q;
buf [--charPos] = DigitOnes[r];
buf [--charPos] = DigitTens[r];
}
// Fall thru to fast mode for smaller numbers
// assert(i <= 65536, i);
for (;;) {
q = (i * 52429) >>> (16+3);
r = i - ((q << 3) + (q << 1)); // r = i-(q*10) ...
buf [--charPos] = digits [r];
i = q;
if (i == 0) break;
}
if (sign != 0) {
buf [--charPos] = sign;
}
}
まず第一段の処理としてiが65536以上の場合は2桁（10進数で）ずつ処理していく。
コメントを見ると、
r = i - ((q << 6) + (q << 5) + (q << 2))
と
r = i - (q * 100)
が等価であることが分かる。確かに100 = 64 + 32 + 4なのでそのとおり。DigitOnesとDigitTensはそれぞれ2桁の数字の1桁目と2桁目をO(1)で取り出すためのテーブル。これはハードコーディングされている。
まあここまでは分かる。
問題は次の第二段目の処理。
q = (i * 52429) >>> (16+3);
r = i - ((q << 3) + (q << 1));
何ですか、これは。。
何ですか、これは。∑(￣Д￣；)
先ほどの100倍と同じように、
r = i - ((q << 3) + (q << 1));
は、r = i - (q * 10)のこと。
ということは逆算して考えると、
q = (i * 52429) >>> (16+3);
ってのは、
q = i / 10ですか？試してみると確かにそうなっている。
でも何で52429と(16+3)なの？他の数字じゃだめなの？？
ということで、いろいろ試行錯誤して「52429」が唯一使える数字ということを確認したコードが以下。
package com.kenjih.test;
public class Clazz {
public void run() {
// 割り算をシフト演算にしたいので、２の冪乗のみ
for (int i = 0 ; i < 32 ; i++) {
int x = 1<<i;
// 10 * y / x == 1となるようなyが候補。
int y = x/10;
if (y++ == 0)
continue;
// 65535を掛けたとき0xffffffffを越えないか？
//（シフト演算が>>>なのでCでいうところのunsigned intの範囲までなら扱える）
if (y * 65535L > 0x0ffffffffL)
continue;
// 60009 * y - 6000 * x < xか？
// 上式が成り立たない場合は、60009 * y % x = 6001（以上）になってしまう。
if (x * 6001 > 60009 * y)
System.out.println(y);
}
}
public static void main(String[] args) {
new Clazz().run();
}
}
以下が実行結果。
$ 52429
まさにシフト演算のマジックやぁ～～。(ﾉ￣□￣)ﾉｵｵｵｫｫｫｫ!
コイツはしびれますね。
で結局これってほんとに速いの？？
ということで高速化を考えず書いた普通の処理と比べてみる。
package com.kenjih.test;
public class MyInteger {
private static char[] digits = {
'0', '1', '2', '3', '4',
'5', '6', '7', '8', '9'
};
public static String toString(int i) {
char[] buf = new char[16];
boolean minus = i < 0;
int pos = 16;
while (i > 0) {
buf[--pos] = digits[i % 10];
i /= 10;
}
if (minus)
buf[pos] = '-';
return new String(buf, pos, (16 - pos));
}
}
普通に書くとまあこんなもんでしょっ。
桁数が大きい方が高速化が生きて来そうなので、1,000,000,000 - 1,100,000,000までを変換する処理も用いて比べてみた。
比較結果。
Integer = 0m4.499s
MyInteger = 0m5.681s
2割くらい速い！（微妙っ。いや、この違いは結構大きいのか？）
