質問編集履歴
1
追記
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -97,4 +97,261 @@
|
|
|
97
97
|
<実行環境>
|
|
98
98
|
Ubuntu 16.04 LTS
|
|
99
99
|
CPU : AMD A4-5000 APU with Radeon(TM) HD Graphics
|
|
100
|
-
gcc version 5.4.1 20160904 (Ubuntu 5.4.1-2ubuntu1~16.04)
|
|
100
|
+
gcc version 5.4.1 20160904 (Ubuntu 5.4.1-2ubuntu1~16.04)
|
|
101
|
+
|
|
102
|
+
|
|
103
|
+
<2017/1/23 追記>
|
|
104
|
+
皆さん回答ありがとうございました！ikedasさんのものとほとんど変わりませんが、皆さんが回答してくださったものを一通り僕の環境でも試してみました。与えられる整数値の桁数の範囲が分かっているなら、２分探索が一番良さそうです。とても勉強になりました、みなさん本当にありがとうございました！以下修正版と結果です。
|
|
105
|
+
|
|
106
|
+
```C
|
|
107
|
+
#include <stdio.h>
|
|
108
|
+
#include <math.h>
|
|
109
|
+
#include <time.h>
|
|
110
|
+
#include <limits.h>
|
|
111
|
+
#include <assert.h>
|
|
112
|
+
|
|
113
|
+
#define LOOP 10000000
|
|
114
|
+
|
|
115
|
+
|
|
116
|
+
void countDigit(int n)
|
|
117
|
+
{
|
|
118
|
+
int digit = 1;
|
|
119
|
+
clock_t start,end;
|
|
120
|
+
|
|
121
|
+
start = clock();
|
|
122
|
+
|
|
123
|
+
for(size_t i = 0;i < LOOP; ++i) {
|
|
124
|
+
while((n /= 10) != 0)
|
|
125
|
+
digit++;
|
|
126
|
+
}
|
|
127
|
+
|
|
128
|
+
end = clock();
|
|
129
|
+
|
|
130
|
+
printf("%-25s\tdigit::%d\ttime::%fs\n",
|
|
131
|
+
"countDigit()",digit,((double)end - start)/CLOCKS_PER_SEC);
|
|
132
|
+
}
|
|
133
|
+
|
|
134
|
+
void countDigitUsingLog(int n)
|
|
135
|
+
{
|
|
136
|
+
clock_t start,end;
|
|
137
|
+
int digit;
|
|
138
|
+
|
|
139
|
+
start = clock();
|
|
140
|
+
|
|
141
|
+
for(size_t i = 0;i < LOOP; ++i)
|
|
142
|
+
digit = log10(n) + 1;
|
|
143
|
+
|
|
144
|
+
end = clock();
|
|
145
|
+
|
|
146
|
+
printf("%-25s\tdigit::%d\ttime::%fs\n",
|
|
147
|
+
"countDigitUsingLog()",digit,((double)end - start)/CLOCKS_PER_SEC);
|
|
148
|
+
}
|
|
149
|
+
|
|
150
|
+
void countDigitBinary(int n)
|
|
151
|
+
{
|
|
152
|
+
int digit;
|
|
153
|
+
clock_t start,end;
|
|
154
|
+
|
|
155
|
+
start = clock();
|
|
156
|
+
|
|
157
|
+
for(size_t i = 0;i < LOOP; ++i) {
|
|
158
|
+
|
|
159
|
+
if (n < 100000) {
|
|
160
|
+
if (n < 1000) {
|
|
161
|
+
if (n < 10)
|
|
162
|
+
digit = 1;
|
|
163
|
+
else if (n < 100)
|
|
164
|
+
digit = 2;
|
|
165
|
+
else
|
|
166
|
+
digit = 3;
|
|
167
|
+
} else {
|
|
168
|
+
if (n < 10000)
|
|
169
|
+
digit = 4;
|
|
170
|
+
else
|
|
171
|
+
digit = 5;
|
|
172
|
+
}
|
|
173
|
+
} else {
|
|
174
|
+
if (n < 10000000) {
|
|
175
|
+
if (n < 1000000)
|
|
176
|
+
digit = 6;
|
|
177
|
+
else
|
|
178
|
+
digit = 7;
|
|
179
|
+
} else {
|
|
180
|
+
if (n < 100000000)
|
|
181
|
+
digit = 8;
|
|
182
|
+
else if (n < 1000000000)
|
|
183
|
+
digit = 9;
|
|
184
|
+
else
|
|
185
|
+
digit = 10;
|
|
186
|
+
}
|
|
187
|
+
}
|
|
188
|
+
}
|
|
189
|
+
|
|
190
|
+
|
|
191
|
+
end = clock();
|
|
192
|
+
|
|
193
|
+
printf("%-25s\tdigit::%d\ttime::%fs\n",
|
|
194
|
+
"countDigitBinary()",digit,((double)end - start)/CLOCKS_PER_SEC);
|
|
195
|
+
}
|
|
196
|
+
|
|
197
|
+
int digitPoor(int n)
|
|
198
|
+
{
|
|
199
|
+
assert(INT_MAX == 2147483647);
|
|
200
|
+
assert(n >= 0);
|
|
201
|
+
|
|
202
|
+
if (n < 10) return 1;
|
|
203
|
+
if (n < 100) return 2;
|
|
204
|
+
if (n < 1000) return 3;
|
|
205
|
+
if (n < 10000) return 4;
|
|
206
|
+
if (n < 100000) return 5;
|
|
207
|
+
if (n < 1000000) return 6;
|
|
208
|
+
if (n < 10000000) return 7;
|
|
209
|
+
if (n < 100000000) return 8;
|
|
210
|
+
if (n < 1000000000) return 9;
|
|
211
|
+
return 10;
|
|
212
|
+
}
|
|
213
|
+
|
|
214
|
+
void countDigitPoor(int n)
|
|
215
|
+
{
|
|
216
|
+
clock_t start,end;
|
|
217
|
+
int digit;
|
|
218
|
+
|
|
219
|
+
start = clock();
|
|
220
|
+
for (size_t i=0; i < 10000000; ++i) {
|
|
221
|
+
digit = digitPoor(n);
|
|
222
|
+
}
|
|
223
|
+
end = clock();
|
|
224
|
+
printf("%-25s\tdigit::%d\ttime::%fs\n",
|
|
225
|
+
"countDigitPoor()",digit,((double)end - start)/CLOCKS_PER_SEC);
|
|
226
|
+
}
|
|
227
|
+
|
|
228
|
+
void countDigitUsingSprintf(int n)
|
|
229
|
+
{
|
|
230
|
+
clock_t start,end;
|
|
231
|
+
int digit;
|
|
232
|
+
char dummy[10];
|
|
233
|
+
|
|
234
|
+
start = clock();
|
|
235
|
+
|
|
236
|
+
for(size_t i = 0;i < LOOP; ++i)
|
|
237
|
+
digit = sprintf(dummy, "%d", n);
|
|
238
|
+
|
|
239
|
+
end = clock();
|
|
240
|
+
printf("%-25s\tdigit::%d\ttime::%fs\n",
|
|
241
|
+
"countDigitUsingSprintf()",digit,((double)end - start)/CLOCKS_PER_SEC);
|
|
242
|
+
}
|
|
243
|
+
|
|
244
|
+
void countForLoop()
|
|
245
|
+
{
|
|
246
|
+
clock_t start,end;
|
|
247
|
+
volatile int x=1;
|
|
248
|
+
|
|
249
|
+
start = clock();
|
|
250
|
+
|
|
251
|
+
for (size_t i = 0; i < LOOP; ++i)
|
|
252
|
+
{
|
|
253
|
+
x=i;
|
|
254
|
+
}
|
|
255
|
+
|
|
256
|
+
end = clock();
|
|
257
|
+
|
|
258
|
+
printf("%-25s\t--------\ttime::%fs\n",
|
|
259
|
+
"countForLoop()",((double)end - start)/CLOCKS_PER_SEC);
|
|
260
|
+
}
|
|
261
|
+
|
|
262
|
+
int main(void)
|
|
263
|
+
{
|
|
264
|
+
int n = 0;
|
|
265
|
+
int i;
|
|
266
|
+
|
|
267
|
+
for(i = 1;i < 10;i++) {
|
|
268
|
+
n = n * 10 + i;
|
|
269
|
+
printf("N = %d\n",n);
|
|
270
|
+
countForLoop();
|
|
271
|
+
countDigit(n);
|
|
272
|
+
countDigitUsingLog(n);
|
|
273
|
+
countDigitBinary(n);
|
|
274
|
+
countDigitPoor(n);
|
|
275
|
+
countDigitUsingSprintf(n);
|
|
276
|
+
printf("\n");
|
|
277
|
+
}
|
|
278
|
+
|
|
279
|
+
return 0;
|
|
280
|
+
}
|
|
281
|
+
|
|
282
|
+
```
|
|
283
|
+
|
|
284
|
+
```ここに言語を入力
|
|
285
|
+
N = 1
|
|
286
|
+
countForLoop() -------- time::0.045770s
|
|
287
|
+
countDigit() digit::1 time::0.100439s
|
|
288
|
+
countDigitUsingLog() digit::1 time::0.378452s
|
|
289
|
+
countDigitBinary() digit::1 time::0.053568s
|
|
290
|
+
countDigitPoor() digit::1 time::0.079120s
|
|
291
|
+
countDigitUsingSprintf() digit::1 time::2.265236s
|
|
292
|
+
|
|
293
|
+
N = 12
|
|
294
|
+
countForLoop() -------- time::0.043182s
|
|
295
|
+
countDigit() digit::2 time::0.100408s
|
|
296
|
+
countDigitUsingLog() digit::2 time::1.012793s
|
|
297
|
+
countDigitBinary() digit::2 time::0.060286s
|
|
298
|
+
countDigitPoor() digit::2 time::0.092724s
|
|
299
|
+
countDigitUsingSprintf() digit::2 time::2.341804s
|
|
300
|
+
|
|
301
|
+
N = 123
|
|
302
|
+
countForLoop() -------- time::0.042746s
|
|
303
|
+
countDigit() digit::3 time::0.100416s
|
|
304
|
+
countDigitUsingLog() digit::3 time::1.004158s
|
|
305
|
+
countDigitBinary() digit::3 time::0.060143s
|
|
306
|
+
countDigitPoor() digit::3 time::0.108729s
|
|
307
|
+
countDigitUsingSprintf() digit::3 time::2.442325s
|
|
308
|
+
|
|
309
|
+
N = 1234
|
|
310
|
+
countForLoop() -------- time::0.045008s
|
|
311
|
+
countDigit() digit::4 time::0.100400s
|
|
312
|
+
countDigitUsingLog() digit::4 time::1.004526s
|
|
313
|
+
countDigitBinary() digit::4 time::0.048930s
|
|
314
|
+
countDigitPoor() digit::4 time::0.132441s
|
|
315
|
+
countDigitUsingSprintf() digit::4 time::2.530141s
|
|
316
|
+
|
|
317
|
+
N = 12345
|
|
318
|
+
countForLoop() -------- time::0.042238s
|
|
319
|
+
countDigit() digit::5 time::0.100400s
|
|
320
|
+
countDigitUsingLog() digit::5 time::1.008050s
|
|
321
|
+
countDigitBinary() digit::5 time::0.060654s
|
|
322
|
+
countDigitPoor() digit::5 time::0.144062s
|
|
323
|
+
countDigitUsingSprintf() digit::5 time::2.624742s
|
|
324
|
+
|
|
325
|
+
N = 123456
|
|
326
|
+
countForLoop() -------- time::0.042451s
|
|
327
|
+
countDigit() digit::6 time::0.100724s
|
|
328
|
+
countDigitUsingLog() digit::6 time::1.008027s
|
|
329
|
+
countDigitBinary() digit::6 time::0.058717s
|
|
330
|
+
countDigitPoor() digit::6 time::0.177779s
|
|
331
|
+
countDigitUsingSprintf() digit::6 time::2.751899s
|
|
332
|
+
|
|
333
|
+
N = 1234567
|
|
334
|
+
countForLoop() -------- time::0.041235s
|
|
335
|
+
countDigit() digit::7 time::0.100376s
|
|
336
|
+
countDigitUsingLog() digit::7 time::1.004352s
|
|
337
|
+
countDigitBinary() digit::7 time::0.069315s
|
|
338
|
+
countDigitPoor() digit::7 time::0.193293s
|
|
339
|
+
countDigitUsingSprintf() digit::7 time::2.825540s
|
|
340
|
+
|
|
341
|
+
N = 12345678
|
|
342
|
+
countForLoop() -------- time::0.041624s
|
|
343
|
+
countDigit() digit::8 time::0.100474s
|
|
344
|
+
countDigitUsingLog() digit::8 time::1.004698s
|
|
345
|
+
countDigitBinary() digit::8 time::0.075757s
|
|
346
|
+
countDigitPoor() digit::8 time::0.215140s
|
|
347
|
+
countDigitUsingSprintf() digit::8 time::2.937961s
|
|
348
|
+
|
|
349
|
+
N = 123456789
|
|
350
|
+
countForLoop() -------- time::0.043923s
|
|
351
|
+
countDigit() digit::9 time::0.100387s
|
|
352
|
+
countDigitUsingLog() digit::9 time::1.004096s
|
|
353
|
+
countDigitBinary() digit::9 time::0.094569s
|
|
354
|
+
countDigitPoor() digit::9 time::0.254226s
|
|
355
|
+
countDigitUsingSprintf() digit::9 time::3.033319s
|
|
356
|
+
|
|
357
|
+
```
|