teratail
回答率
85.36%
teratail 10th-anniversary
teratail 10th-anniversary
質問するログイン新規登録
トップCに関する質問C/C++で整数の桁数を求める場合、１番処理が速いのはどの方法でしょうか？

編集履歴

回答編集履歴

4

コード修正しました。でも速いなあ。なぜ\?

2017/01/23 04:51

投稿

ikedas
ikedas

スコア4443

test CHANGED
@@ -1,7 +1,7 @@
1
1
  sharowさんの「貧者のアルゴリズム」では最悪計算量が`O(log n)`ですが、二分探索にすると`O(log log n)`に減らせます!
2
2
 
3
3
  ```lang-c
4
- int
4
+ int
5
5
  digitBinary(int n)
6
6
  {
7
7
  if (n < 100000) {
@@ -35,18 +35,18 @@
35
35
  }
36
36
  }
37
37
 
38
- void
38
+ void
39
39
  countDigitBinary(int n)
40
- {
40
+ {
41
- clock start , end;
41
+ clock_t start,end;
42
- int digit;
42
+ int digit;
43
-
43
+
44
- start = clock();
44
+ start = clock();
45
- for (size i = 0; i < 10000000; ++i) {
45
+ for (size_t i=0; i < 10000000; ++i) {
46
- digit = digitPoor(n);
46
+ digit = digitBinary(n);
47
47
  }
48
48
  end = clock();
49
- printf("countDigitBinary() digit::%d time::%fsec\n", digit, ((double)end - start) / CLOCKS_PER_SEC);
49
+ printf("countDigitBinary() digit::%d time::%fsec\n",digit,((double)end - start)/CLOCKS_PER_SEC);
50
50
  }
51
51
  ```
52
52
 
@@ -63,134 +63,134 @@
63
63
 
