Q&A
実行時間を正確にだすには、繰り返し実行 (1000回とか) して平均を取った方がいいですよ。
タイトル通りですが、C/C++で整数の桁数を最短で求めるにはどうすればよいでしょうか？
実験として、以下のようなプログラムを書いて、①10で割っていく、②常用対数を使う、の２通りを試してみました。
C
1#include <stdio.h> 2#include <math.h> 3#include <time.h> 4 5 6void countDigit(int n) 7{ 8 int digit = 1; 9 clock_t start,end; 10 11 start = clock(); 12 13 while((n /= 10) != 0) 14 digit++; 15 16 end = clock(); 17 18 printf("countDigit() digit::%d time::%dms\n",digit,(int)(end - start)); 19} 20 21void countDigitUsingLog(int n) 22{ 23 clock_t start,end; 24 int digit; 25 26 start = clock(); 27 28 digit = log10(n) + 1; 29 30 end = clock(); 31 printf("countDigitUsingLog() digit::%d time::%dms\n",digit,(int)(end - start)); 32} 33 34int main(void) 35{ 36 int n = 0; 37 int i; 38 39 for(i = 1;i < 10;i++) { 40 n = n * 10 + i; 41 printf("N = %d\n",n); 42 countDigit(n); 43 countDigitUsingLog(n); 44 printf("\n"); 45 } 46 47 return 0; 48} 49
実行結果：：
N = 1 countDigit() digit::1 time::3ms countDigitUsingLog() digit::1 time::47ms N = 12 countDigit() digit::2 time::1ms countDigitUsingLog() digit::2 time::12ms N = 123 countDigit() digit::3 time::2ms countDigitUsingLog() digit::3 time::2ms N = 1234 countDigit() digit::4 time::1ms countDigitUsingLog() digit::4 time::2ms N = 12345 countDigit() digit::5 time::1ms countDigitUsingLog() digit::5 time::2ms N = 123456 countDigit() digit::6 time::2ms countDigitUsingLog() digit::6 time::2ms N = 1234567 countDigit() digit::7 time::1ms countDigitUsingLog() digit::7 time::2ms N = 12345678 countDigit() digit::8 time::2ms countDigitUsingLog() digit::8 time::2ms N = 123456789 countDigit() digit::9 time::2ms countDigitUsingLog() digit::9 time::3ms
僕の実行環境では、①は桁数に関わらず一定の速さ、②は3桁目あたりから①の速さに追いつく、といった結果になりました。この結果だけみると①のほうが良いのではないかの思ったのですが、C/C++は初心者に毛が生えた程度の知識しかないので、検証方法にあまり自信がありません。この結果を信じてもよいのでしょか？また、他にもっと良い方法があれば教えてください。
<実行環境>
Ubuntu 16.04 LTS
CPU : AMD A4-5000 APU with Radeon(TM) HD Graphics
gcc version 5.4.1 20160904 (Ubuntu 5.4.1-2ubuntu1~16.04)
<2017/1/23 追記>
皆さん回答ありがとうございました！ikedasさんのものとほとんど変わりませんが、皆さんが回答してくださったものを一通り僕の環境でも試してみました。与えられる整数値の桁数の範囲が分かっているなら、２分探索が一番良さそうです。とても勉強になりました、みなさん本当にありがとうございました！以下修正版と結果です。
C
1#include <stdio.h> 2#include <math.h> 3#include <time.h> 4#include <limits.h> 5#include <assert.h> 6 7#define LOOP 10000000 8 9 10void countDigit(int n) 11{ 12 int digit = 1; 13 clock_t start,end; 14 15 start = clock(); 16 17 for(size_t i = 0;i < LOOP; ++i) { 18 while((n /= 10) != 0) 19 digit++; 20 } 21 22 end = clock(); 23 24 printf("%-25s\tdigit::%d\ttime::%fs\n", 25 "countDigit()",digit,((double)end - start)/CLOCKS_PER_SEC); 26} 27 28void countDigitUsingLog(int n) 29{ 30 clock_t start,end; 31 int digit; 32 33 start = clock(); 34 35 for(size_t i = 0;i < LOOP; ++i) 36 digit = log10(n) + 1; 37 38 end = clock(); 39 40 printf("%-25s\tdigit::%d\ttime::%fs\n", 41 "countDigitUsingLog()",digit,((double)end - start)/CLOCKS_PER_SEC); 42} 43 44void countDigitBinary(int n) 45{ 46 int digit; 47 clock_t start,end; 48 49 start = clock(); 50 51 for(size_t i = 0;i < LOOP; ++i) { 52 53 if (n < 100000) { 54 if (n < 1000) { 55 if (n < 10) 56 digit = 1; 57 else if (n < 100) 58 digit = 2; 59 else 60 digit = 3; 61 } else { 62 if (n < 10000) 63 digit = 4; 64 else 65 digit = 5; 66 } 67 } else { 68 if (n < 10000000) { 69 if (n < 1000000) 70 digit = 6; 71 else 72 digit = 7; 73 } else { 74 if (n < 100000000) 75 digit = 8; 76 else if (n < 1000000000) 77 digit = 9; 78 else 79 digit = 10; 80 } 81 } 82 } 83 84 85 end = clock(); 86 87 printf("%-25s\tdigit::%d\ttime::%fs\n", 88 "countDigitBinary()",digit,((double)end - start)/CLOCKS_PER_SEC); 89} 90 91int digitPoor(int n) 92{ 93 assert(INT_MAX == 2147483647); 94 assert(n >= 0); 95 96 if (n < 10) return 1; 97 if (n < 100) return 2; 98 if (n < 1000) return 3; 99 if (n < 10000) return 4; 100 if (n < 100000) return 5; 101 if (n < 1000000) return 6; 102 if (n < 10000000) return 7; 103 if (n < 100000000) return 8; 104 if (n < 1000000000) return 9; 105 return 10; 106} 107 108void countDigitPoor(int n) 109{ 110 clock_t start,end; 111 int digit; 112 113 start = clock(); 114 for (size_t i=0; i < 10000000; ++i) { 115 digit = digitPoor(n); 116 } 117 end = clock(); 118 printf("%-25s\tdigit::%d\ttime::%fs\n", 119 "countDigitPoor()",digit,((double)end - start)/CLOCKS_PER_SEC); 120} 121 122void countDigitUsingSprintf(int n) 123{ 124 clock_t start,end; 125 int digit; 126 char dummy[10]; 127 128 start = clock(); 129 130 for(size_t i = 0;i < LOOP; ++i) 131 digit = sprintf(dummy, "%d", n); 132 133 end = clock(); 134 printf("%-25s\tdigit::%d\ttime::%fs\n", 135 "countDigitUsingSprintf()",digit,((double)end - start)/CLOCKS_PER_SEC); 136} 137 138void countForLoop() 139{ 140 clock_t start,end; 141 volatile int x=1; 142 143 start = clock(); 144 145 for (size_t i = 0; i < LOOP; ++i) 146 { 147 x=i; 148 } 149 150 end = clock(); 151 152 printf("%-25s\t--------\ttime::%fs\n", 153 "countForLoop()",((double)end - start)/CLOCKS_PER_SEC); 154} 155 156int main(void) 157{ 158 int n = 0; 159 int i; 160 161 for(i = 1;i < 10;i++) { 162 n = n * 10 + i; 163 printf("N = %d\n",n); 164 countForLoop(); 165 countDigit(n); 166 countDigitUsingLog(n); 167 countDigitBinary(n); 168 countDigitPoor(n); 169 countDigitUsingSprintf(n); 170 printf("\n"); 171 } 172 173 return 0; 174} 175
N = 1 countForLoop() -------- time::0.045770s countDigit() digit::1 time::0.100439s countDigitUsingLog() digit::1 time::0.378452s countDigitBinary() digit::1 time::0.053568s countDigitPoor() digit::1 time::0.079120s countDigitUsingSprintf() digit::1 time::2.265236s N = 12 countForLoop() -------- time::0.043182s countDigit() digit::2 time::0.100408s countDigitUsingLog() digit::2 time::1.012793s countDigitBinary() digit::2 time::0.060286s countDigitPoor() digit::2 time::0.092724s countDigitUsingSprintf() digit::2 time::2.341804s N = 123 countForLoop() -------- time::0.042746s countDigit() digit::3 time::0.100416s countDigitUsingLog() digit::3 time::1.004158s countDigitBinary() digit::3 time::0.060143s countDigitPoor() digit::3 time::0.108729s countDigitUsingSprintf() digit::3 time::2.442325s N = 1234 countForLoop() -------- time::0.045008s countDigit() digit::4 time::0.100400s countDigitUsingLog() digit::4 time::1.004526s countDigitBinary() digit::4 time::0.048930s countDigitPoor() digit::4 time::0.132441s countDigitUsingSprintf() digit::4 time::2.530141s N = 12345 countForLoop() -------- time::0.042238s countDigit() digit::5 time::0.100400s countDigitUsingLog() digit::5 time::1.008050s countDigitBinary() digit::5 time::0.060654s countDigitPoor() digit::5 time::0.144062s countDigitUsingSprintf() digit::5 time::2.624742s N = 123456 countForLoop() -------- time::0.042451s countDigit() digit::6 time::0.100724s countDigitUsingLog() digit::6 time::1.008027s countDigitBinary() digit::6 time::0.058717s countDigitPoor() digit::6 time::0.177779s countDigitUsingSprintf() digit::6 time::2.751899s N = 1234567 countForLoop() -------- time::0.041235s countDigit() digit::7 time::0.100376s countDigitUsingLog() digit::7 time::1.004352s countDigitBinary() digit::7 time::0.069315s countDigitPoor() digit::7 time::0.193293s countDigitUsingSprintf() digit::7 time::2.825540s N = 12345678 countForLoop() -------- time::0.041624s countDigit() digit::8 time::0.100474s countDigitUsingLog() digit::8 time::1.004698s countDigitBinary() digit::8 time::0.075757s countDigitPoor() digit::8 time::0.215140s countDigitUsingSprintf() digit::8 time::2.937961s N = 123456789 countForLoop() -------- time::0.043923s countDigit() digit::9 time::0.100387s countDigitUsingLog() digit::9 time::1.004096s countDigitBinary() digit::9 time::0.094569s countDigitPoor() digit::9 time::0.254226s countDigitUsingSprintf() digit::9 time::3.033319s
回答6件
0
頭の悪そうなコードが良いパフォーマンスを出すことがあります。
ベンチマークはChironianさんのコードをベースにさせていただきました。
c
1#include <limits.h> 2#include <assert.h> 3 4... 5 6int digitPoor(int n) 7{ 8 assert(INT_MAX == 2147483647); 9 assert(n >= 0); 10 11 if (n < 10) return 1; 12 if (n < 100) return 2; 13 if (n < 1000) return 3; 14 if (n < 10000) return 4; 15 if (n < 100000) return 5; 16 if (n < 1000000) return 6; 17 if (n < 10000000) return 7; 18 if (n < 100000000) return 8; 19 if (n < 1000000000) return 9; 20 return 10; 21} 22 23void countDigitPoor(int n) 24{ 25 clock_t start,end; 26 int digit; 27 28 start = clock(); 29 for (size_t i=0; i < 10000000; ++i) { 30 digit = digitPoor(n); 31 } 32 end = clock(); 33 printf("countDigitPoor() digit::%d time::%fsec\n",digit,((double)end - start)/CLOCKS_PER_SEC); 34} 35
$ gcc --version gcc (GCC) 6.3.1 20170109 ... $ gcc -O1 -DNDEBUG ./bench.c -lm $ ./a.out N = 1 countForLoop() time::0.003087sec countDigit() digit::1 time::0.005684sec countDigitUsingLog() digit::1 time::0.138261sec countDigitPoor() digit::1 time::0.003104sec N = 12 countForLoop() time::0.003059sec countDigit() digit::2 time::0.010454sec countDigitUsingLog() digit::2 time::0.447394sec countDigitPoor() digit::2 time::0.003249sec N = 123 countForLoop() time::0.003394sec countDigit() digit::3 time::0.019453sec countDigitUsingLog() digit::3 time::0.444180sec countDigitPoor() digit::3 time::0.003249sec N = 1234 countForLoop() time::0.003439sec countDigit() digit::4 time::0.027927sec countDigitUsingLog() digit::4 time::0.436616sec countDigitPoor() digit::4 time::0.003247sec N = 12345 countForLoop() time::0.003234sec countDigit() digit::5 time::0.034176sec countDigitUsingLog() digit::5 time::0.448515sec countDigitPoor() digit::5 time::0.003319sec N = 123456 countForLoop() time::0.003215sec countDigit() digit::6 time::0.043226sec countDigitUsingLog() digit::6 time::0.446970sec countDigitPoor() digit::6 time::0.003536sec N = 1234567 countForLoop() time::0.003203sec countDigit() digit::7 time::0.053820sec countDigitUsingLog() digit::7 time::0.439272sec countDigitPoor() digit::7 time::0.003598sec N = 12345678 countForLoop() time::0.003272sec countDigit() digit::8 time::0.065535sec countDigitUsingLog() digit::8 time::0.446334sec countDigitPoor() digit::8 time::0.003244sec N = 123456789 countForLoop() time::0.003499sec countDigit() digit::9 time::0.079410sec countDigitUsingLog() digit::9 time::0.444234sec countDigitPoor() digit::9 time::0.003261sec
でも移植性を考えると割り算が無難だと思います。
投稿2017/01/22 16:42
総合スコア1151
0
ベストアンサー
sharowさんの「貧者のアルゴリズム」では最悪計算量がO(log n)ですが、二分探索にするとO(log log n)に減らせます!
lang
1int 2digitBinary(int n) 3{ 4 if (n < 100000) { 5 if (n < 1000) { 6 if (n < 10) 7 return 1; 8 else if (n < 100) 9 return 2; 10 else 11 return 3; 12 } else { 13 if (n < 10000) 14 return 4; 15 else 16 return 5; 17 } 18 } else { 19 if (n < 10000000) { 20 if (n < 1000000) 21 return 6; 22 else 23 return 7; 24 } else { 25 if (n < 100000000) 26 return 8; 27 else if (n < 1000000000) 28 return 9; 29 else 30 return 10; 31 } 32 } 33} 34 35void 36countDigitBinary(int n) 37{ 38 clock_t start,end; 39 int digit; 40 41 start = clock(); 42 for (size_t i=0; i < 10000000; ++i) { 43 digit = digitBinary(n); 44 } 45 end = clock(); 46 printf("countDigitBinary() digit::%d time::%fsec\n",digit,((double)end - start)/CLOCKS_PER_SEC); 47}
〈実行環境〉
macOS Sierra 10.12.2
CPU Core i5 1.7 GHz
clang --version
Apple LLVM version 8.0.0 (clang-800.0.42.1)
Target: x86_64-apple-darwin16.3.0
Thread model: posix
clang -O0
N = 1 countForLoop() time::0.023104sec countDigit() digit::1 time::0.047660sec countDigitUsingLog() digit::1 time::0.246963sec countDigitPoor() digit::1 time::0.037537sec countDigitBinary() digit::1 time::0.039012sec N = 12 countForLoop() time::0.023421sec countDigit() digit::2 time::0.084005sec countDigitUsingLog() digit::2 time::0.233920sec countDigitPoor() digit::2 time::0.051066sec countDigitBinary() digit::2 time::0.043674sec N = 123 countForLoop() time::0.025515sec countDigit() digit::3 time::0.117607sec countDigitUsingLog() digit::3 time::0.236735sec countDigitPoor() digit::3 time::0.053296sec countDigitBinary() digit::3 time::0.051939sec N = 1234 countForLoop() time::0.025521sec countDigit() digit::4 time::0.173296sec countDigitUsingLog() digit::4 time::0.234089sec countDigitPoor() digit::4 time::0.060343sec countDigitBinary() digit::4 time::0.045750sec N = 12345 countForLoop() time::0.025067sec countDigit() digit::5 time::0.224774sec countDigitUsingLog() digit::5 time::0.236502sec countDigitPoor() digit::5 time::0.070013sec countDigitBinary() digit::5 time::0.051067sec N = 123456 countForLoop() time::0.024541sec countDigit() digit::6 time::0.300018sec countDigitUsingLog() digit::6 time::0.236935sec countDigitPoor() digit::6 time::0.084706sec countDigitBinary() digit::6 time::0.043754sec N = 1234567 countForLoop() time::0.026226sec countDigit() digit::7 time::0.365955sec countDigitUsingLog() digit::7 time::0.241753sec countDigitPoor() digit::7 time::0.082430sec countDigitBinary() digit::7 time::0.049685sec N = 12345678 countForLoop() time::0.025289sec countDigit() digit::8 time::0.430325sec countDigitUsingLog() digit::8 time::0.236876sec countDigitPoor() digit::8 time::0.094294sec countDigitBinary() digit::8 time::0.050104sec N = 123456789 countForLoop() time::0.026642sec countDigit() digit::9 time::0.513616sec countDigitUsingLog() digit::9 time::0.237418sec countDigitPoor() digit::9 time::0.097828sec countDigitBinary() digit::9 time::0.061868sec
clang -Ofast
N = 1 countForLoop() time::0.004516sec countDigit() digit::1 time::0.000000sec countDigitUsingLog() digit::1 time::0.000039sec countDigitPoor() digit::1 time::0.000000sec countDigitBinary() digit::1 time::0.000000sec N = 12 countForLoop() time::0.003351sec countDigit() digit::2 time::0.011395sec countDigitUsingLog() digit::2 time::0.000001sec countDigitPoor() digit::2 time::0.000000sec countDigitBinary() digit::2 time::0.000000sec N = 123 countForLoop() time::0.003504sec countDigit() digit::3 time::0.020016sec countDigitUsingLog() digit::3 time::0.000002sec countDigitPoor() digit::3 time::0.000001sec countDigitBinary() digit::3 time::0.000000sec N = 1234 countForLoop() time::0.005942sec countDigit() digit::4 time::0.033859sec countDigitUsingLog() digit::4 time::0.000002sec countDigitPoor() digit::4 time::0.000001sec countDigitBinary() digit::4 time::0.000000sec N = 12345 countForLoop() time::0.003354sec countDigit() digit::5 time::0.050976sec countDigitUsingLog() digit::5 time::0.000001sec countDigitPoor() digit::5 time::0.000001sec countDigitBinary() digit::5 time::0.000002sec N = 123456 countForLoop() time::0.003368sec countDigit() digit::6 time::0.066714sec countDigitUsingLog() digit::6 time::0.000001sec countDigitPoor() digit::6 time::0.000001sec countDigitBinary() digit::6 time::0.000000sec N = 1234567 countForLoop() time::0.003355sec countDigit() digit::7 time::0.071519sec countDigitUsingLog() digit::7 time::0.000001sec countDigitPoor() digit::7 time::0.000001sec countDigitBinary() digit::7 time::0.000000sec N = 12345678 countForLoop() time::0.005837sec countDigit() digit::8 time::0.093607sec countDigitUsingLog() digit::8 time::0.000001sec countDigitPoor() digit::8 time::0.000000sec countDigitBinary() digit::8 time::0.000000sec N = 123456789 countForLoop() time::0.003542sec countDigit() digit::9 time::0.107566sec countDigitUsingLog() digit::9 time::0.000002sec countDigitPoor() digit::9 time::0.000002sec countDigitBinary() digit::9 time::0.000001sec
……速くなった……でも、桁数の小さいときも速くなってるように見えるのはなんでだろう?
投稿2017/01/23 04:07
編集2017/01/23 04:51総合スコア4443
誰かやらないかと待っていたら本当にやってくれたので+1
BAうれしいです。が、平均計算量では「貧者」とタメのはずなので、Cの整数型くらいの桁数ならそちらでいいかな、と。
あと、書いてから気づきましたが、二分探索のアイディアはmajiponiさんがすでに書いておられました。あと2進対数 (要はビット数ですね) を使うやり方というのはどんなものなのか、興味があります。
0
こんにちは。
数回くらいの除算や1回のlog10計算にかかる時間は短すぎてclock()関数ではとても測れません。10,000,000回ほど繰り返して計測してみました。(utunbu 16.04 LTS on VirtualBox)
圧倒的に10で割る方が早いです。
32ビットであれば、このまま10で割る方が勝つと思います。
64ビットならば、どこかで逆転すると思います。
C
1#include <stdio.h> 2#include <math.h> 3#include <time.h> 4 5void countForLoop() 6{ 7 clock_t start,end; 8 volatile int x=1; 9 10 start = clock(); 11 12 for (size_t i=0; i < 10000000; ++i) 13 { 14 x=i; 15 } 16 17 end = clock(); 18 19 printf("countForLoop() time::%fsec\n",((double)end - start)/CLOCKS_PER_SEC); 20} 21 22void countDigit(int n) 23{ 24 int digit = 1; 25 clock_t start,end; 26 27 start = clock(); 28 29 for (size_t i=0; i < 10000000; ++i) 30 { 31 digit=1; 32 int x=n; 33 while((x /= 10) != 0) 34 digit++; 35 } 36 37 end = clock(); 38 39 printf("countDigit() digit::%d time::%fsec\n",digit,((double)end - start)/CLOCKS_PER_SEC); 40} 41 42void countDigitUsingLog(int n) 43{ 44 clock_t start,end; 45 int digit; 46 47 start = clock(); 48 49 for (size_t i=0; i < 10000000; ++i) 50 digit = log10(n) + 1; 51 52 end = clock(); 53 printf("countDigitUsingLog() digit::%d time::%fsec\n",digit,((double)end - start)/CLOCKS_PER_SEC); 54} 55 56int main(void) 57{ 58 int n = 0; 59 int i; 60 61 for(i = 1;i < 10;i++) { 62 n = n * 10 + i; 63 printf("N = %d\n",n); 64 countForLoop(); 65 countDigit(n); 66 countDigitUsingLog(n); 67 printf("\n"); 68 } 69 70 return 0; 71}
txt
1N = 1 2countForLoop() time::0.003324sec 3countDigit() digit::1 time::0.005868sec 4countDigitUsingLog() digit::1 time::0.592562sec 5 6N = 12 7countForLoop() time::0.003532sec 8countDigit() digit::2 time::0.015215sec 9countDigitUsingLog() digit::2 time::0.880503sec 10 11N = 123 12countForLoop() time::0.002862sec 13countDigit() digit::3 time::0.027572sec 14countDigitUsingLog() digit::3 time::0.875855sec 15 16N = 1234 17countForLoop() time::0.002556sec 18countDigit() digit::4 time::0.041923sec 19countDigitUsingLog() digit::4 time::0.857530sec 20 21N = 12345 22countForLoop() time::0.003236sec 23countDigit() digit::5 time::0.057147sec 24countDigitUsingLog() digit::5 time::0.872361sec 25 26N = 123456 27countForLoop() time::0.002726sec 28countDigit() digit::6 time::0.074915sec 29countDigitUsingLog() digit::6 time::0.875790sec 30 31N = 1234567 32countForLoop() time::0.002834sec 33countDigit() digit::7 time::0.089634sec 34countDigitUsingLog() digit::7 time::0.862718sec 35 36N = 12345678 37countForLoop() time::0.002489sec 38countDigit() digit::8 time::0.110157sec 39countDigitUsingLog() digit::8 time::0.879816sec 40 41N = 123456789 42countForLoop() time::0.003085sec 43countDigit() digit::9 time::0.125394sec 44countDigitUsingLog() digit::9 time::0.876311sec
投稿2017/01/22 15:08
編集2017/01/22 15:26
総合スコア23272
0
sprintfを使う方法もあります。
c
1void countDigitUsingSprintf(int n) 2{ 3 clock_t start,end; 4 int digit; 5 char dummy[10]; 6 7 start = clock(); 8 9 digit = sprintf(dummy, "%d", n); 10 11 end = clock(); 12 printf("countDigitUsingSptintf() digit::%d time::%dms\n",digit,(int)(end - start)); 13}
速い遅いは環境や入力データに依存してしまうのかな。
投稿2017/01/23 04:56
総合スコア6621
0
atoi関数定義で文字列にして、strlenで文字列の長さを求める。
あっ！コーディングか早いだけです、、、
投稿2017/01/22 23:46
編集2017/01/22 23:47
総合スコア648
0
最適なアルゴリズムは時と場合により変わります。例えば、小さな数の入力がほとんどであれば、割り算の繰り返しのほうが圧倒的に速いです。が、入力が完全なランダムであれば、桁数が大きい入力が増えるので、常用対数のほうが有利になることもあります。なので、どちらが速いかという質問の答えは、使い方次第となります。
ちなみに私が最初に思いついたのは、2進対数(切り捨て)を出して10進だとどうなるか調べる方法、それから二分探索です。
投稿2017/01/22 15:53
総合スコア1722
あなたの回答
tips
プレビュー
