convert integer to std::string

int型変数を std::string に変換する方法を考えてみた。

C言語で、char * にするなら、反射的に、sprintf などを使うと思うが、 std::string に入れたいときに一番いい方法はあまり思いつかない。 今回は、いくつか案を考えて実際に家のPCで計測してみた。 以下のような関数をそれぞれ定義して、計測する。

void func(int num, std::string &str);

計測に使った関数は以下のとおり。 getMicroTime はマイクロタイムを取得する関数。

void testCount(const char *msg, int count, void (*func)(int, std::string &)){
    std::string str;
    int num;

    long start, ustart, end, uend;
    getMicroTime(start, ustart);
    for(int i=-count; i< count; i++){
        num = i;
        (*func)(num, str);
    }
    getMicroTime(end, uend);
    double i = (end - start) * 1000000;
    double f = uend - ustart;

    printf("%s time:%lf\n", msg, (i+f)/2/count );
}

[1]std::streamstring を使う

一番 C++ らしい方法はこれかもしれない。

void intToString1(int num, std::string &str){
    std::stringstream ss;
    ss << num;
    str = ss.str();
}

しかし、今回調べた中で最も遅かった。

[2]sprintf を使う

C言語のスタンダードな方法だと思う。

void intToString2(int num, std::string &str){
    char buf[32];
    sprintf(buf, "%d", num);
    str = buf;
}

[1]に比べたら、5～6倍ぐらい早かった

[3]10 のmodulo演算を使用

modulo 演算で、1の位から順に決定していく。

void intToString3(int num, std::string &str){
    int snum = num;
    if(num<0)
        snum = ~num + 1;
    char buf[12];
    char *ptr = buf+11;
    *ptr = '\0';
    while(snum > 0){
        *(--ptr) = '0' + snum % 10;
        snum /= 10;
    }
    if(num<0)
        *(--ptr) = '-';

    str = ptr;
}

[2]よりも、2～3倍速い

[4]長さを求めて、引数のstd::string に直接書き込む

作業用バッファを用意するのではなく、引数の std::string に直接書き込む方法とした。

void intToString4(int num, std::string &str){
    int snum = num & 0x80000000 ? ~num + 1 : num;

    int len = snum < 10000  ? (snum < 100 ? ( snum < 10 ? 1 : 2 ) : snum < 1000 ? 3 : 4)
         : snum < 100000000 ? (snum < 1000000 ? ( snum < 100000 ? 5 : 6 ) : snum < 10000000 ? 7 : 8)
         : snum < 1000000000 ? 9 : 10;

    if(num & 0x80000000)
        ++len;
    str.resize(len);

    while(snum > 0){
        str[--len] = '0' + snum % 10;
        snum /= 10;
    }
    if(num & 0x80000000)
        str[0] = '-';
}

[3]よりもだいたい 1.5 倍くらい早い

[5]std::string::data() で内部メモリに直接書く

[4]を修正し、str.data() で取得したアドレスに直接書いてみた。

    int snum = num & 0x80000000 ? ~num + 1 : num;

    int len = snum < 10000  ? (snum < 100 ? ( snum < 10 ? 1 : 2 ) : snum < 1000 ? 3 : 4)
         : snum < 100000000 ? (snum < 1000000 ? ( snum < 100000 ? 5 : 6 ) : snum < 10000000 ? 7 : 8)
         : snum < 1000000000 ? 9 : 10;
    if(num<0)
        ++len;
    str.resize(len);

    char *ptr = (char *)str.data()+len;
    while(snum > 0){
        *(--ptr) = '0' + snum % 10;
        snum /= 10;
    }
    if(num & 0x80000000)
        *(--ptr) = '-';
}

[4]より1.2倍くらい早くなった。

[6]再度sprintf

内部メモリに直接書く方法で、sprintf を使う方法にしてみた。

void intToString6(int num, std::string &str){
    int snum = num & 0x80000000 ? ~num + 1 : num;

    int len = snum < 10000  ? (snum < 100 ? ( snum < 10 ? 1 : 2 ) : snum < 1000 ? 3 : 4)
         : snum < 100000000 ? (snum < 1000000 ? ( snum < 100000 ? 5 : 6 ) : snum < 10000000 ? 7 : 8)
         : snum < 1000000000 ? 9 : 10;
    if(num<0)
        ++len;
    str.resize(len);

    char *ptr = (char *)str.data()+len;
    sprintf(ptr, "%d", num);
}

[5]に比べると、5倍~6倍くらい遅くなってしまった。

[7]大きい位の数から順に決めていく

長さを先に決めているので、大きい位から代入していくことにした。

