FizzBuzz

Hra FizzBuzz, prověřující schopnost hráčů nahrazovat v posloupnosti přirozených čísel násobky 3 slovem "Fizz", násobky 5 slovem "Buzz" a společné násobky obou slovní kombinací "FizzBuzz", bývá i často užívaným námětem pro testování stylu programátorů během přijímacích pohovorů. Vhodné téma i pro nás. Vodítek k tomu, co se od dotazovaných může očekávat, je na webu nepočítaně. My nabereme inspiraci z blogu FizzBuzz in Too Much Detail a porovnáme si svá řešení s benchmarkem High throughput Fizz Buzz.

Pro varianty algoritmu a styl si zde vybereme Python, pro rychlost pak zkusíme Fortran.

Třikrát mod

Od počátku budeme parametrizovat oba dělitele pomocí fizz=3 a buzz=5 a délku procházené posloupnosti jménem nmax. Jednotlivé varianty budeme vkládat do funkcí o vstupním argumentu n udávajícím testované číslo a s výstupní hodnotou obsahující buď totéž číslo, není-li dělitelné ani jedním z fizz a buzz, nebo příslušný řetězec. Tyto výstupy budeme pro úsporu místa i snadnější vizuální kontrolu výsledků klást za sebe oddělené třeba čárkou, tedy pro nmax=20:

1,2,Fizz,4,Buzz,Fizz,7,8,Fizz,Buzz,11,Fizz,13,14,FizzBuzz,16,17,Fizz,19,Buzz

Drží-li se člověk předloženého popisu, na mysli rychle vytane řešení pomocí tří testů dělitelnosti, realizovaných testem nulovosti zbytků po dělení jednak společným násobkem, jednak jednotlivými děliteli. Možnost psát místo testu dělitelnosti společným násobkem složený test n%fizz==0 and n%buzz==0 a mít tak ve funkci čtyři testy dělitelnosti, jen zmiňujeme.

fizz=3
buzz=5
nmax=20

# FizzBuzz by 3 modulo operators
def mod3FizzBuzz(n):
  if n%(fizz*buzz)==0:
    result='FizzBuzz'
  elif n%fizz==0:
    result='Fizz'
  elif n%buzz==0:
    result='Buzz'
  else:
    result=str(n)
  return result

for n in range(1,nmax+1):
  print(mod3FizzBuzz(n),end=',')
print('mod3FizzBuzz')

Dvakrát mod

Když už nám oko padlo na operace modulo, můžeme jejich počet snížit tím, že nahradíme výstup při dělitelnosti společným násobkem řetězením obou dílčích výstupů. Zda ušetření jedné operace modulo náhradou za operaci řetězení nepřinese negativní efekt při snaze o rychlost běhu, to si prověříme později.

def mod2FizzBuzz(n):
  result=''
  if n%fizz==0:
    result+='Fizz'
  if n%buzz==0:
    result+='Buzz'
  if result=='':
    result=str(n)
  return result

Pythonská zkratka nahrazující poslední tři řádky: return result or str(n).

Pro milovníky stručných zápisů je zde varianta, která aritmetickým složením obou testů vytváří hodnoty 0, 1, 2, 3 a ze čtveřice možných výstupů pak tímto indexem vybírá:

def plusFizzBuzz(n):
  return (str(n),'Fizz','Buzz','FizzBuzz')[int(n%fizz==0)+2*int(n%buzz==0)]

Pro milovníky novinek je zde obdobné řešení pomocí konstrukce match case, která se objevila až v Pythonu 3.10 (roku 2021):

def plusFizzBuzz_match_case(n):
  match int(n%fizz==0)+2*int(n%buzz==0):
    case 0: result=str(n)
    case 1: result='Fizz'
    case 2: result='Buzz'
    case 3: result='FizzBuzz'
    case _: result='****'
  return result

Jediný mod

Šetřit s operací modulo můžeme ještě víc, vytvoříme-li si posloupnost možných výsledků pro všechny zbytky po dělení společným násobkem fizz*buzz, zde ovšem jen pro naše specifické dělitele fizz=3 a buzz=5:

