CODEWITHSUNDEEP
calgorithmperformancereadability
mauroSabella
mauroSabella

Reputation: 71

Is a single loop with several statements and conditions better than several simple loops?

I was creating a very simple program that determines how many coins you need to return the change to a client, using a greedy algorithm. The algorithm is really obvious, you just need to determine which is the bigger coin you can use, subtract its value from the change and update the coins counter.

I have thought of two really similar implementations.

note: changeInt is the change, multiplied by 100 and converted into a integer.

1) A single "complex" loop

while(changeInt != 0) {
       if(changeInt - 25 >= 0){
           changeInt -= 25;
           coins++;
       }
       else if(changeInt - 10 >= 0){
           changeInt -= 10;
           coins++;
       }
       else if(changeInt - 5 >= 0){
           changeInt -= 5;
           coins++;
       }
       else if(changeInt - 1 >= 0){
           changeInt -= 1;
           coins++;
       }

   }

2) Multiple simple loops

    while(changeInt - 25 >= 0) 
   {
       changeInt -= 25;
       coins++;
   }
    while(changeInt - 10 >= 0)
   {
       changeInt -= 10;
       coins++;
   }

    while(changeInt - 5 >= 0)
   {
       changeInt -= 5;
       coins++;
   }

    while(changeInt - 1 >= 0)
   {
       changeInt -= 1;
       coins++;
   }

Now, I know the performance will probably be similar in both cases, since the algorithm is the same, but I was wondering which approach is better.

The single loop is the first idea I came up with, then I thought of the second method and it intuitively seems better to me.

I don't really care about my exact scenario, I'm more interested in the general one (several simple loops vs few more complex loops)

1) Which approach is better in terms of performance?

2) Is the difference noticeable, at least when working with huge numbers?

3) Is one approach significantly more readable than the other? (not sure if I can ask that here)

Thank you!

Upvotes: 5

Views: 167

Answers (4)

dbush
dbush

Reputation: 225437

As others have mentioned, the second approach is preferable since it uses less comparisons.

A cleaner, more concise way would be to use division and modulus:

int current = changeInt;
coins += current / 25;
current %= 25;
coins += current / 10;
current %= 10;
coins += current / 5;
current %= 5;
coins += current;

While the div and mod operators are more expensive than subtracting, it's likely to be faster for larger value of changeInt and there are no branches.

Upvotes: 2

Anjani Kumar Agrawal
Anjani Kumar Agrawal

Reputation: 375

I see no reason why you need a loop for this. Adding a temp variable in case you need to preserve your original value:

int tempChangeInt;

tempChangeInt = changeInt;
coins = changeInt / 25;
tempChangeInt = changeInt % 25;
if (tempChangeInt != 0)
{
    coins += tempChangeInt / 10;
    tempChangeInt = tempChangeInt % 10;
}
if (tempChangeInt != 0)
{
    if (tempChangeInt >= 5)
        coins += (tempChangeInt - 5) + 1;
    else
        coins += tempChangeInt;
}

Upvotes: 0

David Pérez Cabrera
David Pérez Cabrera

Reputation: 5068

As you said, both are pretty similar, if we are talking about the readability I prefer the first one (but it is a subjective opinion).

If we think in performance, IMHO the second is a little bit faster than the previous one. We can try to traslate to ASM for for detail comparison:

1) A single "complex" loop (aprox ASM x86-64)

jmp
mov
sub
test
js
sub
add
jmp
mov
sub
test
js 
sub
add
jmp 
mov 
sub 
test
js  
sub 
add 
jmp 
mov 
sub 
test
js 
sub
add
cmp
jne

2) Multiple simple loops (aprox ASM x86-64)

jmp
sub
add
mov
sub
test
jns
jmp
sub
add
mov
sub
test
jns
jmp
sub
add
mov
sub
test
jns
jmp
sub
add
mov
sub
test
jns

If we count the x86-64 ASM instructions:

jmp: 4
mov: 4
sub: 8
test: 4
add: 4
js: 4
cmp: 1
jne: 1

vs 

jmp: 4
mov: 4
sub: 8
test: 4
add: 4
jns: 4

Then to sum up:

js 4
cmp 1
jne 1

vs

jns 4

And "js" is similar to "jns".

But this can change with other compilers or architectures, even so, I think the second one is a little bit faster than the first one.

Upvotes: 0

Sparky
Sparky

Reputation: 14117

If you had to choose between the looped approaches you described, the second would be preferable (with a slight variation). It is cleaner, and mostly avoids unnecessary testing.

Here's the slight variation ...

while(changeInt >= 25) {
   changeInt -= 25;
   coins++;
}

while(changeInt >= 10) {
   changeInt -= 10;
   coins++;
}

while(changeInt >= 5) {
   changeInt -= 5;
   coins++;
}

while(changeInt > 0) {
   changeInt -= 1;
   coins++;
}

The primary advantage that this offers is that it helps ensure that 'changeInt - X' never wraps around. From what you described in your post, it is unlikely that it would be an issue, but if the type were change from a signed integer to an unsigned integer, then you might have found yourself trying to figure out where the bug lay.

Alternatively, you may wish to use a combination of the division and modulus operators to calculate the change and avoid the loops.

Hope this helps.

Upvotes: 1

Related Questions