For Loops Code Optimization

Question

I had a challenge to print out multiples of 7 (non-negative) to the 50th multiple in the simplest way humanly possible using for loops.

I came up with this (Ignoring the data types)

for(int i = 0; i <= 350; i += 7)
         {System.out.println(i);}

The other guy came up with this

for(int i=0;i <=50; i++)
{
System.out.println(7*i);
}

However, I feel the two code snippets could be further optimized. If it actually can please tell. And what are the advantages/disadvantages of one over the other?

You want to optimize this? The output part will take roughly 99.99% of the time, with the actual math taking way too little time to even spend a single thought on whether to optimize it, much less how. By the time you arrive at enlightenment and realize all that and even more reasons you shouldn't worry,, you've already spent countless times the time it takes to make these calculations thousands and thousands of times. Way to waste time ;) — user395760
– user395760, Commented Jul 24, 2011 at 22:02
there's for(int i=0; i<1; i++) System.out.println("0,7,...."); // :-) — hatchet - done with SOverflow
– hatchet - done with SOverflow, Commented Jul 24, 2011 at 22:11
The fastest execution would be to unroll the loops and just print each number: System.out.println("0"); System.out.println("7"); System.out.println("14"); ... . But you ruled that out in the premise to the challenge. :-P However, "the simplest way humanly possible" can mean many different things; I would it to mean "easiest to maintain" and/or "easiest to understand what's going on by looking at the code," not "fastest." — Ted Hopp
– Ted Hopp, Commented Jul 24, 2011 at 22:12
@delnan: I with I could find the comment where I first heard the expression "getting a haircut to lose weight". — Mike Dunlavey
– Mike Dunlavey, Commented Jul 25, 2011 at 0:18

Eng.Fouad · Accepted Answer · 2011-07-24 22:58:54Z

9

If you really want to optimize it, do this:

System.out.print("0\n7\n14\n21\n28\n35\n42\n49\n56\n63\n70\n77\n84\n91\n98\n105\n112\n119\n126\n133\n140\n147\n154\n161\n168\n175\n182\n189\n196\n203\n210\n217\n224\n231\n238\n245\n252\n259\n266\n273\n280\n287\n294\n301\n308\n315\n322\n329\n336\n343\n350");

and it's O(1) :)

answered Jul 24, 2011 at 22:58

Eng.Fouad

118k75 gold badges326 silver badges431 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Mike Dunlavey Over a year ago

++ Even faster would be to have the results in a file, and just cat it.

trutheality · Accepted Answer · 2011-07-24 22:08:46Z

3

The first one technically performs less operations (no multiplication).

The second one is slightly more readable (50 multiples of 7 vs. multiples of 7 up to 350).

Probably can't be optimized any further.

Unless you're willing to optimize away multiple println calls by doing:

StringBuilder s = new StringBuilder();

for(int i = 0; i <= 350; i += 7) s.append(i).append(", ");

System.out.println(s.toString());

(IIRC printlns are relatively expensive.)

This is getting to the point where you gain a tiny bit of optimization at the expense of simplicity.

edited Jul 24, 2011 at 22:08

answered Jul 24, 2011 at 22:01

trutheality

23.5k6 gold badges58 silver badges68 bronze badges

16 Comments

fastcodejava Over a year ago

But i++ is faster than i+7.

user395760 Over a year ago

@fastcodejava: Says who? And even if, could you measure a difference even for insanely many iterations?

Ted Hopp Over a year ago

@fastcodejava - How do you know that i++ is always faster than i+7?

Mob Over a year ago

But CPU's multiplication is basically addition??

trutheality Over a year ago

@fastcodejava: doing i++ and then i*7 is almost certainly more expensive than just doing i+=7.

|

phihag · Accepted Answer · 2011-07-24 22:02:43Z

1

In theory, your code is faster since it does not need one less multiplication instruction per loop.

However, the multiple calls to System.out.println (and the integer-to-string conversion) will dwarf the runtime the multiplication takes. To optimize, aggregate the Strings with a StringBuilder and output the whole result (or output the result when memory becomes a problem).

However, in real-world code, this is extremely unlikely to be the bottleneck. Profile, then optimize.

answered Jul 24, 2011 at 22:02

phihag

289k75 gold badges475 silver badges489 bronze badges

Comments

Tom · Accepted Answer · 2011-07-24 21:59:56Z

0

The second function is the best you would get: O(n)

answered Jul 24, 2011 at 21:59

Tom

9,69527 gold badges96 silver badges149 bronze badges

4 Comments

phihag Over a year ago

@Both functions are O(n), and the constant of the asymptotic complexities is actually meaningful here.

fastcodejava Over a year ago

First function is not O(n)?

Tom Over a year ago

I know they are both O(n) the second one makes fewer iterations thus more optimized. And when scaling even greater optimized

user395760 Over a year ago

Both make exactly the same number of iterations, only with different step sizes.

Collectives™ on Stack Overflow

For Loops Code Optimization

4 Answers 4

1 Comment

16 Comments

Comments

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

16 Comments

Comments

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related