def mod1FizzBuzz(n):
  return ('FizzBuzz',str(n),str(n),'Fizz',str(n),'Buzz','Fizz',str(n),str(n),'Fizz','Buzz',str(n),'Fizz',str(n),str(n))[n%(fizz*buzz)]

Tak jako výše, totéž bez potřeby patnáctice lze zapsat pomocí match case. Místo toho zde přineseme variantu, která znakové symboly možných výsledků shrnuje do řetězce a poté pomocí těchto symbolů vybírá odpovídající výstupní text z pythonského slovníku. Vytváření řetězce při každém volání funkce by jistě bylo vadou při snaze o rychlost, kterou patrně nepodpoří ani užití slovníku.

def stringFizzBuzz(n):
  s='2NNFNBFNNFBNFNN'
  return {'N':str(n),'F':'Fizz','B':'Buzz','2':'FizzBuzz'}[s[n%(fizz*buzz)]]

Zobecnění: více dělitelů

V dalším budeme FizzBuzz zobecňovat. Jako první cíl si vytyčíme libovolný počet dělitelů. Z našich variant je k tomu nejvhodnější funkce mod2FizzBuzz, kde cíle dosáhneme pouhým přidáváním dalších podmínek s případným řetězením výstupu. Pokud si sdružíme dělitele a příslušné texty do dvojic a ty pak do n-tice, v defaultu tedy (('Fizz',fizz),('Buzz',buzz)), můžeme vše vyjádřit cyklem:

def triggerFizzBuzzTupleIndex(n,triggers=(('Fizz',fizz),('Buzz',buzz))):
  result=''
  for i in range(len(triggers)):
    if n%triggers[i][1]==0: result+=triggers[i][0]
  return result or str(n)

def triggerFizzBuzzTuple(n,triggers=(('Fizz',fizz),('Buzz',buzz))):
  result=''
  for t in triggers:
    if n%t[1]==0: result+=t[0]
  return result or str(n)

Po vzoru shora citovaného blogu jsme n-tice dvojic nazvali triggers, neboť dělitel vlastně spouští akci přetvářející prvky vstupní posloupnosti, a v rozhraní funkce jsme uvedli jako volitelný argument s default hodnotou této n-tice platnou pro standardní FizzBuzz. V první funkci indexujeme prvky n-tice pomocí integer indexu, v druhé příhodněji procházíme hodnoty celé n-tice bez užití indexu. Použitím v sekvenci

# standard FizzBuzz
for n in range(1,nmax+1):
  print(triggerFizzBuzzTuple(n),end=',')
print('triggerFizzBuzzTuple')

# FizzBuzzZazz
for n in range(1,fizz*buzz*7+1):
  print(triggerFizzBuzzTuple(n,(('Fizz',fizz),('Buzz',buzz),('Zazz',7))),end=',')
print('triggerFizzBuzzTuple')

zaprvé ověříme shodu se standardem a zadruhé přidáme k dvojici dělitelů jako třetího sedmičku.

Přidáme ještě obdobnou variantu s užitím slovníků, kde prvky nečíslujeme, ale pojmenujeme mnemotechnickými jmény text a divisor:

def triggerFizzBuzzDict(n,triggers=(dict(text='Fizz',divisor=fizz),dict(text='Buzz',divisor=buzz))):
  result=''
  for t in triggers:
    if n%t['divisor']==0: result+=t['text']
  return result or str(n)

Zobecnění: predikáty

FizzBuzz s testováním dělitelnosti by se mohl brzy ohrát, nabízí se tedy nahradit test dělitelnosti libovolnou logickou funkcí neboli predikátem. Pro standardní verzi si připravíme funkce ffizz a fbuzz, obě spojíme s příslušnými texty opět v n-tici slovníků a získáme toto:

fizz=3; buzz=5; nmax=20

def ffizz(n):
  return n%fizz==0

def fbuzz(n):
  return n%buzz==0

def predicateFizzBuzz(n,triggers=(dict(text='Fizz',predicate=ffizz),dict(text='Buzz',predicate=fbuzz))):
  result=''
  for t in triggers:
    if t['predicate'](n): result+=t['text']
  return result or str(n)

# standard FizzBuzz
for n in range(1,nmax+1):
  print(predicateFizzBuzz(n),end=',')
print('predicateFizzBuzz')

