TA貢獻(xiàn)2021條經(jīng)驗(yàn) 獲得超8個贊
遞歸方法：-)
int numPlaces (int n) {
if (n < 0) return numPlaces ((n == INT_MIN) ? MAX_INT: -n);
if (n < 10) return 1;
return 1 + numPlaces (n / 10);
}
或迭代：
int numPlaces (int n) {
int r = 1;
if (n < 0) n = (n == INT_MIN) ? INT_MAX: -n;
while (n > 9) {
n /= 10;
r++;
}
return r;
}
或原始速度：
int numPlaces (int n) {
if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
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;
/* 2147483647 is 2^31-1 - add more ifs as needed
and adjust this final return as well. */
return 10;
}
修改了上面的內(nèi)容，以更好地處理MININT。在任何不遵循明智的2 n二進(jìn)制補(bǔ)碼規(guī)則的怪異系統(tǒng)上，可能需要進(jìn)一步調(diào)整。
原始速度版本實(shí)際上勝過浮點(diǎn)版本，對其進(jìn)行了以下修改：
int numPlaces (int n) {
if (n == 0) return 1;
return floor (log10 (abs (n))) + 1;
}
經(jīng)過一億次迭代，我得到了以下結(jié)果：
Raw speed with 0: 0 seconds
Raw speed with 2^31-1: 1 second
Iterative with 2^31-1: 5 seconds
Recursive with 2^31-1: 6 seconds
Floating point with 1: 6 seconds
Floating point with 2^31-1: 7 seconds
這實(shí)際上讓我有些驚訝-我以為Intel芯片的FPU不錯，但我想一般的FP操作仍然無法與手動優(yōu)化的整數(shù)代碼競爭。
更新以下Stormsoul的建議：
通過Stormsoul測試乘法迭代解決方案可獲得4秒鐘的結(jié)果，因此盡管它比除法迭代解決方案要快得多，但仍與優(yōu)化的if語句解決方案不匹配。
從1000個隨機(jī)生成的數(shù)字中選擇參數(shù)將原始速度時間縮短到2秒，因此，雖然每次都使用相同的參數(shù)似乎有些優(yōu)勢，但它仍然是列出的最快方法。
使用-O2進(jìn)行編譯可以提高速度，但不能改善相對位置（我將迭代計數(shù)增加了十倍來進(jìn)行檢查）。
任何進(jìn)一步的分析都必須認(rèn)真考慮CPU效率的內(nèi)部工作原理（不同的優(yōu)化類型，緩存的使用，分支預(yù)測，您實(shí)際擁有的CPU，房間的環(huán)境溫度等等），這將妨礙我的付費(fèi)工作：-)。這是一個有趣的轉(zhuǎn)移，但是在某些時候，優(yōu)化的投資回報變得太小了而已。我認(rèn)為我們已經(jīng)有了足夠的解決方案來回答這個問題（畢竟，這與速度無關(guān)）。
進(jìn)一步更新：
這將是我對此答案的最終更新，其中不包含不依賴于體系結(jié)構(gòu)的明顯錯誤。受Stormsoul勇于測量的啟發(fā)，我發(fā)布了我的測試程序（根據(jù)Stormsoul自己的測試程序進(jìn)行了修改）以及此處答案中顯示的所有方法的一些示例圖。請記住，這是在一臺特定的機(jī)器上，您的行駛里程可能會因運(yùn)行位置而異（這就是為什么我發(fā)布測試代碼的原因）。
隨心所欲地處理它：
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>
#include <time.h>
#define numof(a) (sizeof(a) / sizeof(a[0]))
/* Random numbers and accuracy checks. */
static int rndnum[10000];
static int rt[numof(rndnum)];
/* All digit counting functions here. */
static int count_recur (int n) {
if (n < 0) return count_recur ((n == INT_MIN) ? INT_MAX : -n);
if (n < 10) return 1;
return 1 + count_recur (n / 10);
}
static int count_diviter (int n) {
int r = 1;
if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
while (n > 9) {
n /= 10;
r++;
}
return r;
}
static int count_multiter (int n) {
unsigned int num = abs(n);
unsigned int x, i;
for (x=10, i=1; ; x*=10, i++) {
if (num < x)
return i;
if (x > INT_MAX/10)
return i+1;
}
}
static int count_ifs (int n) {
if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
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;
/* 2147483647 is 2^31-1 - add more ifs as needed
and adjust this final return as well. */
return 10;
}
static int count_revifs (int n) {
if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
if (n > 999999999) return 10;
if (n > 99999999) return 9;
if (n > 9999999) return 8;
if (n > 999999) return 7;
if (n > 99999) return 6;
if (n > 9999) return 5;
if (n > 999) return 4;
if (n > 99) return 3;
if (n > 9) return 2;
return 1;
}
static int count_log10 (int n) {
if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
if (n == 0) return 1;
return floor (log10 (n)) + 1;
}
static int count_bchop (int n) {
int r = 1;
if (n < 0) n = (n == INT_MIN) ? INT_MAX : -n;
if (n >= 100000000) {
r += 8;
n /= 100000000;
}
if (n >= 10000) {
r += 4;
n /= 10000;
}
if (n >= 100) {
r += 2;
n /= 100;
}
if (n >= 10)
r++;
return r;
}
/* Structure to control calling of functions. */
typedef struct {
int (*fnptr)(int);
char *desc;
} tFn;
static tFn fn[] = {
NULL, NULL,
count_recur, " recursive",
count_diviter, " divide-iterative",
count_multiter, " multiply-iterative",
count_ifs, " if-statements",
count_revifs, "reverse-if-statements",
count_log10, " log-10",
count_bchop, " binary chop",
};
static clock_t clk[numof (fn)];
int main (int c, char *v[]) {
int i, j, k, r;
int s = 1;
/* Test code:
printf ("%11d %d\n", INT_MIN, count_recur(INT_MIN));
for (i = -1000000000; i != 0; i /= 10)
printf ("%11d %d\n", i, count_recur(i));
printf ("%11d %d\n", 0, count_recur(0));
for (i = 1; i != 1000000000; i *= 10)
printf ("%11d %d\n", i, count_recur(i));
printf ("%11d %d\n", 1000000000, count_recur(1000000000));
printf ("%11d %d\n", INT_MAX, count_recur(INT_MAX));
/* */
/* Randomize and create random pool of numbers. */
srand (time (NULL));
for (j = 0; j < numof (rndnum); j++) {
rndnum[j] = s * rand();
s = -s;
}
rndnum[0] = INT_MAX;
rndnum[1] = INT_MIN;
/* For testing. */
for (k = 0; k < numof (rndnum); k++) {
rt[k] = (fn[1].fnptr)(rndnum[k]);
}
/* Test each of the functions in turn. */
clk[0] = clock();
for (i = 1; i < numof (fn); i++) {
for (j = 0; j < 10000; j++) {
for (k = 0; k < numof (rndnum); k++) {
r = (fn[i].fnptr)(rndnum[k]);
/* Test code:
if (r != rt[k]) {
printf ("Mismatch error [%s] %d %d %d %d\n",
fn[i].desc, k, rndnum[k], rt[k], r);
return 1;
}
/* */
}
}
clk[i] = clock();
}
/* Print out results. */
for (i = 1; i < numof (fn); i++) {
printf ("Time for %s: %10d\n", fn[i].desc, (int)(clk[i] - clk[i-1]));
}
return 0;
}
請記住，您需要確保使用正確的命令行進(jìn)行編譯。特別是，您可能需要明確列出數(shù)學(xué)庫才能開始log10()工作。我在Debian下使用的命令行是gcc -o testprog testprog.c -lm。
而且，就結(jié)果而言，這是我的環(huán)境的排行榜：
優(yōu)化級別0：
Time for reverse-if-statements: 1704
Time for if-statements: 2296
Time for binary chop: 2515
Time for multiply-iterative: 5141
Time for divide-iterative: 7375
Time for recursive: 10469
Time for log-10: 26953
優(yōu)化級別3：
Time for if-statements: 1047
Time for binary chop: 1156
Time for reverse-if-statements: 1500
Time for multiply-iterative: 2937
Time for divide-iterative: 5391
Time for recursive: 8875
Time for log-10: 25438
TA貢獻(xiàn)1843條經(jīng)驗(yàn) 獲得超7個贊
二進(jìn)制搜索偽算法，以獲取v。中r的位數(shù)。
if (v < 0 ) v=-v;
r=1;
if (v >= 100000000)
{
r+=8;
v/=100000000;
}
if (v >= 10000) {
r+=4;
v/=10000;
}
if (v >= 100) {
r+=2;
v/=100;
}
if( v>=10)
{
r+=1;
}
return r;
舉報