我有一些代码对64位整数进行了大量的比较,但是它必须考虑数字的长度,就好像它被格式化为字符串一样。我不能更改调用代码,只能更改函数。
最简单的方法(除了.ToString().Length)是:
(int)Math.Truncate(Math.Log10(x)) + 1;
然而,这表现得相当糟糕。因为我的应用程序只发送正值,并且长度在2和9之间相当均匀地分布(偏向于9),所以我预先计算了这些值和have if语句:
static int getLen(long x) {
if (x < 1000000) {
if (x < 100) return 2;
if (x < 1000) return 3;
if (x < 10000) return 4;
if (x < 100000) return 5;
return 6;
} else {
if (x < 10000000) return 7;
if (x < 100000000) return 8;
if (x < 1000000000) return 9;
return (int)Math.Truncate(Math.Log10(x)) + 1; // Very uncommon
}
}
这样就可以通过平均4次比较来计算长度。
那么,有没有其他技巧可以让这个函数更快呢?
编辑:这将作为32位代码(Silverlight)运行。
更新:
我采纳了诺曼的建议,对in做了一些修改,平均只有3次比较。根据Sean的评论,我删除了Math.Truncate。总而言之,这提高了大约10%。谢谢!
发布于 2009-03-24 23:28:00
这是一个二进制搜索版本,我已经测试过了,它在64位整数上工作,每次只使用五次比较。
int base10len(uint64_t n) {
int len = 0;
/* n < 10^32 */
if (n >= 10000000000000000ULL) { n /= 10000000000000000ULL; len += 16; }
/* n < 10^16 */
if (n >= 100000000) { n /= 100000000; len += 8; }
/* n < 100000000 = 10^8 */
if (n >= 10000) { n /= 10000; len += 4; }
/* n < 10000 */
if (n >= 100) { n /= 100; len += 2; }
/* n < 100 */
if (n >= 10) { return len + 2; }
else { return len + 1; }
}
我怀疑这会比你已经做的更快。但这是可以预测的。
发布于 2009-03-24 23:56:53
我做了一些测试,这似乎比你现在的代码快2-4倍:
static int getLen(long x) {
int len = 1;
while (x > 9999) {
x /= 10000;
len += 4;
}
while (x > 99) {
x /= 100;
len += 2;
}
if (x > 9) len++;
return len;
}
编辑:
下面是一个使用了更多Int32操作的版本,如果您没有x64应用程序,它应该会工作得更好:
static int getLen(long x) {
int len = 1;
while (x > 99999999) {
x /= 100000000;
len += 8;
}
int y = (int)x;
while (y > 999) {
y /= 1000;
len += 3;
}
while (y > 9) {
y /= 10;
len ++;
}
return len;
}
发布于 2009-03-24 23:38:18
您在代码中评论说10位或更多的数字非常不常见,所以您最初的解决方案还不错
https://stackoverflow.com/questions/679602
复制相似问题