0
\$\begingroup\$

I'v written this code snippet that's part of a code competition.

I want to do the trick without the for-loop, or simply find a way to optimize this code for speed.

for ( i=1; i<=N; i++ )

How is it possible, if it is? What do I need to modify to speed up this code considering a very large input file?

Here is the competition summary:

Players generally sit in a circle. The player designated to go first says the number "1", and each player thenceforth counts one number in turn. However, any number divisible by 'A' e.g. three is replaced by the word fizz and any divisible by 'B' e.g. five by the word buzz. Numbers divisible by both become fizz buzz. A player who hesitates or makes a mistake is either eliminated.

Write a program that prints out the the pattern generated by such a scenario given the values of 'A'/'B' and 'N' which are read from an input text file. The input text file contains three space delimited numbers i.e. A, B, N. The program should then print out the final series of numbers using 'F' for fizz, 'B' for 'buzz' and 'FB' for fizz buzz.

Print out the series 1 through N replacing numbers divisible by 'A' by F, numbers divisible by 'B' by B and numbers divisible by both as 'FB'. Since the input file contains multiple sets of values, your output will print out one line per set. Ensure that there are no trailing empty spaces on each line you print.

Input file:

3 5 10
2 7 15

Output:

1 2 F 4 B F 7 8 F B
1 F 3 F 5 F B F 9 F 11 F 13 FB 15

Here my code:

int main(int argc, const char * argv[])
{
  NSString* filename      = [NSString stringWithCString:argv[1] encoding:NSASCIIStringEncoding];
  NSString* content       = [NSString stringWithContentsOfFile:filename encoding:NSASCIIStringEncoding error:nil];
  NSScanner* scanner      = [NSScanner scannerWithString:content];
  while ( ![scanner isAtEnd] )
  {
    NSString* line;
    [scanner scanUpToString:@"\n" intoString:&line];

    NSArray *nums = [ line componentsSeparatedByString:@" " ];
    int A         = [[nums objectAtIndex:0] intValue];
    int B         = [[nums objectAtIndex:1] intValue];
    int N         = [[nums objectAtIndex:2] intValue];

    int i=0;
    for ( i=1; i<=N; i++ )
    {
      NSString *str = [ NSString stringWithFormat:@"%d", i ];

      if ( i%A == 0 ) str = @"F";
      if ( i%B == 0 ) str = @"B";
      if ( i%A == 0 && i%B == 0 ) str = @"FB";

      printf( "%s ", [str UTF8String] );
    }
    printf("\n");
  }    
  return 0;
}
\$\endgroup\$
3
\$\begingroup\$

A compiler might unroll the loop for you. Try inspecting the assembly output when it is compiled at different optimization levels.

As for the body of the loop, I'd keep the string manipulation to a minimum.

int AB = A * B;
for ( int i=1; i<=N; i++ )
{
  if      ( i % AB == 0 ) printf("FB ");
  else if ( i % A  == 0 ) printf("F ");
  else if ( i % B  == 0 ) printf("B ");
  else                    printf("%d ", i);
}

Also consider concatenating the output to be printed at once. It's likely that I/O is the bottleneck.

\$\endgroup\$
  • 1
    \$\begingroup\$ N is not const value, so it is not possible for compiler to unroll the loop \$\endgroup\$ – Bryan Chen Jan 9 '14 at 5:00
5
\$\begingroup\$

The title of your post puts a lot of stress on removing the for loop. Can it be removed?

No, it cannot. You need at least one loop to solve the fizz-buzz...

Additionally, the 'print' statements are by far the largest bulk of your performance problem.

I don't really believe that this code suffers from a problematic performance issue, but, if you want it to go faster, your best bet would be to accumulate all your String values and only print the line once:

NSMutableString* result;
....

for (...) {
    .....
        [result appendString:@"FB "];
    .....
        [result appendFormat:@"%d ", i];

}
printf(result);
printf("\n");

This saves a fair number of unnecessary print statements, and your performance will improve as a result.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.