views:

663

answers:

8

Is there a neater way for getting the length of an int as this?

int length = String.valueOf(1000).length();
+12  A: 

The logarithm is your friend:

 int length = (int)(Math.log10(1000)+1);
Dmitry Brant
an expensive friend...oh, its java. Nevermind.
Tom
Cool, but: cannot convert from double to int, needs a cast. Greetz GHad
GHad
And is this faster or better than using my variant?
finsterr
+1 You beat me by a second, and your answer was right, where mine was slightly off. Note, though, that the compiler will complain due to a missing cast to *int*
Dirk
As others have said, you should try a speed test using both methods. I have not tried it myself.
Dmitry Brant
@finsterr: It actually might. Yours involves allocation of char-arrays and non-trivial computations (division/remainder) in order to generate the string representation. Plus: the string will be thrown away afterwards, so all this happens just to calculate the length...
Dirk
I think the intend of this is pretty clear.
dmeister
@Tom Why would you assume it's expensive? One might assume that the math co-processor would execute it, so it might be close to the speed of an addition. Even if java doesn't use the co-processor now, it's a good assumption that it might... (We'll just ignore your even more uneducated implication that Java is slow because you probably aren't interested in evidence--or if you were you'd go to http://shootout.alioth.debian.org/ and find out for yourself)
Bill K
+3  A: 

Since the number of digits in base 10 of an integer is just 1 + truncate(log10(number)), you can do:

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);
    }
}

Edited because my last edit fixed the code example, but not the description.

Dirk
Cool. but I think it needs abs(number) and also "0" is special case too?
DmitryK
Yes. If you need to account for the sign, you will have to do something like *1 + (int)Math.floor(Math.log10(Math.abs(number))) + ((number < 0)? 1 : 0)*
Dirk
+15  A: 

Your String-based solution is perfectly OK, there is nothing "un-neat" about it. You have to realize that mathematically, numbers don't have a length, nor do they have digits. Length and digits are both properties of a physical representation of a number in a specific base, i.e. a String.

A logarithm-based solution does (some of) the same things the String-based one does internally, and probably does so (insignificantly) faster because it only produces the length and ignores the digits. But I wouldn't actually consider it clearer in intent - and that's the most important factor.

Michael Borgwardt
+1 for consider intent of the code when picking a way to solve a problem
J. Pablo Fernández
Datapoint: On my machine, the log method seems to run just under twice as fast as the string length methods. I wouldn't call that insignificant if the method gets called a lot or in a time-critical section of code.
CPerkins
See my benchmark unit test below(wich may be flawed too i am no benchmark expert). Over a large number of runs (100 000 000), the speed is 11s to 8s on my machine hardly twice as fast.
Jean
@CPerkins. Premature optimization. You know the spiel.
Michael Borgwardt
A: 

Can I try? ;)

based on Dirk's solution

final int digits = number==0?1:(1 + (int)Math.floor(Math.log10(Math.abs(number))));
DmitryK
A: 
int myInt = 123456789;
            int myLength = myInt.ToString().Length;
            Console.WriteLine(myLength);

Try this.

Jonathan Shepherd
This appears to be C# and not Java. It will not compile...
Thorbjørn Ravn Andersen
So why did people vote down? Just because it's c#?
Jonathan Shepherd
Incorrect answers are usually voted down, in the same way that correct answers are voted up. If you want upvotes, answer the question given ;-)
Thorbjørn Ravn Andersen
Sorry, and yes it's c# :)
Jonathan Shepherd
A: 

Curious, I tried to benchmark it ...

import org.junit.Test;
import static org.junit.Assert.*;


public class TestStack1306727 {

    @Test
    public void bench(){
     int number=1000;
     int a= String.valueOf(number).length();
     int b= 1 + (int)Math.floor(Math.log10(number));

     assertEquals(a,b);
     int i=0;
     int s=0;
     long startTime = System.currentTimeMillis();
     for(i=0, s=0; i< 100000000; i++){
      a= String.valueOf(number).length();
      s+=a;
     }
     long stopTime = System.currentTimeMillis();
     long runTime = stopTime - startTime;
     System.out.println("Run time 1: " + runTime);
     System.out.println("s: "+s);
     startTime = System.currentTimeMillis();
     for(i=0,s=0; i< 100000000; i++){
      b= number==0?1:(1 + (int)Math.floor(Math.log10(Math.abs(number))));
      s+=b;
     }
     stopTime = System.currentTimeMillis();
     runTime = stopTime - startTime;
     System.out.println("Run time 2: " + runTime);
     System.out.println("s: "+s);
     assertEquals(a,b);


    }
}

