桁数を求める（2）

昨日の日記（id:kt-blackout:20040815#p1）で桁数を求める関数のベンチマークの比較を取ってみた。結果としてtype_D（昨日の日記参照）がもっとも速かったわけだけど、同日のid:PaiNさんのコメントを見て気付いたことがある。

それはベンチマークの取り方だ。昨日は0からCOUNT_MAXまでのすべての数字の桁を求めることでベンチマークとした。それも１つのやり方として間違ってはいないだろうけど、これはアルゴリズムの１つの側面でしかない。そこで、別の２通りの計測を行なってみた。それぞれの疑似ソースを見て頂きたい（COUNT_MAX=2,000,000,000）。

＜ベンチマークタイプ1＞ 0 - 10桁の全体を対象とする

for (int i=0; i

＜ベンチマークタイプ2＞ 8桁以上の数のみを対象

for (int i=0; i

＜ベンチマークタイプ3＞ 6桁未満の数のみを対象

for (int i=0; i

そして、ベンチマークを取ったのは以下の二つの関数

#define FIG_10 1000000000
#define FIG_9 100000000
#define FIG_8 10000000
#define FIG_7 1000000
#define FIG_6 100000
#define FIG_5 10000
#define FIG_4 1000
#define FIG_3 100
#define FIG_2 10
#define FIG_1 1

int type_D(int n)
{
    n = (n>=0)?n:-n;
    if      (n >= FIG_10)   return 10;
    else if (n >= FIG_9)    return 9;
    else if (n >= FIG_8)    return 8;
    else if (n >= FIG_7)    return 7;
    else if (n >= FIG_6)    return 6;
    else if (n >= FIG_5)    return 5;
    else if (n >= FIG_4)    return 4;
    else if (n >= FIG_3)    return 3;
    else if (n >= FIG_2)    return 2;
    else                    return 1;
}

int type_E(int n)
{
    n = (n>=0)?n:-n;

    if (n >= FIG_6) {
        if (n >= FIG_8) {
            if (n >= FIG_10)        return 10;
            else if (n >= FIG_9)    return 9;
            else                    return 8;
        }
        else {
            if (n >= FIG_7)         return 7;
            else                    return 6;
        }
    }
    else { /* n < FIG_6 */
        if (n >= FIG_3) {
            if (n >= FIG_5)         return 5;
            else if (n >= FIG_4)    return 4;
            else                    return 3;
        }
        else {
            if (n >= FIG_2)         return 2;
            else                    return 1;
        }
    }
}

type_D()は問題無いと思う。type_E()は桁数を二分探索で絞りこむようになっている。こうすることでどんなときも比較の回数を3,4回で求めることを可能にしている。type_Eでは見ての通り比較回数は1-9回となっているので性質が違うことが分かると思う。

# 余談。PaiNさんが言おうとしてたのはtype_Eのことでしょうか？ PaiNさんのコメントを見て「あぁ、二分探索すれば良いのか」と思ったものの、何か比較の手順が違う…。

そして結果は以下の通り。

	Bench 1（全域）	Bench 2（高域）	Bench 3（低域）
type_D	8.14000	23.65000	35.14000
type_E	10.28000	30.51000	24.81000

おし、想像通りの結果。一言で言えば、type_Eは大きな数の桁数を求めるのが遅い。極端な話10桁の数字を対象とするとtype_Dでは1回の比較ですむのが、type_Eでは3回かかるのだから当然だ。しかも皮肉なことに全域を平均的に走査すると大きな数の方が多いから、ベンチマーク1でtype_Dのほうが優勢なわけだ。同様に高域のみを対象とするベンチマーク2でもtype_Dのほうが速い。そして、低域のみを対象とするベンチマーク3ではtype_Eがダントツに速くなる。

つまりtype_Eはたしかに平均的には速いが、数字の桁数の分布というのは大きな数ほど多いので全域を対象とすると負ける。ただ一般的には極端に大きな数を扱うことは少ないので、type_Eが良いように思う。type_Dだとバランスが悪いし、得意とする桁数が6桁以上なのは別に嬉しくない。

と、今日もまた、そんなに凄くないことを、さも凄いかのように熱く書いてみた。