64
64
  ```
65
65
  N = 1
66
- countForLoop() time::0.022950sec
66
+ countForLoop() time::0.023104sec
67
- countDigit() digit::1 time::0.047975sec
67
+ countDigit() digit::1 time::0.047660sec
68
- countDigitUsingLog() digit::1 time::0.244019sec
68
+ countDigitUsingLog() digit::1 time::0.246963sec
69
- countDigitPoor() digit::1 time::0.040802sec
69
+ countDigitPoor() digit::1 time::0.037537sec
70
- countDigitBinary() digit::1 time::0.033143sec
70
+ countDigitBinary() digit::1 time::0.039012sec
71
71
 
72
72
  N = 12
73
- countForLoop() time::0.024643sec
73
+ countForLoop() time::0.023421sec
74
- countDigit() digit::2 time::0.082038sec
74
+ countDigit() digit::2 time::0.084005sec
75
- countDigitUsingLog() digit::2 time::0.240760sec
75
+ countDigitUsingLog() digit::2 time::0.233920sec
76
- countDigitPoor() digit::2 time::0.048678sec
76
+ countDigitPoor() digit::2 time::0.051066sec
77
- countDigitBinary() digit::2 time::0.047829sec
77
+ countDigitBinary() digit::2 time::0.043674sec
78
78
 
79
79
  N = 123
80
- countForLoop() time::0.022539sec
80
+ countForLoop() time::0.025515sec
81
- countDigit() digit::3 time::0.122099sec
81
+ countDigit() digit::3 time::0.117607sec
82
- countDigitUsingLog() digit::3 time::0.236290sec
82
+ countDigitUsingLog() digit::3 time::0.236735sec
83
- countDigitPoor() digit::3 time::0.052775sec
83
+ countDigitPoor() digit::3 time::0.053296sec
84
- countDigitBinary() digit::3 time::0.052692sec
84
+ countDigitBinary() digit::3 time::0.051939sec
85
85
 
86
86
  N = 1234
87
- countForLoop() time::0.022707sec
87
+ countForLoop() time::0.025521sec
88
- countDigit() digit::4 time::0.173149sec
88
+ countDigit() digit::4 time::0.173296sec
89
- countDigitUsingLog() digit::4 time::0.241182sec
89
+ countDigitUsingLog() digit::4 time::0.234089sec
90
- countDigitPoor() digit::4 time::0.065699sec
90
+ countDigitPoor() digit::4 time::0.060343sec
91
- countDigitBinary() digit::4 time::0.054667sec
91
+ countDigitBinary() digit::4 time::0.045750sec
92
92
 
93
93
  N = 12345
94
- countForLoop() time::0.026085sec
94
+ countForLoop() time::0.025067sec
95
- countDigit() digit::5 time::0.224581sec
95
+ countDigit() digit::5 time::0.224774sec
96
- countDigitUsingLog() digit::5 time::0.236559sec
96
+ countDigitUsingLog() digit::5 time::0.236502sec
97
- countDigitPoor() digit::5 time::0.072343sec
97
+ countDigitPoor() digit::5 time::0.070013sec
98
- countDigitBinary() digit::5 time::0.069892sec
98
+ countDigitBinary() digit::5 time::0.051067sec
99
99
 
100
100
  N = 123456
101
- countForLoop() time::0.024668sec
101
+ countForLoop() time::0.024541sec
102
- countDigit() digit::6 time::0.297632sec
102
+ countDigit() digit::6 time::0.300018sec
103
- countDigitUsingLog() digit::6 time::0.241746sec
103
+ countDigitUsingLog() digit::6 time::0.236935sec
104
- countDigitPoor() digit::6 time::0.084354sec
104
+ countDigitPoor() digit::6 time::0.084706sec
105
- countDigitBinary() digit::6 time::0.084627sec
105
+ countDigitBinary() digit::6 time::0.043754sec
106
106
 
107
107
  N = 1234567
108
- countForLoop() time::0.024655sec
108
+ countForLoop() time::0.026226sec
109
- countDigit() digit::7 time::0.363861sec
109
+ countDigit() digit::7 time::0.365955sec
110
- countDigitUsingLog() digit::7 time::0.234623sec
110
+ countDigitUsingLog() digit::7 time::0.241753sec
111
- countDigitPoor() digit::7 time::0.083174sec
111
+ countDigitPoor() digit::7 time::0.082430sec
112
- countDigitBinary() digit::7 time::0.081885sec
112
+ countDigitBinary() digit::7 time::0.049685sec
113
113
 
114
114
  N = 12345678
115
- countForLoop() time::0.024638sec
115
+ countForLoop() time::0.025289sec
116
- countDigit() digit::8 time::0.422116sec
116
+ countDigit() digit::8 time::0.430325sec
117
- countDigitUsingLog() digit::8 time::0.242134sec
117
+ countDigitUsingLog() digit::8 time::0.236876sec
118
- countDigitPoor() digit::8 time::0.090548sec
118
+ countDigitPoor() digit::8 time::0.094294sec
119
- countDigitBinary() digit::8 time::0.085079sec
119
+ countDigitBinary() digit::8 time::0.050104sec
120
120
 
121
121
  N = 123456789
122
- countForLoop() time::0.027161sec
122
+ countForLoop() time::0.026642sec
123
- countDigit() digit::9 time::0.504405sec
123
+ countDigit() digit::9 time::0.513616sec
124
- countDigitUsingLog() digit::9 time::0.237745sec
124
+ countDigitUsingLog() digit::9 time::0.237418sec
125
- countDigitPoor() digit::9 time::0.097997sec
125
+ countDigitPoor() digit::9 time::0.097828sec
126
- countDigitBinary() digit::9 time::0.094996sec
126
+ countDigitBinary() digit::9 time::0.061868sec
127
127
  ```
128
128
 
129
129
  `clang -Ofast`
130
130
 
