Efficiency In Small Programs.

[BarakH]

Hi guys,
First of all I'm new here so how are you all? and nice too meet you! :)
My name is Barak, I'm a first year student in Computer Science although I have some experience (studied in John Bryce).
We recently had a test where I think my teacher dedacted points for no good reason.
Our task was:
We have two arrays, one is a bucket array and one is an input array that holds numbers with up to 10 digits.
we had to count each number and the seconed array and increase the bucket by one in the index that is equal to the amount of digits of the number.
My way of doing that is:

for(int i = 0 ; i < size ; i++)
{
    temp = num[i]; // Store The Number In A Temp Integer.
    while (temp > 0) // Run While There Are Still Digits In The Number.
    {
        temp /= 10; // Cut The Last Digit.
        DigitsNum++; // Increase The Counter.
    }
    Counts[DigitsNum]++; // Increase The Bucket In The Index - DigitNum.
    DigitsNum = 0; // Init DigitsNum.
}

My teacher told me that "the while part should have been taken out of the function and placed in a side function that counts the digits". but in my opinion, even though there shouldn't be a significant amount of improvment, doing the while in the same function (since it is small and not difficult to understand) is just as efficient and even more then doing it like he said (I forgot to mention that in the first page they asked for most efficent while using the least ammount of memory), there for there is no reason too write it in a side function.
Am I right? wrong? missing something?

Thanks a lot,
Barak.

[Nick Evan]

It's a matter of personal opinion. I would have done it the way your teacher described (and lose the temp var), because it would be easier to read IMO:

int NumberOfDigits(int in) {
    int DigitsNum = 0;
    while (in > 0) // Run While There Are Still Digits In The Number.
    {
        in /= 10; // Cut The Last Digit.
        DigitsNum++; // Increase The Counter.
    }
    return DigitsNum;
}

[........]


for(int i = 0 ; i < size ; i++)
{
    int DigitsNum = NumberOfDigits(num[i]);
    Counts[DigitsNum]++; // Increase The Bucket In The Index - DigitNum.
}

But that's no reason to give you a lower grade. I can imagine that not using a temp-var would result in a bit more efficiency (although it might be optimized out when compiling), but using a function and passing a var to it will result in a decrease in efficiency.
Either way, we're talking about micro-optimization which isn't used anymore in reallife. (unless you're working with embedded systems, or really old processors).

[Narue]

>Am I right? wrong? missing something?
That's a toughie. While a compiler might inline your function, it's best to assume that there will be overhead. However, the overhead of a function call isn't exactly significant these days, which is why it's generally better to modularize (your teacher's suggestion) than to rewrite inline as needed (your solution).

A good middle ground is an inline function that counts digits (though it's still not guaranteed to be inlined):

inline int digits(int value, int base = 10)
{
  int n = 0;

  do
    ++n;
  while ((value /= base) != 0);

  return n;
}

"Most efficient" doesn't necessarily mean "worst structure". ;) Usually you can use less than optimal code structure for readability and get the most performance benefits from well chosen algorithms. Only in uncommon cases will you need to go balls to the wall and squeeze every last cycle out of your code.

I think I'd side with your teacher on this one, though that's in terms of advice. I probably wouldn't deduct points.

[BarakH]

Hi, thanks for the answers.
I agree with what you guys said, my teacher's remark is in place but I want to appeal on the part where he deducted points since I think both answers are well written and no major improvement well be gained be doing either way.
Would you agree with me on that? (I want to appeal so badly since that's my final score in the course and every point is needed).

[Nick Evan]

Let me put it this way: If I were you and he deducted points for something as trivial as this, I'd probably kick him in the hemorrhoids.
But if you want proof, you should benchmark the three solutions you currently have.

[Narue]

>I want to appeal so badly since that's my final
>score in the course and every point is needed
How many points are we talking about? Is this the difference between passing and failing? Or are the points deducted ridiculous relative to the triviality of the situation? If you're so keen to appeal, I think there might be more to the story than you've shown.

[tetron]

Minimum memory and speed is always a compromise

log10 is an ugly way of solving this with possibly fewer steps unfortunately math.h only has double and float versions so

#include <math.h>

while(--size)
{
++Counts[ int( log10( float(*num) ) ) ];
++num;
}

This code uses fewer temp variables if you use log10 as a look-up and though logss requires more space this would not count as an overhead. where "0" is being counted as 1 digit

But clearly the code is insane to read and temp variables would be
best contained within a function

so

//assuming only doing this for one array of numbers
while(--size)
{
++Counts[digits(*num)];
++num;
}

This has removed all error checking that digits is in range of counts
for the purpose of speed it is assumed that num has checked this.

now
you can use NARUE's sensible function or the ugly

inline int digits(int value)
{
float val(value);
float ret = log10(val); //math.h pollutes the namespace
return int(ret); 
}

and by being separate you can chose how to optimise it later

the *num is because all arrays act as pointers and is faster than [] which is random access but it has been superceded by the stl

the ++x is supposedly better than x++ as x++ uses a temp but
if you time it I doubt your compiler does what you tell it and will do the same for both.

The penalty does seem harsh but perhaps there were marks for using your own functions and OO programming good luck with your appeal.

>Am I right? wrong? missing something?
That's a toughie. While a compiler might inline your function, it's best to assume that there will be overhead. However, the overhead of a function call isn't exactly significant these days, which is why it's generally better to modularize (your teacher's suggestion) than to rewrite inline as needed (your solution).

A good middle ground is an inline function that counts digits (though it's still not guaranteed to be inlined):

inline int digits(int value, int base = 10)
{
  int n = 0;

  do
    ++n;
  while ((value /= base) != 0);

  return n;
}

"Most efficient" doesn't necessarily mean "worst structure". ;)

[tetron]

Minimum memory and speed is always a while(--size)

This will stop when size is 0 and so size should been used first as a do while if using same size as original array it wouldn't add the last number :)
but in real life I don't use do while and would have used a for loop and iterators and stl, this is why it is important to write clear code ;)