the results are :

Run time 1: 6765
s: 400000000
Run time 2: 6000
s: 400000000

Now I am left to wonder if my benchmark actually means something but I do get consistent results (variations within a ms) over multiple runs of the benchmark itself ... :) It looks like it's useless to try and optimize this...


edit: following ptomli's comment, I replaced 'number' by 'i' in the code above and got the following results over 5 runs of the bench :

Run time 1: 11500
s: 788888890
Run time 2: 8547
s: 788888890

Run time 1: 11485
s: 788888890
Run time 2: 8547
s: 788888890

Run time 1: 11469
s: 788888890
Run time 2: 8547
s: 788888890

Run time 1: 11500
s: 788888890
Run time 2: 8547
s: 788888890

Run time 1: 11484
s: 788888890
Run time 2: 8547
s: 788888890
Jean
Just for the fun of it, what's the difference across a distribution of values of number, from say 0 to a trillion? :)
ptomli
@ptomli: nice catch :-)
Stephen C
+2  A: 

Two comments on your benchmark: Java is a complex environment, what with just-in-time compiling and garbage collection and so forth, so to get a fair comparison, whenever I run a benchmark, I always: (a) enclose the two tests in a loop that runs them in sequence 5 or 10 times. Quite often the runtime on the second pass through the loop is quite different from the first. And (b) After each "approach", I do a System.gc() to try to trigger a garbage collection. Otherwise, the first approach might generate a bunch of objects, but not quite enough to force a garbage collection, then the second approach creates a few objects, the heap is exhausted, and garbage collection runs. Then the second approach is "charged" for picking up the garbage left by the first approach. Very unfair!

That said, neither of the above made a significant difference in this example.

With or without those modifications, I got very different results than you did. When I ran this, yes, the toString approach gave run times of 6400 to 6600 millis, while the log approach topok 20,000 to 20,400 millis. Instead of being slightly faster, the log approach was 3 times slower for me.

Note that the two approaches involve very different costs, so this isn't totally shocking: The toString approach will create a lot of temporary objects that have to be cleaned up, while the log approach takes more intense computation. So maybe the difference is that on a machine with less memory, toString requires more garbage collection rounds, while on a machine with a slower processor, the extra computation of log would be more painful.

I also tried a third approach. I wrote this little function:

static int numlength(int n)
{
 int l;
 n=Math.abs(n);
 for (l=0;n>0;++l)
  n/=10;
 return l;   
}

That ran in 1600 to 1900 millis -- less than 1/3 of the toString approach, and 1/10 the log approach on my machine.

If you had a broad range of numbers, you could speed it up further by starting out dividing by 1,000 or 1,000,000 to reduce the number of times through the loop. I haven't played with that.

Jay
+4  A: 

The fastest approach: divide and conquer.

Assuming your range is 0 to MAX_INT, then you have 1 to 10 digits. You can approach this interval using divide and conquer, with up to 4 comparisons per each input. First, you divide [1..10] into [1..5] and [6..10] with one comparison, and then each length 5 interval you divide using one comparison into one length 3 and one length 2 interval. The length 2 interval requires one more comparison (total 3 comparisons), the length 3 interval can be divided into length 1 interval (solution) and a length 2 interval. So, you need 3 or 4 comparisons.

No divisions, no floating point operations, no expensive logarithms, only integer comparisons.

Code (long but fast):

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;
   }
  }
 }

Benchmark (after JVM worm-up) - see code below to see how the benchmark was run:

  1. baseline method (with String.length): 2145ms
  2. log10 method: 711ms = 3.02 times faster than baseline
  3. repeated divide: 2797ms = 0.77 times faster than baseline
  4. divide-and-conquer: 74ms = 28.99
    times faster than baseline

Full code:

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;
}

Again, benchmark:

  1. baseline method (with String.length): 2145ms
  2. log10 method: 711ms = 3.02 times faster than baseline
  3. repeated divide: 2797ms = 0.77 times faster than baseline
  4. divide-and-conquer: 74ms = 28.99
    times faster than baseline

Edit: After I wrote the benchmark, I took a sneak peak into Integer.toString from Java 6, and I found that it uses:

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;
}

I benchmarked it against my divide-and-conquer solution:

  1. divide-and-conquer: 104ms
  2. Java 6 solution - iterate and compare: 406ms

Mine is about 4x faster.

Marian
this looks great. you could write it a little more compact using the ?: operator to get more acceptance
Andre Pareis
talk about premature optimization :D
CrazyJugglerDrummer