131
131
  ```
132
132
  N = 1
133
- countForLoop() time::0.003539sec
133
+ countForLoop() time::0.004516sec
134
- countDigit() digit::1 time::0.000001sec
134
+ countDigit() digit::1 time::0.000000sec
135
- countDigitUsingLog() digit::1 time::0.000035sec
135
+ countDigitUsingLog() digit::1 time::0.000039sec
136
136
  countDigitPoor() digit::1 time::0.000000sec
137
137
  countDigitBinary() digit::1 time::0.000000sec
138
138
 
139
139
  N = 12
140
- countForLoop() time::0.003392sec
140
+ countForLoop() time::0.003351sec
141
- countDigit() digit::2 time::0.011977sec
141
+ countDigit() digit::2 time::0.011395sec
142
- countDigitUsingLog() digit::2 time::0.000002sec
142
+ countDigitUsingLog() digit::2 time::0.000001sec
143
- countDigitPoor() digit::2 time::0.000001sec
143
+ countDigitPoor() digit::2 time::0.000000sec
144
144
  countDigitBinary() digit::2 time::0.000000sec
145
145
 
146
146
  N = 123
147
- countForLoop() time::0.005974sec
147
+ countForLoop() time::0.003504sec
148
- countDigit() digit::3 time::0.019831sec
148
+ countDigit() digit::3 time::0.020016sec
149
- countDigitUsingLog() digit::3 time::0.000000sec
149
+ countDigitUsingLog() digit::3 time::0.000002sec
150
- countDigitPoor() digit::3 time::0.000000sec
150
+ countDigitPoor() digit::3 time::0.000001sec
151
151
  countDigitBinary() digit::3 time::0.000000sec
152
152
 
153
153
  N = 1234
154
- countForLoop() time::0.004375sec
154
+ countForLoop() time::0.005942sec
155
- countDigit() digit::4 time::0.036558sec
155
+ countDigit() digit::4 time::0.033859sec
156
- countDigitUsingLog() digit::4 time::0.000001sec
156
+ countDigitUsingLog() digit::4 time::0.000002sec
157
- countDigitPoor() digit::4 time::0.000000sec
157
+ countDigitPoor() digit::4 time::0.000001sec
158
158
  countDigitBinary() digit::4 time::0.000000sec
159
159
 
160
160
  N = 12345
161
- countForLoop() time::0.003414sec
161
+ countForLoop() time::0.003354sec
162
- countDigit() digit::5 time::0.051762sec
162
+ countDigit() digit::5 time::0.050976sec
163
- countDigitUsingLog() digit::5 time::0.000000sec
163
+ countDigitUsingLog() digit::5 time::0.000001sec
164
- countDigitPoor() digit::5 time::0.000000sec
164
+ countDigitPoor() digit::5 time::0.000001sec
165
- countDigitBinary() digit::5 time::0.000000sec
165
+ countDigitBinary() digit::5 time::0.000002sec
166
166
 
167
167
  N = 123456
168
- countForLoop() time::0.004665sec
168
+ countForLoop() time::0.003368sec
169
- countDigit() digit::6 time::0.068558sec
169
+ countDigit() digit::6 time::0.066714sec
170
170
  countDigitUsingLog() digit::6 time::0.000001sec
171
- countDigitPoor() digit::6 time::0.000000sec
171
+ countDigitPoor() digit::6 time::0.000001sec
172
172
  countDigitBinary() digit::6 time::0.000000sec
173
173
 
174
174
  N = 1234567
175
- countForLoop() time::0.003357sec
175
+ countForLoop() time::0.003355sec
176
- countDigit() digit::7 time::0.077268sec
176
+ countDigit() digit::7 time::0.071519sec
177
- countDigitUsingLog() digit::7 time::0.000000sec
177
+ countDigitUsingLog() digit::7 time::0.000001sec
178
- countDigitPoor() digit::7 time::0.000000sec
178
+ countDigitPoor() digit::7 time::0.000001sec
179
179
  countDigitBinary() digit::7 time::0.000000sec
180
180
 
181
181
  N = 12345678
182
- countForLoop() time::0.003348sec
182
+ countForLoop() time::0.005837sec
183
- countDigit() digit::8 time::0.087896sec
183
+ countDigit() digit::8 time::0.093607sec
184
184
  countDigitUsingLog() digit::8 time::0.000001sec
185
185
  countDigitPoor() digit::8 time::0.000000sec
186
186
  countDigitBinary() digit::8 time::0.000000sec
187
187
 
188
188
  N = 123456789
189
- countForLoop() time::0.003336sec
189
+ countForLoop() time::0.003542sec
190
- countDigit() digit::9 time::0.100265sec
190
+ countDigit() digit::9 time::0.107566sec
191
- countDigitUsingLog() digit::9 time::0.000000sec
191
+ countDigitUsingLog() digit::9 time::0.000002sec
192
192
  countDigitPoor() digit::9 time::0.000002sec
193
- countDigitBinary() digit::9 time::0.000000sec
193
+ countDigitBinary() digit::9 time::0.000001sec
194
194
  ```
