获取int的长度是否比这种方法更简洁？
int length = String.valueOf(1000).length();
Mic*_*rdt 333
你的基于String的解决方案完全没问题,没有什么"不整齐"的.你必须在数学上认识到,数字没有长度,也没有数字.长度和数字都是特定基数中数字的物理表示的属性,即字符串.
基于对数的解决方案(基于字符串的)在内部执行(某些)相同的操作,并且可能更快(无关紧要)更快,因为它只生成长度并忽略数字.但我实际上并不认为它的意图更清晰 - 这是最重要的因素.
Dmi*_*ant 256
对数是你的朋友:
int n = 1000;
int length = (int)(Math.log10(n)+1);
注意:仅对n> 0有效.
Mar*_*ian 153
最快的方法:分而治之.
假设您的范围是0到MAX_INT,那么您有1到10位数.您可以使用除法和征服来处理此间隔,每个输入最多可进行4次比较.首先,通过一次比较将[1..10]划分为[1..5]和[6..10],然后使用一次比较将每个长度为5的间隔划分为一个长度3和一个长度2间隔.长度2间隔需要一次比较(总共3次比较),长度3间隔可以分为长度1间隔(解)和长度2间隔.所以,你需要3或4个比较.
没有划分,没有浮点运算,没有昂贵的对数,只有整数比较.
代码(长但快):
if (n < 100000){
// 5 or less
if (n < 100){
// 1 or 2
if (n < 10)
return 1;
else
return 2;
}else{
// 3 or 4 or 5
if (n < 1000)
return 3;
else{
// 4 or 5
if (n < 10000)
return 4;
else
return 5;
}
}
} else {
// 6 or more
if (n < 10000000) {
// 6 or 7
if (n < 1000000)
return 6;
else
return 7;
} else {
// 8 to 10
if (n < 100000000)
return 8;
else {
// 9 or 10
if (n < 1000000000)
return 9;
else
return 10;
}
}
}
基准测试(在JVM热身之后) - 请参阅下面的代码以了解基准测试的运行方式:
完整代码:
public static void main(String[] args)
throws Exception
{
// validate methods:
for (int i = 0; i < 1000; i++)
if (method1(i) != method2(i))
System.out.println(i);
for (int i = 0; i < 1000; i++)
if (method1(i) != method3(i))
System.out.println(i + " " + method1(i) + " " + method3(i));
for (int i = 333; i < 2000000000; i += 1000)
if (method1(i) != method3(i))
System.out.println(i + " " + method1(i) + " " + method3(i));
for (int i = 0; i < 1000; i++)
if (method1(i) != method4(i))
System.out.println(i + " " + method1(i) + " " + method4(i));
for (int i = 333; i < 2000000000; i += 1000)
if (method1(i) != method4(i))
System.out.println(i + " " + method1(i) + " " + method4(i));
// work-up the JVM - make sure everything will be run in hot-spot mode
allMethod1();
allMethod2();
allMethod3();
allMethod4();
// run benchmark
Chronometer c;
c = new Chronometer(true);
allMethod1();
c.stop();
long baseline = c.getValue();
System.out.println(c);
c = new Chronometer(true);
allMethod2();
c.stop();
System.out.println(c + " = " + StringTools.formatDouble((double)baseline / c.getValue() , "0.00") + " times faster than baseline");
c = new Chronometer(true);
allMethod3();
c.stop();
System.out.println(c + " = " + StringTools.formatDouble((double)baseline / c.getValue() , "0.00") + " times faster than baseline");
c = new Chronometer(true);
allMethod4();
c.stop();
System.out.println(c + " = " + StringTools.formatDouble((double)baseline / c.getValue() , "0.00") + " times faster than baseline");
}
private static int method1(int n)
{
return Integer.toString(n).length();
}
private static int method2(int n)
{
if (n == 0)
return 1;
return (int)(Math.log10(n) + 1);
}
private static int method3(int n)
{
if (n == 0)
return 1;
int l;
for (l = 0 ; n > 0 ;++l)
n /= 10;
return l;
}
private static int method4(int n)
{
if (n < 100000)
{
// 5 or less
if (n < 100)
{
// 1 or 2
if (n < 10)
return 1;
else
return 2;
}
else
{
// 3 or 4 or 5
if (n < 1000)
return 3;
else
{
// 4 or 5
if (n < 10000)
return 4;
else
return 5;
}
}
}
else
{
// 6 or more
if (n < 10000000)
{
// 6 or 7
if (n < 1000000)
return 6;
else
return 7;
}
else
{
// 8 to 10
if (n < 100000000)
return 8;
else
{
// 9 or 10
if (n < 1000000000)
return 9;
else
return 10;
}
}
}
}
private static int allMethod1()
{
int x = 0;
for (int i = 0; i < 1000; i++)
x = method1(i);
for (int i = 1000; i < 100000; i += 10)
x = method1(i);
for (int i = 100000; i < 1000000; i += 100)
x = method1(i);
for (int i = 1000000; i < 2000000000; i += 200)
x = method1(i);
return x;
}
private static int allMethod2()
{
int x = 0;
for (int i = 0; i < 1000; i++)
x = method2(i);
for (int i = 1000; i < 100000; i += 10)
x = method2(i);
for (int i = 100000; i < 1000000; i += 100)
x = method2(i);
for (int i = 1000000; i < 2000000000; i += 200)
x = method2(i);
return x;
}
private static int allMethod3()
{
int x = 0;
for (int i = 0; i < 1000; i++)
x = method3(i);
for (int i = 1000; i < 100000; i += 10)
x = method3(i);
for (int i = 100000; i < 1000000; i += 100)
x = method3(i);
for (int i = 1000000; i < 2000000000; i += 200)
x = method3(i);
return x;
}
private static int allMethod4()
{
int x = 0;
for (int i = 0; i < 1000; i++)
x = method4(i);
for (int i = 1000; i < 100000; i += 10)
x = method4(i);
for (int i = 100000; i < 1000000; i += 100)
x = method4(i);
for (int i = 1000000; i < 2000000000; i += 200)
x = method4(i);
return x;
}
基准:
编辑: 在我编写基准测试之后,我从Java 6中获得了Integer.toString的潜行峰值,我发现它使用:
final static int [] sizeTable = { 9, 99, 999, 9999, 99999, 999999, 9999999,
99999999, 999999999, Integer.MAX_VALUE };
// Requires positive x
static int stringSize(int x) {
for (int i=0; ; i++)
if (x <= sizeTable[i])
return i+1;
}
我将它与我的分而治之的解决方案进行了对比:
我的速度提高了约4倍.
Jay*_*Jay 13
关于您的基准测试的两条评论:Java是一个复杂的环境,即时编译和垃圾收集等等,所以为了得到公平的比较,每当我运行基准测试时,我总是:(a)附上两个测试在循环中按顺序运行它们5或10次.第二次通过循环的运行时通常与第一次完全不同.并且(b)在每个"方法"之后,我做一个System.gc()来尝试触发垃圾收集.否则,第一种方法可能会生成一堆对象,但不足以强制进行垃圾收集,然后第二种方法会创建一些对象,堆耗尽,垃圾收集运行.然后第二种方法被"收费"用于拾取第一种方法留下的垃圾.非常不公平!
也就是说,上述两个都没有在这个例子中产生显着差异.
无论有没有这些修改,我得到的结果都与你的不同.当我运行它时,是的,toString方法的运行时间为6400到6600毫秒,而日志方法则超过20,000到20,400毫秒.对于我来说,日志方法速度慢了3倍,而不是稍微快一些.
请注意,这两种方法涉及非常不同的成本,因此这并不是完全令人震惊:toString方法将创建许多必须清理的临时对象,而日志方法需要更加强烈的计算.所以可能不同的是,在内存较少的机器上,toString需要更多的垃圾收集轮次,而在处理器速度较慢的机器上,额外的日志计算会更加痛苦.
我也尝试了第三种方法.我写了这个小函数:
static int numlength(int n)
{
if (n == 0) return 1;
int l;
n=Math.abs(n);
for (l=0;n>0;++l)
n/=10;
return l;
}
它运行在1600到1900毫秒之间 - 不到toString方法的1/3,并且是我机器上日志方法的1/10.
如果您有多种数字,可以通过开始除以1,000或1,000,000来进一步加快速度,以减少循环次数.我没玩过那个.
San*_*osh 11
使用Java
int nDigits = Math.floor(Math.log10(Math.abs(the_integer))) + 1;
使用import java.lang.Math.*;在开始
使用C.
int nDigits = floor(log10(abs(the_integer))) + 1;
使用inclue math.h在开始
还不能发表评论,所以我将作为一个单独的答案发布.
基于对数的解决方案不计算非常大的长整数的正确位数,例如:
long n = 99999999999999999L;
// correct answer: 17
int numberOfDigits = String.valueOf(n).length();
// incorrect answer: 18
int wrongNumberOfDigits = (int) (Math.log10(n) + 1);
由于整数的基数10中的位数仅为1 + truncate(log10(数字)),因此您可以:
public class Test {
public static void main(String[] args) {
final int number = 1234;
final int digits = 1 + (int)Math.floor(Math.log10(number));
System.out.println(digits);
}
}
编辑,因为我的上一次编辑修复了代码示例,但没有修改说明.
Marian的解决方案适用于长型号码(最多9,223,372,036,854,775,807),以防有人想要复制和粘贴它.在我编写的程序中,对于数量高达10000的可能性更大,所以我为它们制作了一个特定的分支.无论如何,它不会产生显着的差异.
public static int numberOfDigits (long n) {
// Guessing 4 digit numbers will be more probable.
// They are set in the first branch.
if (n < 10000L) { // from 1 to 4
if (n < 100L) { // 1 or 2
if (n < 10L) {
return 1;
} else {
return 2;
}
} else { // 3 or 4
if (n < 1000L) {
return 3;
} else {
return 4;
}
}
} else { // from 5 a 20 (albeit longs can't have more than 18 or 19)
if (n < 1000000000000L) { // from 5 to 12
if (n < 100000000L) { // from 5 to 8
if (n < 1000000L) { // 5 or 6
if (n < 100000L) {
return 5;
} else {
return 6;
}
} else { // 7 u 8
if (n < 10000000L) {
return 7;
} else {
return 8;
}
}
} else { // from 9 to 12
if (n < 10000000000L) { // 9 or 10
if (n < 1000000000L) {
return 9;
} else {
return 10;
}
} else { // 11 or 12
if (n < 100000000000L) {
return 11;
} else {
return 12;
}
}
}
} else { // from 13 to ... (18 or 20)
if (n < 10000000000000000L) { // from 13 to 16
if (n < 100000000000000L) { // 13 or 14
if (n < 10000000000000L) {
return 13;
} else {
return 14;
}
} else { // 15 or 16
if (n < 1000000000000000L) {
return 15;
} else {
return 16;
}
}
} else { // from 17 to ...¿20?
if (n < 1000000000000000000L) { // 17 or 18
if (n < 100000000000000000L) {
return 17;
} else {
return 18;
}
} else { // 19? Can it be?
// 10000000000000000000L is'nt a valid long.
return 19;
}
}
}
}
}
| 归档时间： |
|
| 查看次数： |
526800 次 |
| 最近记录： |