• Post Reply Bookmark Topic Watch Topic
  • New Topic

For Loop Performance  RSS feed

 
Shahid Pathan
Greenhorn
Posts: 23
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

How can I improve the performance of above for loop?
 
Loic Beylot
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
What do you think about using a logarithm function? No if, just one System.out.println.
 
Wouter Oet
Bartender
Posts: 2700
IntelliJ IDE Opera
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Something like:

 
Campbell Ritchie
Marshal
Posts: 56562
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
you should not go around at this early stage worrying too much about performance. The best way to improve the performance, making the loop run hundreds of times faster, is to remove the print instructions from it. Add the Strings to a StringBulider and then the loop will run in a few microseconds rather than anything up to a second. You will of course need a few milliseconds afterwards to print the result.

I like the idea of a logarithm, however. That is a much better idea which will generalise the loop and allow it to accept numbers of any size.
 
Luigi Plinge
Ranch Hand
Posts: 441
IntelliJ IDE Scala Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Using a floating point logarithm to count integer digits happens to work for ints in Java using the Math.log10() method, but this approach is not theoretically sound e.g. it fails on corner cases for Longs (see bolded results at bottom):


Results:
i - 1 = 9 has 1 digits
(int)log10(i - 1) + 1 = 1
i = 10 has 2 digits
(int)log10(i) + 1 = 2

i - 1 = 99 has 2 digits
(int)log10(i - 1) + 1 = 2
i = 100 has 3 digits
(int)log10(i) + 1 = 3

i - 1 = 999 has 3 digits
(int)log10(i - 1) + 1 = 3
i = 1000 has 4 digits
(int)log10(i) + 1 = 4

i - 1 = 9999 has 4 digits
(int)log10(i - 1) + 1 = 4
i = 10000 has 5 digits
(int)log10(i) + 1 = 5

i - 1 = 99999 has 5 digits
(int)log10(i - 1) + 1 = 5
i = 100000 has 6 digits
(int)log10(i) + 1 = 6

i - 1 = 999999 has 6 digits
(int)log10(i - 1) + 1 = 6
i = 1000000 has 7 digits
(int)log10(i) + 1 = 7

i - 1 = 9999999 has 7 digits
(int)log10(i - 1) + 1 = 7
i = 10000000 has 8 digits
(int)log10(i) + 1 = 8

i - 1 = 99999999 has 8 digits
(int)log10(i - 1) + 1 = 8
i = 100000000 has 9 digits
(int)log10(i) + 1 = 9

i - 1 = 999999999 has 9 digits
(int)log10(i - 1) + 1 = 9
i = 1000000000 has 10 digits
(int)log10(i) + 1 = 10

i - 1 = 9999999999 has 10 digits
(int)log10(i - 1) + 1 = 10
i = 10000000000 has 11 digits
(int)log10(i) + 1 = 11

i - 1 = 99999999999 has 11 digits
(int)log10(i - 1) + 1 = 11
i = 100000000000 has 12 digits
(int)log10(i) + 1 = 12

i - 1 = 999999999999 has 12 digits
(int)log10(i - 1) + 1 = 12
i = 1000000000000 has 13 digits
(int)log10(i) + 1 = 13

i - 1 = 9999999999999 has 13 digits
(int)log10(i - 1) + 1 = 13
i = 10000000000000 has 14 digits
(int)log10(i) + 1 = 14

i - 1 = 99999999999999 has 14 digits
(int)log10(i - 1) + 1 = 14
i = 100000000000000 has 15 digits
(int)log10(i) + 1 = 15

i - 1 = 999999999999999 has 15 digits
(int)log10(i - 1) + 1 = 16

i = 1000000000000000 has 16 digits
(int)log10(i) + 1 = 16

i - 1 = 9999999999999999 has 16 digits
(int)log10(i - 1) + 1 = 17

i = 10000000000000000 has 17 digits
(int)log10(i) + 1 = 17

i - 1 = 99999999999999999 has 17 digits
(int)log10(i - 1) + 1 = 18

i = 100000000000000000 has 18 digits
(int)log10(i) + 1 = 18
 
Campbell Ritchie
Marshal
Posts: 56562
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You said "not theoretically sound". I think the theory is sound, but there are reasons why practice fails at >15 digits. I presume you know what they are. When using ints as in the original example, that problem would not have occurred.
 
Luigi Plinge
Ranch Hand
Posts: 441
IntelliJ IDE Scala Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I'm not referring to the mathematical theory, rather the theory behind using floating point operations for this kind of thing. It may happen to work for Java using ints, but as I showed it doesn't work for Longs, and it might not work for Type X in Language Y in 5 years' time, which makes it bad programming practice in my book. Besides, it probably slower than an integer-based method that you can guarantee always works.
 
Shahid Pathan
Greenhorn
Posts: 23
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks all...
Can we change if conditions in conditional if so that less code and good performance.
 
Luigi Plinge
Ranch Hand
Posts: 441
IntelliJ IDE Scala Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
How about this:
 
Shahid Pathan
Greenhorn
Posts: 23
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is good.
However the performance is low, if you see for loop run for 100 times and every times condition n == 0 is getting check by jvm.
 
Mike Simmons
Ranch Hand
Posts: 3090
14
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Well, I agree with Campbell that optimizing in this way seems like a bad idea, as the printing is likely to be much slower than the math operations you're worrying over. For that matter, the string concatenation is probably slower as well, though not as slow as the printing.

Nonetheless, here's my quick attempt to solve the original problem with a minimum of performance bottlenecks. I don't care enough about this to test whether the way I'm using System.out is actually optimal or not. If it isn't, maybe try using a BufferedWriter around an OutputStreamWriter around System.out.

I intentionally omitted the initial 0 because (a) it doesn't fit into the rest of the algorithm, and (b) it seems silly to describe the number of digits in zero. If you care, add this at the beginning:
 
Luigi Plinge
Ranch Hand
Posts: 441
IntelliJ IDE Scala Windows
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Shahid Pathan wrote:However the performance is low,

You should really do some benchmarking before making incorrect statements like this. I timed your method by running it 100000 times and found that even if you take out the printlns and stick the strings in an array instead, about 95% of the run time is spent building the strings. And the time taken (slightly surprisingly to me) is more or less proportional to the length of the strings you use. But this in turn will be tiny compared with the time it'll take to do anything with them, like output to the console, so "optimising" your conditional statements is irrelevant in any practical situation since it has an unmeasurably small effect. If you want to speed up your method (which is kind of pointless when you have I/O in there), stop worrying about conditionals and focus on avoiding string concatenation like Mike does above.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!