195
195
 
196
196
  ……速くなった……でも、桁数の小さいときも速くなってるように見えるのはなんでだろう?

3

〆の言葉修正

2017/01/23 04:51

投稿

ikedas
ikedas

スコア4443

test CHANGED
@@ -193,5 +193,5 @@
193
193
  countDigitBinary() digit::9 time::0.000000sec
194
194
  ```
195
195
 
196
- ……速くなった……のかな。よくわからない……。
196
+ ……速くなった……でも、桁数の小さいときも速くなってるように見えるのはなんでだろう?
197
197
 

2

微修正

2017/01/23 04:40

投稿

ikedas
ikedas

スコア4443

test CHANGED
@@ -4,9 +4,6 @@
4
4
  int
5
5
  digitBinary(int n)
6
6
  {
7
- //assert(INT_MAX == 2147483647);
8
- //assert(n >= 0);
9
-
10
7
  if (n < 100000) {
11
8
  if (n < 1000) {
12
9
  if (n < 10)

1

indent

2017/01/23 04:19

投稿

ikedas
ikedas

スコア4443

test CHANGED
@@ -1,50 +1,55 @@
1
1
  sharowさんの「貧者のアルゴリズム」では最悪計算量が`O(log n)`ですが、二分探索にすると`O(log log n)`に減らせます!
2
2
 
3
3
  ```lang-c
4
+ int
4
- int digitBinary(int n)
5
+ digitBinary(int n)
5
6
  {
7
+ //assert(INT_MAX == 2147483647);
8
+ //assert(n >= 0);
9
+
6
10
  if (n < 100000) {
7
- if (n < 1000) {
11
+ if (n < 1000) {
8
- if (n < 10)
12
+ if (n < 10)
9
- return 1;
13
+ return 1;
10
- else if (n < 100)
14
+ else if (n < 100)
11
- return 2;
15
+ return 2;
12
- else
16
+ else
13
- return 3;
17
+ return 3;
14
- } else {
18
+ } else {
15
- if (n < 10000)
19
+ if (n < 10000)
16
- return 4;
20
+ return 4;
17
- else
21
+ else
18
- return 5;
22
+ return 5;
19
- }
23
+ }
20
24
  } else {
21
- if (n < 10000000) {
25
+ if (n < 10000000) {
22
- if (n < 1000000)
26
+ if (n < 1000000)
23
- return 6;
27
+ return 6;
24
- else
28
+ else
25
- return 7;
29
+ return 7;
26
- } else {
30
+ } else {
27
- if (n < 100000000)
31
+ if (n < 100000000)
28
- return 8;
32
+ return 8;
29
- else if (n < 1000000000)
33
+ else if (n < 1000000000)
30
- return 9;
34
+ return 9;
31
- else
35
+ else
32
- return 10;
36
+ return 10;
33
- }
37
+ }
34
38
  }
35
39
  }
36
40
 
41
+ void
37
- void countDigitBinary(int n)
42
+ countDigitBinary(int n)
38
43
  {
39
- clock_t start,end;
44
+ clock start , end;
40
- int digit;
45
+ int digit;
41
46
 
42
47
  start = clock();
43
- for (size_t i=0; i < 10000000; ++i) {
48
+ for (size i = 0; i < 10000000; ++i) {
44
49
  digit = digitPoor(n);
45
50
  }
46
51
  end = clock();
47
- printf("countDigitBinary() digit::%d time::%fsec\n",digit,((double)end - start)/CLOCKS_PER_SEC);
52
+ printf("countDigitBinary() digit::%d time::%fsec\n", digit, ((double)end - start) / CLOCKS_PER_SEC);
48
53
  }
49
54
  ```
50
55