void intToString7(int num, std::string &str){
    int snum = num & 0x80000000 ? ~num + 1 : num;

    int len = snum < 10000  ? (snum < 100 ? ( snum < 10 ? 1 : 2 ) : snum < 1000 ? 3 : 4)
         : snum < 100000000 ? (snum < 1000000 ? ( snum < 100000 ? 5 : 6 ) : snum < 10000000 ? 7 : 8)
         : snum < 1000000000 ? 9 : 10;
    if(num & 0x80000000)
        ++len;
    str.resize(len);

    char *ptr = (char *)str.data()-1;
    if( num & 0x80000000 ){
        *(++ptr) = '-';
         --len;
    }

    int one;
    if( len > 9 )
        one = snum / 1000000000, *(++ptr) = '0' + one, snum -= 1000000000 * one;
    if( len > 8 )
        one = snum / 100000000, *(++ptr) = '0' + one, snum -= 100000000  * one;
    if( len > 7 )
        one = snum / 10000000, *(++ptr) = '0' + one, snum -= 10000000 * one;
    if( len > 6 )
        one = snum / 1000000, *(++ptr) = '0' + one, snum -= 1000000 * one;
    if( len > 5 )
        one = snum / 100000, *(++ptr) = '0' + one, snum -= 100000 * one;
    if( len > 4 )
        one = snum / 10000, *(++ptr) = '0' + one, snum -= 10000 * one;
    if( len > 3 )
        one = snum / 1000, *(++ptr) = '0' + one, snum -= 1000 * one;
    if( len > 2 )
        one = snum / 100, *(++ptr) = '0' + one, snum -= 100  * one;
    if( len > 1 )
        one = snum / 10, *(++ptr) = '0' + one, snum -= 10 * one;

    *(++ptr) = '0' + snum;
}

これが、今回最も早い方法で、[5]よりも少し速くなった。

[8]少し改良

[7]を while を使って、キレイに書いてみた。

void intToString8(int num, std::string &str){
    static int tens[]={ 0, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000};
    int snum = num & 0x80000000 ? ~num + 1 : num;

    int len = snum < 10000  ? (snum < 100 ? ( snum < 10 ? 1 : 2 ) : snum < 1000 ? 3 : 4)
         : snum < 100000000 ? (snum < 1000000 ? ( snum < 100000 ? 5 : 6 ) : snum < 10000000 ? 7 : 8)
         : snum < 1000000000 ? 9 : 10;
    if(num & 0x80000000)
        ++len;
    str.resize(len);

    char *ptr = (char *)str.data();
    if(num & 0x80000000){
        *(ptr++) = '-';
         --len;
    }
    --ptr;

    int one = 0;
    int *tptr = &tens[len];
    while(*(--tptr)){
        one = snum / *tptr;
        *(++ptr) = '0' + one;
        snum -= *tptr * one;
    }
    *(++ptr) = '0' + snum;
}

なぜか、このコードは比較的遅いという結果になった。 配列tensから値を引くところが遅いようである。 [7]を配列tensを使うように変えると遅くなり、O2か、O3を指定すると[7]と同じ速度になった。

以上の計測結果は以下のとおり。

./out speed (最適化コンパイルなし )
intToString1 time:1.052384
intToString2 time:0.232779
intToString3 time:0.114349
intToString4 time:0.127272
intToString5 time:0.095429
intToString6 time:0.214056
intToString7 time:0.073023
intToString8 time:0.186148
./out1 speed ( -O コンパイルオプション )
intToString1 time:0.745957
intToString2 time:0.215731
intToString3 time:0.066834
intToString4 time:0.042813
intToString5 time:0.031119
intToString6 time:0.177850
intToString7 time:0.036448
intToString8 time:0.116570
./out2 speed ( -O2 コンパイルオプション )
intToString1 time:0.714182
intToString2 time:0.223773
intToString3 time:0.062432
intToString4 time:0.048148
intToString5 time:0.033870
intToString6 time:0.192560
intToString7 time:0.032088
intToString8 time:0.115626
./out3 speed ( -O3 コンパイルオプション )
intToString1 time:0.780855
intToString2 time:0.201429
intToString3 time:0.061252
intToString4 time:0.048085
intToString5 time:0.034723
intToString6 time:0.186857
intToString7 time:0.032486
intToString8 time:0.115503

こうしてみると、最速の[7] が、stringstream [1] よりも 20倍くらい異なる結果となった。 しかし単位はマイクロタイムなので、少し改良したところで大した差にはならない上、現状でもかなり速い。 改善するなら、全てビット演算だけで記述できればもっと改善できるかもしれない。