質問編集履歴

追記

2017/01/23 14:17

投稿

yama_da

スコア73

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -197,3 +197,517 @@
 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
+#include <stdio.h>
+#include <math.h>
+#include <time.h>
+#include <limits.h>
+#include <assert.h>
+#define LOOP 10000000
+void countDigit(int n)
+{
+  int digit = 1;
+  clock_t start,end;
+  start = clock();
+  for(size_t i = 0;i < LOOP; ++i) {
+    while((n /= 10) != 0)
+      digit++;
+  }
+  end = clock();
+  printf("%-25s\tdigit::%d\ttime::%fs\n",
+	 "countDigit()",digit,((double)end - start)/CLOCKS_PER_SEC);
+}
+void countDigitUsingLog(int n)
+{
+  clock_t start,end;
+  int digit;
+  start = clock();
+  for(size_t i = 0;i < LOOP; ++i)
+  digit = log10(n) + 1;
+  end = clock();
+  printf("%-25s\tdigit::%d\ttime::%fs\n",
+	 "countDigitUsingLog()",digit,((double)end - start)/CLOCKS_PER_SEC);
+}
+void countDigitBinary(int n)
+{
+      int digit;
+  clock_t start,end;
+  start = clock();
+  for(size_t i = 0;i < LOOP; ++i) {
+    if (n < 100000) {
+      if (n < 1000) {
+    	if (n < 10)
+    	  digit = 1;
+    	else if (n < 100)
+    	  digit = 2;
+    	else
+    	  digit = 3;
+      } else {
+    	if (n < 10000)
+    	  digit = 4;
+    	else
+    	  digit = 5;
+      }
+    } else {
+      if (n < 10000000) {
+    	if (n < 1000000)
+    	  digit = 6;
+    	else
+    	  digit = 7;
+      } else {
+    	if (n < 100000000)
+    	  digit = 8;
+    	else if (n < 1000000000)
+    	  digit = 9;
+    	else
+    	  digit = 10;
+      }
+    }
+  }
+  end = clock();
+  printf("%-25s\tdigit::%d\ttime::%fs\n",
+	 "countDigitBinary()",digit,((double)end - start)/CLOCKS_PER_SEC);
+}
+int digitPoor(int n)
+{
+    assert(INT_MAX == 2147483647);
+    assert(n >= 0);
+    if (n < 10)         return 1;
+    if (n < 100)        return 2;
+    if (n < 1000)       return 3;
+    if (n < 10000)      return 4;
+    if (n < 100000)     return 5;
+    if (n < 1000000)    return 6;
+    if (n < 10000000)   return 7;
+    if (n < 100000000)  return 8;
+    if (n < 1000000000) return 9;
+    return 10;
+}
+void countDigitPoor(int n)
+{
+    clock_t start,end;
+    int digit;
+    start = clock();
+    for (size_t i=0; i < 10000000; ++i) {
+        digit = digitPoor(n);
+    }
+    end = clock();
+    printf("%-25s\tdigit::%d\ttime::%fs\n",
+	   "countDigitPoor()",digit,((double)end - start)/CLOCKS_PER_SEC);
+}
+void countDigitUsingSprintf(int n)
+{
+  clock_t start,end;
+  int digit;
+  char dummy[10];
+  start = clock();
+  for(size_t i = 0;i < LOOP; ++i)
+  digit = sprintf(dummy, "%d", n);
+  end = clock();
+  printf("%-25s\tdigit::%d\ttime::%fs\n",
+	 "countDigitUsingSprintf()",digit,((double)end - start)/CLOCKS_PER_SEC);
+}
+void countForLoop()
+{
+  clock_t start,end;
+  volatile int x=1;
+  start = clock();
+  for (size_t i = 0; i < LOOP; ++i)
+    {
+      x=i;
+    }
+  end = clock();
+  printf("%-25s\t--------\ttime::%fs\n",
+	 "countForLoop()",((double)end - start)/CLOCKS_PER_SEC);
+}
+int main(void)
+{
+  int n = 0;
+  int i;
+  for(i = 1;i < 10;i++) {
+    n = n * 10 + i;
+    printf("N = %d\n",n);
+    countForLoop();
+    countDigit(n);
+    countDigitUsingLog(n);
+    countDigitBinary(n);
+    countDigitPoor(n);
+    countDigitUsingSprintf(n);
+    printf("\n");
+  }
+  return 0;
+}
+```
+```ここに言語を入力
+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
+```