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倍くらい異なる結果となった。 しかし単位はマイクロタイムなので、少し改良したところで大した差にはならない上、現状でもかなり速い。 改善するなら、全てビット演算だけで記述できればもっと改善できるかもしれない。
