FizzBuzz Obsessions III: Battles in the vast underexplored world of Bash FizzBuzzing
After three kinds of spreadsheets, Haskell, and Emacs Lisp, a battle ensues.
#01. Noob
#!/bin/bash # This is FizzBuzz. We want to return numbers from a sequential list starting # from 1, but replace them with some words. The number will be replaced with # "Fizz" if divisible by 3 but not 5, with "Buzz" if by 5 but not 3, with # "FizzBuzz" if by both, that is, 15. # So first we do a loop, and test things as we go. I'm using seq to generate # numbers. all_numbers=`seq 1 $1` for number in $all_numbers do # We need to start with the 15, right? Let's use bc, our UNIX calculator. if test `echo $number%15 | bc` -eq 0 then echo -n "FizzBuzz " # Now we test for 3 elif test `echo $number%3 | bc` -eq 0 then echo -n "Fizz " # Now we test for 5 elif test `echo $number%5 | bc` -eq 0 then echo -n "Buzz " # If none of these match, we just return the number. else echo -n "$number " fi done # That's it!
Ok, that's a bit painful to look at: comments about the obvious, the deprecated `backquotes` for evaluation, unnecessary all_numbers
variable that doesn't make things cleaner, echo
piped to bc
(ugly and unnecessary external process — although, admittedly, for 100, speed is irrelevant), unquoted variables, etc. But hey, I've been there, too!
#02. Almost-graduating noob
#!/bin/bash # This is FizzBuzz. We return a sequence of numbers, but instead "Fizz" if # divisible by 3 and not 5, "Buzz" if by 5 and not 3, and "FizzBuzz" if by # both. for num in $(seq 1 $1) do if [ $(echo "$num % 15" | bc) -eq 0 ] then echo -n "FizzBuzz " elif [ $(echo "$num % 3" | bc) -eq 0 ] then echo -n "Fizz " elif [ $(echo "$num % 5" | bc) -eq 0 ] then echo -n "Buzz " else echo -n "$num " fi done
This one looks a bit cleaner. But one still smells a noob-like something in it.
#03. Balanced ex-noob
#!/bin/bash # This is FizzBuzz. We return a sequence of numbers, but instead "Fizz" if # divisible by 3 and not 5, "Buzz" if by 5 and not 3, and "FizzBuzz" if by # both. for num in $(seq "$1") do ((num % 15)) || { echo -n "FizzBuzz " ; continue ; } ((num % 3)) || { echo -n "Fizz " ; continue ; } ((num % 5)) || { echo -n "Buzz " ; continue ; } echo -n "$num " done | sed "s/ $/\n/"
Now, this is nicer: it doesn't pipe to bc
, uses result of arithmetic expressions as test, trims the trailing blank, etc.
It strikes a good balance between readability and terseness.
#04. Lisper 1
"Look at the repetitions from the balanced folk. Rule of three. You should put that in a separate function. Oh, you can't? Because of the continue
? So what you need is a macro! Yes, macros are fantastic. You see, with macros you— what, there's no defmacro
here? Sigh. Can't we improvise one, or something?" (note: yes, we can)
#!/usr/bin/env bash # This is FizzBuzz. fizztest() { # MACRO! (Sort of. This is bash, after all.) echo "((num % $1)) || { echo -n '$2 '; continue; }" } fizzbuzz() { # Run MACRO! for num in $(seq "$1") do . <(fizztest 15 FizzBuzz fizztest 3 Fizz fizztest 5 Buzz fizztest 1 "$num") done | sed "s/ $/\n/" } fizzbuzz "$1"
— Isn't this test of divisibility by 1 inefficient and unnecessary, Mr. Lisper?
— A bit inefficient, yes. Some 4% in my tests. But it doesn't matter for this use case. And it adds consistency and readability. And it's also one more chance to use a macro! MACROS!
#05. Lisper 2
"My dear Lisper friend did a good job in macro-ifying a bit this unlispy language that is Bash.
I just wished he had finished the job, you know. He's calling these fizztests repeatedly. Frankly."
#!/usr/bin/env bash # This is FizzBuzz. fizztest() { echo "((num % $1)) || { echo -n '$2 '; continue; }" } dofizztests() { local p p=$(($1*$2)) . <(for d in "$p" "$1" "$2" 1; do case $d in "$p") : FizzBuzz ;; "$1") : Fizz ;; "$2") : Buzz ;; 1) : '$num' ;; esac printf "%s\n" "fizztest $d $_" done) } fizzbuzz(){ for num in $(seq "$1") do . <(dofizztests 3 5) done | sed "s/ $/\n/" } fizzbuzz "$1"
(Is it just me or this didn't seem like an improvement over Lisper 1?)
#06. Array fan
"Good grief, Lisper 2. You could have used an associative array. Bash has those, you know."
#!/usr/bin/env bash # This is FizzBuzz. fizztest() { echo "((num % $1)) || { echo -n '$2 '; continue; }" } dofizztest() { declare -A fb fb[1]='"$num"'; fb[3]="Fizz"; fb[5]="Buzz"; fb[15]="FizzBuzz" . <(for d do echo fizztest "$d" "${fb[$d]}" done) } fizzbuzz(){ for num in $(seq "$1") do . <(dofizztest 15 3 5 1) done | sed "s/ $/\n/" } fizzbuzz "$1"
(Is it just me, or is Lisper 1's the clearest of the three in spite of the repetition? In fact, Balanced Basher's seems clearest of all four. Sorry, Lispers.)
#07. Caseful
"The two noobs from the beginning use all these ifs
and elifs
. Ugh. They don't know case
yet, the noobs."
#!/usr/bin/env bash # This is FizzBuzz. We all know it. whichfizz() { case "$(("$1" % 15))" in 0) : "FizzBuzz" ;; *) case "$(("$1" % 3))" in 0) : "Fizz" ;; *) case "$(("$1" % 5))" in 0) : "Buzz" ;; *) : "$1" esac esac esac echo -n "$_ " } fizzbuzz() { seq "$(($1-1))" | while read -r num do whichfizz "$num" done whichfizz "$1" | sed "s/ $/\n/" # ↑ So we can trim the trailing whitespace without "clogging the pipe". # Not that it makes any difference for small numbers. Not for 100. # But what if you want to watch a large stream of FizzBuzz numbers # flowing to STDOUT? } fizzbuzz "$1"
#08. Simple case
"My friend, I also like case
. It's faster.
But we don't really need three levels of nesting, do we? A single one would suffice.
#!/usr/bin/env bash # This is FizzBuzz. We all know it. whichfizz() { case "$(("$1" % 3))$(("$1" % 5))" in [^0][^0]) : "$1" ;; 0[1-4]) : "Fizz" ;; [1-2]0) : "Buzz" ;; 00) : "FizzBuzz" ;; esac echo -n "$_ " } fizzbuzz() { seq "$(($1-1))" | while read -r num do whichfizz "$num" done whichfizz "$1" | sed "s/ $/\n/" } fizzbuzz "$1"
#09. Simpler case
"But you aren't using case
to its full potential: why four tests when three are enough? Hint: &"
#!/usr/bin/env bash # This is FizzBuzz. We all know it. en() { printf "%s" "$*";} whichfizz() { case "$(("$1" % 3))$(("$1" % 5))" in [^0][^0]) en "$1" ;; 0[0-4]) en "Fizz" ;;& [0-2]0) en "Buzz" ;; esac en " " } fizzbuzz() { seq "$(($1-1))" | while read -r num do whichfizz "$num" done whichfizz "$1" | sed "s/ $/\n/" } fizzbuzz "$1"
#10. Short-circuited
"Jesus! Caseful basher knows what she's doing, but... argh. The thing keeps drifting to the right.
Neither case
nor if
, folks. Cut that noise. Brace yourselves.
P.S.: And why aren't you all testing your inputs to harden your FizzBuzz against the Bobby Tables of the world? Very important here. Haven't you any sense of proportion?"
#!/usr/bin/env bash # This is FizzBuzz. We all know it. whichfizz() { (($1%5!=0)) && { (($1%3!=0)) && : "$1" || : "Fizz" } || { (($1%3==0)) && : "FizzBuzz" || : "Buzz" } printf "%s " "$_" } natural() [[ "$1" =~ ^[0-9]+$ ]] # We test only the main input, once: no need for testing repeatedly inside the # loop in our particular case, since we know "$i" will be a natural. fizzbuzz() { natural "$1" && for ((i=1;i<=$1;i++)) { whichfizz "$i";} echo } fizzbuzz "$1"
#11. Stylish practical
"All those fancy tests of divisibility have a cost — and these folks are testing every single number! Instead of testing, why don't we just go over the regular sequence three times and jump lines to replace things? And we can make it short and readable and elegant."
#!/usr/bin/env bash # FizzBuzz. fizzbuzz() (seq "$1" | sed '3~3 s/.*/Fizz/ 5~5 s/.*/Buzz/ 15~15 s/.*/FizzBuzz/' | xargs) fizzbuzz "$1"
(Now, ain't that cute? Possibly my favorite.)
#12. Pipeless (aka: The Herestringer)
"I like your style and simplicity, my friend.
Know what would be even more stylish? To make it mimic the actual function application order: y=xargs(sed(seq(x)))
.
In other words: here-strings."
#!/usr/bin/env bash # FizzBuzz. fizzbuzz() (xargs <<< $(sed '3~3 s/.*/Fizz/ 5~5 s/.*/Buzz/ 15~15 s/.*/FizzBuzz/' <<< $(seq "$1"))) fizzbuzz "$1"
#13. Purist
"What?! seq
? sed
? xargs
?
You don't need to spawn processes to call external utilities.
You don't need dependencies.
Sometimes you don't even need braces!
Listen to me: you can do it all with just Bash."
#!/usr/bin/env bash # FizzBuzz. prs() { printf '%s ' "$1";} fizzify() if (("$1"%15==0)); then prs "FizzBuzz" elif (("$1"% 3==0)); then prs "Fizz" elif (("$1"% 5==0)); then prs "Buzz" else prs "$1" fi fizzbuzz() for ((i=1;i<"$1";i++)) do fizzify "$i" done fizzbuzz "$1" : "$(fizzify "$1")" printf "%s\n" "${_% }"
#14. Straight-case practical semi-purist
"Purist, this is great. But all these if-then
and C-like syntax... a bit ugly, don't you think? And can't we just list the few remainders and make it more straightforward and readable — even if sacrificing some generality?"
#!/usr/bin/env bash # This is FizzBuzz. We all know it. fizzbuzz() { printf "%s" "1" while read num do case $((num % 15)) in 3|6|9|12) : "Fizz" ;; 5|10) : "Buzz" ;; 0) : "FizzBuzz" ;; *) : "$num" esac printf "%s" " $_" done < <(seq 2 "$1") echo } fizzbuzz "$1"
#15. Exotic casual bashgolfer
"Shorter, folks. Shorter. Let's play some casual golf."
#!/usr/bin/env bash fizzbuzz() for((i=0;i++<"$1";)) { ((r=i%3==0?i%5==0?3:1:i%5==0?2:0)) case $r in 0): "$i";; 1): Fizz;; 2): Buzz;; 3): FizzBuzz esac; printf "%s " "$_";} fizzbuzz "$1"
This one is almost... as if...
I'm not sure what to think of it.
- It starts with a promise of obscurity, but the "casing" saves it.
- It wants terseness, but doesn't overdo it.
- The lack of trailing newline is ok.
It's quite readable.
#16. Haskeller
#!/usr/bin/env bash # -- No Haskell in this machine, so it seems that I will need to use # -- <contempt>bash</contempt>, of all things. Sigh. # This is FizzBuzz. -- And to think it'd be only half a dozen lines # -- in Haskell... sigh. # -- Ok. Let's do it, hmm, the bash way. # $ man bash<RET> # /bananas<RET> # Pattern not found # -- !? # /lenses<RET> # Pattern not found # -- !!! C'mon. # /zygohistomorphic.prepromorphism<RET> # Pattern not found # -- SIGH... How boring. # /monad<RET> # Pattern not found # -- You gotta be kidding me! # /fmap<RET> # Pattern not found # -- The horror. The horror. # * * * # -- Let's pretend for a moment that this... "language"... can do functors. # fmap :: Functor f => (a -> b) -> f a -> f b fmap() { . <(sed -E \ 's/^(.*)[.](.*)/while read -r x; do \1 "$x"; done <<< "$\(\2\)"/' \ <<< "$*"); } # show :: Show a => a -> String show() { printf '%s ' "$*"; } # putStrLn :: String -> IO () putStrLn() { printf '%s\n' "$*"; } # isNatural :: a -> Bool isNatural() [[ "$1" =~ ^[0-9]+$ ]] # isDivisible :: Natural -> Natural -> Bool isDivisible() { (("$2"!=0)) && (("$1"%"$2"==0)) && true || false; } #-- no "Justs", no "Maybes". sigh. # makeSequence :: Natural -> [Natural] makeSequence() { seq "$1"; } # fizzify :: Int -> String fizzify() if isNatural "$1"; then if isDivisible "$1" 15; then show "FizzBuzz" elif isDivisible "$1" 3; then show "Fizz" elif isDivisible "$1" 5; then show "Buzz" else show "$1" fi fi # -- Now, THAT looks almost decent! # fizzbuzz :: Int -> [String] fizzbuzz() (fmap fizzify . makeSequence "$1" putStrLn) # -- Can't we change this prompt, maybe? Say: # -- show "λ> fizzbuzz $1"; putStrLn # -- Anyway: fizzbuzz "$1"
Pick one of these and enjoy!
fizzbuzz 300 | xargs -n15 | column -ts$' ' | grep -E '..zz|$'
Who is the fastest FizzBuzz in the West? The Profiler steps in.
"Speed, folks. Efficiency. I don't care how much you comment it. I don't care if you code-golf. I care if it's fast. Is your thing fast? Can the world sleep at night with the tranquility that comes from knowing that their FizzBuzz won't lag or hang at critical moments of their lives?"
So. Someone should create a repo crowdsourcing FizzBuzz in many languages to test their speed at standard inputs of 10⁴ and 10⁶. The world deserves this.
While this doesn't happen, allow me to offer a modest contribution that will reduce the anxieties of The Profiler: a Bash FizzBuzz Benchmark.
Benchmarking the functions
#!/usr/bin/env bash # # 1bench.sh # Default TIMEFORMAT is: $'\nreal\t%3lR\nuser\t%3lU\nsys\t%3lS' benchOne() { echo -en "$1\t" TIMEFORMAT="%R" # %lR time { "$@" >/dev/null;};} testOne() { echo -en "$1\t" # Here-string guarantees a trailing space cat <<< "$("$@")";} showFunctions() { # File or function names are PIPED TO. # ARG1 is the mapping function to apply. # Arguments to each function are the other arguments. funs="$(cat -)" mapfunction="$1"; shift local max max="$(wc -L <<< "$funs")" while read fun do printf "%$((max-${#fun}))s" "$mapfunction" "$fun" "$@" done <<< "$funs" } benchAll() { # File or function names are PIPED TO. # Arguments to each function are inputs. showFunctions benchOne "$@" } testAll() { # File or function names are PIPED TO. # Arguments to each function are inputs. showFunctions testOne "$@" }
Running the tests
After creating individual script files for every function, we put them all in the presented order
<<<"noob almost-grad balanced lisper1 lisper2 array-fan caseful simple-case simpler-case short-circuited stylish-practical pipeless purist straight-case exotic haskeller" \ tr " " "\n" | sed "/^$/d; s/$/.sh/" > order.txt
and see if all of them give us the expected results:
PATH="$PATH:$PWD" # make sure all .sh files here are in $PATH source 1bench.sh cat order.txt | testAll 15
noob.sh 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz almost-grad.sh 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz balanced.sh 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz lisper1.sh 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz lisper2.sh 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz array-fan.sh 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz caseful.sh 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz simple-case.sh 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz simpler-case.sh 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz short-circuited.sh 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz stylish-practical.sh 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz pipeless.sh 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz purist.sh 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz straight-case.sh 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz exotic.sh 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz haskeller.sh 1 2 Fizz 4 Buzz Fizz 7 8 Fizz Buzz 11 Fizz 13 14 FizzBuzz
Looks good.
So let's see the times. I ran
cat order.txt | benchAll "$n"
for n=1, and all do it in ~0.032s. We take this to be the fixed cost of loading the script.
Then I ran it for 100, 10000 and 1000000, and sorted them in the table below.
(Some of them I interrupted: too slow.)
sec %of_noob rank cluster ----------------------- -------------- ----- ------- n: 100 10k 1M 100 10k (10k) ----------------------- -------------- ----- ------- noob.sh 1.231 120.886 ? 100.00 100.00 15 5 almost-grad.sh 1.280 127.623 ? 104.00 105.57 16 5 balanced.sh 0.033 0.521 48.99 2.68 0.43 3 2a lisper1.sh 0.190 17.526 ? 15.43 14.50 12 4 lisper2.sh 0.401 39.173 ? 32.58 32.40 14 4 array-fan.sh 0.373 36.906 ? 30.30 30.53 13 4 caseful.sh 0.043 1.295 126.08 3.49 1.07 9 2a simple-case.sh 0.044 1.094 110.18 3.57 0.90 8 2a simpler-case.sh 0.046 1.558 156.60 3.74 1.29 10 2a short-circuited.sh 0.037 0.869 84.26 3.41 0.72 6 2a stylish-practical.sh 0.030 0.043 1.11 2.44 0.04 1 1 pipeless.sh 0.037 0.061 2.12 3.01 0.05 2 1 purist.sh 0.037 0.985 97.21 3.01 0.81 7 2b straight-case.sh 0.038 0.706 69.75 2.60 0.58 5 2a exotic.sh 0.031 0.633 61.66 2.52 0.52 4 2a haskeller.sh 0.074 3.349 331.75 6.01 2.77 11 3
"But something something significant digits!" —Physicist
Yeah, yeah.
Speed clusters, roughly
A first take on why results clustered as above. The clusters:
1 | No divisibility testing: "blind" spaced replacements instead. |
2a | Uses case-esac , short-circuiting (&& , ❘❘ ), null command (: ), and/or continue |
2b | Uses if-fi (slow) in a C-style for loop (fast). |
3 | Uses if-fi (slow) in a while-read loop fed from seq lines (not as fast). |
4 | Opens subshells inside the loop ("macros!"). |
5 | Bash's native $((exp)) syntax not used: expression echoed and piped to bc inside the loop. |
Style and speed
When I concocted these characters, I was at first thinking mostly about style, somewhat oblivious to performance considerations. I found it intriguing that the two to-me most style-wise noob-looking ones ended up also being the slowest. I also found it intriguing that the fastest one ended up being the shortest, most readable, and to me most elegant one: the Stylish practical.
But there's something counter-intuitive going on with this one. See, the lines that are multiple of 15 are being written four times: once when populating it with integers, then again replacing them with "Fizz", then with "Buzz", then with "FizzBuzz". This looks like a terrible waste — a blunt choice of algorithm that should be doomed to lower performance.
And yet, it's the fastest. Why?
Not so inefficient, after all
From all Bash solutions here, only this one and its similar "Pipeless" aren't doing any test of divisibility. Those tests are rather expensive, and being able to do away with them leads to improvements. Huge improvements. Just look at the table.
But wait a second. Just because the divisibility tests aren't explicit, it doesn't mean that they aren't being done. How does GNU sed knows if line 30 should be replaced or not when sed '15~15 s/.*/FizzBuzz/'
is run? Isn't it also testing for divisibility?
I haven't looked at its source, but I suspect that no, it probably isn't. My guess is that it seeks line breaks keeping a simple incremental counter. Or maybe something else. In any case, this is so much faster than our $((n%15))
that the "inefficiency" of repainting the lines ends up being an irrelevant cost.
Herestrings are slower for bigger numbers
I also found the "Pipeless" intriguing. So here-strings are slower than pipes, after all. Irrelevant for smaller numbers, but it then becomes 50% slower for 10k, 100% slower for 1M. Why?
My understanding is that it's because here-strings do not do line-by-line streaming as pipes do. Rather, the $(command1)
is stored in memory, and only upon completion the command2 <<<
is applied to it. So this would have some strain on memory, which would be slower than plain streaming.
Loop types: avoid ifs, prefer C-style
Both case-esac
and short-circuiting (&&
, ||
) are faster than if-fi
.
And a C-style indexed loop is faster than piping seq
to a while-read
loop.
Subshells inside loops: very slow.
Want to open a subshell once? That's fine.
- The fastest function here is being defined between parentheses, see? No braces. Negligible cost.
- Feeding a
while-read
loop with a subshell that runsseq
? No problem. It's only once.
But repeatedly opening a subshell inside a loop, like our array fan and Lispers? This will noticeably slow down your multi-thousand FizzBuzz activities.
And piping to bc
inside a loop...
...seems to be the most costly of all.
Bonus: the extra-lazy Bashkeller
"Greetings, fellow Haskeller-who-suffers-Bash. I admire your effort and patience. Do note that your evaluations can be optimized by changing the order of tests. Your fizzify is the most elegant, but have you tried to start with the test for numbers that aren't divisible by either?"
Let's run
time haskeller.sh 50000 >/dev/null
using the Haskeller's code, and normalize the time to 1000
. Here is the fizzify function that it uses:
# fizzify :: Int -> String fizzify() if isNatural "$1"; then if isDivisible "$1" 15; then show "FizzBuzz" elif isDivisible "$1" 3; then show "Fizz" elif isDivisible "$1" 5; then show "Buzz" else show "$1" fi fi
By replacing it with the alternative versions below, the score drops to 985
and 903
, respectively. So the order matters, and the third one, which does less tests than the original, is faster.
# fizzify :: Int -> String fizzify() if isNatural "$1"; then if ! isDivisible "$1" 3 && ! isDivisible "$1" 5; then show "$1" elif isDivisible "$1" 3; then if isDivisible "$1" 5; then show "FizzBuzz" else show "Fizz" fi else show "Buzz" fi fi
# fizzify :: Int -> String fizzify() if isNatural "$1"; then if ! isDivisible "$1" 5; then if ! isDivisible "$1" 3; then show "$1" else show "Fizz" fi else if ! isDivisible "$1" 3; then show "Buzz" else show "FizzBuzz" fi fi fi
Exercise for the math-inclined reader
Straight-case practical semi-purist basher dares to utter the phrase "even if sacrificing some generality"... and then goes ahead and hardcodes multiples of 3 and 5 in the case
statements!
Gasp!
Do not allow such blasphemies to pass unnoticed. Show them that the only correct way of doing FizzBuzz is, obviously, through the utmost generality — with arbitrary divisors, fully functional, thoroughly parameterized. Euler totient coefficients, maybe? Or perhaps some generalized version of its meta-generalization? We urge you to write it.
In Bash, of course.