Before addressing efficiency, some improvements I would recommend:
No need for a goto
here. This is easy to turn into a for
loop.
Say const char *input2
, to avoid accidentally modifying your input string.
Use whitespace to clarify order of operations:
Take out the asterisk in *input2++;
You aren't using the character.
And a more subtle issue:
isdigit
expects an unsigned char
casted to an int
. char
is usually signed (but on some platforms, it's unsigned). Thus, if one of your input bytes is not ASCII, it may lead to undefined behavior.
isdigit((unsigned char) *input2)
Here is an editorialized version of your code:
void GetCount(const char* input2)
{
int sum = 0; /* Sum of digits in current number */
int n = 0; /* Number of digits in current number */
for (;;)
{
input2++;
if (*input2 == '\0')
break;
/*
* If we have a digit, increment sum and n appropriately.
*
* Otherwise (we ran into a brace or comma), tally the current number,
* and clear the stats for the next number.
*/
if(isdigit((unsigned char) *input2))
{
sum += *input2 - '0';
n++;
}
else
{
if(sum > n<<2)
output1++;
sum = 0;
n = 0;
}
}
}
Let's look at the sum > n<<2
line, which looks wrong to me. Here's the condition we want to test (simple, but inefficient):
1. (double)sum / n >= 5.0
We can express it in integer arithmetic as:
2. sum >= n * 5
Now I get what you were trying to do. Your next steps converted the multiplication to a less expensive shift:
3. sum > n * 4
4. sum > n<<2
Step 3 is wrong. sum
can be greater than n * 4
but less than n * 5
. Example:
34566: sum = 24, n = 5
n * 4 = 20 sum > n * 4 holds
n * 5 = 25 sum >= n * 5 does not hold
The good news is, we can get rid of the multiply and even the shift! Just increment n
by 5 each iteration:
if(isdigit((unsigned char) *input2))
{
sum += *input2 - '0';
n += 5;
}
else
{
if(sum >= n)
output1++;
sum = 0;
n = 0;
}
Finally, let's get rid of that isdigit
. It's probably pretty fast, but it has to guard against EOF
and do a table lookup. Assuming your input is guaranteed to be in the syntax you describe (non-negative integers delimited by commas and wrapped in braces), you can test for two specific characters instead of having to do a character class lookup.
Here is a final version, with more cleanups:
/*
* Given a list of numbers in the following syntax:
*
* list ::= '{' '}'
| '{' number (',' number)* '}'
*
* number ::= [0-9]+
*
* Count how many numbers have digits that average to 5 or more.
*/
int GetCount(const char* input)
{
int sum = 0; /* Sum of digits in current number */
int length_times_five = 0; /* Number of digits in current number, times 5 */
int ret = 0;
/*
* Handle empty list. Otherwise, the following code
* would return 1 because 0 >= 0.
*/
if (input[0] == '{' && input[1] == '}')
return 0;
while (*++input != '\0')
{
if (*input == ',' || *input == '}')
{
if(sum >= length_times_five)
ret++;
sum = 0;
length_times_five = 0;
}
else
{
sum += *input - '0';
length_times_five += 5;
}
}
return ret;
}
n
passed into the function if the first thing you do is set it to zero? \$\endgroup\$goto
: You are going to hear, again and again, that you should never usegoto
. Like any best practice, try to adhere to it, but take it with a grain of salt. Since C lacks exceptions and closures, and does not guarantee optimized tail recursion, there are legitimate uses forgoto
(e.g. jumping to cleanup code at the end of your function). However, it takes a lot of maturity to know whengoto
is a good idea. Take a look at this parser I wrote in C a couple years ago, and decide for yourself if it abusesgoto
. \$\endgroup\$