# squares and cubes
for n in range(1,31):
  print(predicateFizzBuzz(n,
    (dict(text='Fizz',predicate=lambda n: int(n**0.5)**2==n),
     dict(text='Buzz',predicate=lambda n: int(n**(1/3))**3==n))),end=',')
print('predicateFizzBuzz')

Prvním cyklem jsme vypsali standardní FizzBuzz sekvenci a druhým jsme vyznačili druhé a třetí celočíselné mocniny. Predikáty jsou zde tvořeny jednovýrazovými lambda funkcemi, testujícími odmocnitelnost n beze zbytku.

Map–Filter–Reduce

Trojice funkcí map, filter a reduce tvoří základ funkcionálního programování, v informatické komunitě ceněného stylu. Tyto vcelku obecné transformace nahrazují mnoho variant cyklů a podmínek a neuškodí uvědomit si dílčí kroky svého algoritmu z této perspektivy. Mapování transformuje vstupní hodnoty na výstupní hodnoty, filtr vybírá ze vstupních hodnot podle příslušného predikátu a redukce kumuluje ze série vstupních hodnot jedinou výstupní. Jinde jsme v tomto duchu zpracovali ukázku se sumací lichých čísel.

Ve FizzBuzzu vidíme dva filtry pro dělitelnost 3 a 5, mapování výstupu filtrů na slova "Fizz" a "Buzz" a redukci těchto slov řetězením do jediného výstupního slova. Zde:

import numpy
fizz=3; buzz=5; nmax=20

def ffizz(n):
  return n%fizz==0

def fbuzz(n):
  return n%buzz==0

def mapFilterReduceFizzBuzz(n,triggers=(dict(text='Fizz',predicate=ffizz),dict(text='Buzz',predicate=fbuzz))):
  import functools
  parts=list(map(lambda t: t['text'],filter(lambda t: t['predicate'](n),triggers)))
  result=functools.reduce(lambda a,b:a+b,parts) if parts else str(n)
  return result

# standard FizzBuzz
for n in range(1,nmax+1):
  print(mapFilterReduceFizzBuzz(n),end=',')
print('mapFilterReduceFizzBuzz')

# squares and cubes
for n in range(1,31):
  print(mapFilterReduceFizzBuzz(n,
    (dict(text='Fizz',predicate=lambda n: int(n**0.5)**2==n),
     dict(text='Buzz',predicate=lambda n: int(n**(1/3))**3==n))),end=',')
print('mapFilterReduceFizzBuzz')

Vhodný okamžik vrátit se k blogu FizzBuzz in Too Much Detail a přečíst si v něm závěrečný názor autora. Shrnut je v akronymu YAGNI, You Ain’t Gonna Need It, a vůbec není přehlíživý k nejjednodušším řešením. Navíc, když teď budeme směřovat k rychlým řešením, shledáme slibný potenciál patrně také v jednoduchosti.

Skript, který obsahuje všechny naše varianty, spouští je a měří dobu jejich běhu, je tady: fizzbuzz.py. Nejjednodušší užití spočívá v nastavení nmax a spuštění pro kratší posloupnosti s výpisem hodnot pomocí python fizzbuzz.py, nebo pro delší řady bez jejich výpisu, jen s výpisem doby běhu pomocí python fizzbuzz.py > nul ve Windows a python fizzbuzz.py > /dev/null v Linuxu. (Doba běhu je směrována na standardní chybový výstup stderr, takže se zobrazí.) Budeme někde u milionu vypsaných a v /dev/null utopených čísel a slov za sekundu. Podíváme-li se do citovaného benchmarku na publikované rychlosti generování výstupu, máme co dohánět. (Náš pokus ve Fortranu: FizzBuzz rychle a zběsile.)

Domácí úkol: zrychlit FizzBuzz. Vyberte si 3 z uvedených funkcí (nebo vytvořte vlastní) a pokuste se dosáhnout co nejvyšší rychlosti výpisu (nebo výpočtu). Můžete si pomoci Numbou nebo některým z triků použitých v našem snažení (FizzBuzz rychle a zběsile), např. binárním výpisem nebo výpisem po blocích, nebo jakkoliv. Zrychlení pouze Numbou má 14denní limit na zpracování, ostatní postupy jsou bez časového limitu.