Most performance-friendly approach to solving FizzBuzz

Question

I was doing this FizzBuzz exercise on CodingBat;

Given a string str, if the string starts with "f" return "Fizz". If the string ends with "b" return "Buzz". If both the "f" and "b" conditions are true, return "FizzBuzz". In all other cases, return the string unchanged.

and came up with this answer;

public String fizzString(String str)
{
    String sum = "";

    if (str.startsWith("f")) sum += "Fizz";
    if (str.endsWith("b")) sum += "Buzz";

    return (sum == "") ? str : sum;
}

however, the author of the problem went for;

public String fizzString(String str)
{
    if (str.startsWith("f") && str.endsWith("b")) return "FizzBuzz";
    if (str.startsWith("f")) return "Fizz";
    if (str.endsWith("b")) return "Buzz";

    return str;
}

which seemed way too redundant...

I was wondering, would it make a difference in the real world, performance-wise, to go for the first program rather then the second?

The second is faster. I don't think FizzBuzz performance ever matters in the real world though. — erickson, May 04 '16 at 18:21
In the real world? Probably not. In a nit-picky world, there's trade offs to both approaches. The first approach uses `String` concatenation, which can be [notoriously slow](http://stackoverflow.com/q/1532461/758280). The second approach uses more conditionals than the first. — Jeffrey, May 04 '16 at 18:21
String concatenation is not worth the extra condition checking in the worst case for solution # 2. You might need to allocate more memory for a string concatenation which is much slower than checking a boolean condition — Lucas Crawford, May 04 '16 at 18:23
Not to mention that, even if it will work here, comparing Strings with == is not a good idea. The first one creates and copies Strings, allocating memory that needs to be GCed, whereas the second one always returns references to the same String objects, allocating 0 memory. — JB Nizet, May 04 '16 at 18:27
Would declaring `str.startsWith("f")` and `str.endsWith("b")` as string variables first and then checking the conditions using those variables improve solution #2? — CaffeinatedSynapse, May 04 '16 at 18:28
Not at all (the variables would have to be of type boolean, BTW). — JB Nizet, May 04 '16 at 18:29
...Right, derp. So, solution #2 is really the optimal program for this problem? — CaffeinatedSynapse, May 04 '16 at 18:30
You could, maybe, be marginally faster by replacing `startsWith("f")` by `str.length() > 0 && str.charAt(0) == 'f'` (and similarly for endsWith), but sacrificing readability and simplicity for a hypothetical negligible performance gain in a method that will never be the cause of a performance problem is not worth it. Newbies tend to focus on meaningless performance considerations, instead on focusing on writing simple, readable, maintainable code. — JB Nizet, May 04 '16 at 18:35
I come back to my previous comment. Yes, saving the startsWith in a variable would give a marginal gain, but not because of the variable: because it avoids evaluating startsWith and endsWith twice. — JB Nizet, May 04 '16 at 18:38

score 0 · Accepted Answer · answered May 04 '16 at 18:45

My calculations tell otherwise... (The comment section got too crowded.)

I have a java program that will run a block of code as fast as possible for a set amount of time (1000 milliseconds). It will do this 10 times to get an average, least, and most.

I gotta say, the first method comes out faster, by about 4,000,000 loops per second on average.

Here are my results:

   First Method:
Least loops: 26,312,768
Most loops: 26,918,157
Average loops: 26,582,653.7

   Second Method:
Least loops: 22,039,592
Most loops: 22,596,476
Average loops: 22,424,598.5

Here's the source code I've got, please tell me a way the data I got might have been skewed. I kept the load that my computer was under constant, and I kept the code constant. The only thing that changed was what I called within the while loop.

package personal;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class SpeedTest {

  public static void main(String[] args) {
    int loops = 10;
    double DELAY = 1000;
    int i;
    double[] loopCount = new double[loops + 1];
    double sum = 0;
    for (i = 0; i < loops + 1; i++) {

      long startTime = System.currentTimeMillis();
      long endTime = (long)(startTime + DELAY);
      long index = 0;

      while (true) {
        fizzString("TEST");
        //fizzString2("TEST");
        long now = System.currentTimeMillis();
        if (now >= endTime) {
          break;
        }
        index++;
      }

      if (i != 0) {
        if (DELAY != 1000) {
          if (DELAY / 1000 % 1 == 0) {
            System.out.printf("Test %.0f. %,.0f loops in %.0f seconds.\n", (float) i, (float) index, (float) DELAY / 1000);
          } else if ((DELAY / 100) % 1 == 0) {
            System.out.printf("Test %.0f. %,.0f loops in %.1f seconds.\n", (float) i, (float) index, (float) DELAY / 1000);
          } else if ((DELAY / 10) % 1 == 0) {
            System.out.printf("Test %.0f. %,.0f loops in %.2f seconds.\n", (float) i, (float) index, (float) DELAY / 1000);
          } else if (DELAY % 1 == 0) {
            System.out.printf("Test %.0f. %,.0f loops in %.3f seconds.\n", (float) i, (float) index, (float) DELAY / 1000);
          }
        } else {
          System.out.printf("Test %.0f. %,.0f loops in %.0f second.\n", (float) i, (float) index, (float) DELAY / 1000);
        }
        loopCount[i] = index;
      }
    }
    Arrays.sort(loopCount);
    System.out.printf("Least loops: %,.0f\n", (loopCount[1]));
    System.out.printf("Most loops: %,.0f\n", loopCount[loops]);

    for (int d = 1; d < loopCount.length; d++) {
      sum += loopCount[d];
    }
    double averageLoopCount = 1.0f * sum / (loopCount.length - 1);
    System.out.printf("Average loops: %,.1f", averageLoopCount);
  }

  public static String fizzString(String str) {
    if (str.startsWith("f") && str.endsWith("b")) return "FizzBuzz";
    if (str.startsWith("f")) return "Fizz";
    if (str.endsWith("b")) return "Buzz";

    return str;
  }

  public static String fizzString2(String str) {
    String sum = "";

    if (str.startsWith("f")) sum += "Fizz";
    if (str.endsWith("b")) sum += "Buzz";

    return (sum == "") ? str : sum;
  }
}

Try for yourselves :)

I just did it over and over, and you're right, it is faster... I do not understand, why did the other say the solution #2 was the fastest then? — CaffeinatedSynapse, May 04 '16 at 18:57
@CoffeeAddict The real reason: I don't know; What I can say is that: *Insert "theory vs practice" quote here* — Kaelinator, May 04 '16 at 19:03
First, this benchmark uses TEST as a String, which eliminates the string construction of the first approach, since it doesn't start with f nor ends with b. Second, it ignores the result, which allows Hotspot to completely avoid the call to fizzbuzz. Third, it uses System.currentTimeMillis(), and calls it at each iteration, so that's probably where most of the time is spent. Writing a micro-benchmark in Java is hard. Read http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java — JB Nizet, May 04 '16 at 19:09

score 0 · Answer 2 · answered May 04 '16 at 19:17

This really depends of the actual CPU instructions that get executed,

but the general idea is to have

the least number of executed branches (if-else)
the least number of memory accesses
no dynamic allocation.

Something like this should be faster than both of the proposed solutions.

public String fizzString(String str)
{
    if (str.length() == 0) return str;

    if (str.charAt(0) == 'f') {
        if (str.charAt(str.length() - 1) == 'b') {
            return "FizzBuzz";
        }
        return "Fizz";
    }
    if (str.charAt(str.length() - 1) == 'b') {
        return "Buzz";
    }
    return str;
}

Most performance-friendly approach to solving FizzBuzz

2 Answers2