Un des problèmes ultra classiques d’entretien, c’est d’afficher les nombres du jeu fizzbuzz.

On va voir comment aller au dela.

Le problème

Bon, déjà, l’énoncé du problème:

interviewer: OK, so I need you to print the numbers from 1 to 100, except that if the number is divisible by 3 print “fizz”, if it’s divisible by 5 print “buzz”, and if it’s divisible by 15 print “fizzbuzz”.

Si vous n’avez jamais codé ce problème, prenez un moment pour y réfléchir, et essayer de le faire.

Une première solution

Voici une solution en python:

def fizzbuzz(n:int) -> int|str:
    if n%3 == 0 and n%5 ==0:
        return 'fizzbuzz'
    if n%3 == 0:
        return 'fizz'
    if n%5 == 0:
        return 'buzz'
    return n

for i in range(100):
    print(fizzbuzz(i))

Et une trace d’exécution:

$ python fizzbuzz.py 
1
2
fizz
4
buzz
fizz
7
8
fizz
buzz
11
fizz
13
14
fizzbuzz
16
17
fizz
19
[…]

Il y a deux difficultés:

• gérer “n est divisible par 3”. Ca se traduit par “le reste de la division par 3 vaut 0”, ce qui se traduit généralement par l’opérateur %: n % 3 == 0
• gérer l’ordre des if. Si vous mettez if n%3 == 0 and n%5 ==0 en dernier, ca ne marche plus.

Il y a plein de choses à dire

Une “meilleure” solution en Python

Il est amusant de voir qu’en python, on peut répondre par un one-liner:

def fizzbuzz(n:int) -> int|str:
    return 'fizz'*(n%3==0)+'buzz'*(n%5==0) or n

Pour comprendre ce one-liner, il faut savoir qu’en python:

• ‘fizz’ * 0 = ‘’
• ‘fizz’ * 1 = ‘fizz’
• un booléen est aussi un entier, avec False = 0 et True = 1

Ca fait la même chose que précédemment: si n est divisable par 3 ou 5, on inclus le bout de chaine correspondant. Et donc s’il est divisible par les deux, on a bien fizzbuzz.

S’il n’est divisible par aucun des deux, on a une chaine vide, et on renvoie le nombre de départ.

Alors oui, c’est pas du code qui arrivera en production tous les jours, mais après avoir levé les yeux au ciel lorsque j’ai vu cette approche la première fois, je lui trouve une certaine élégance.

Ruby, qui est pourtant très expressif, ne permet pas cette concision:

def fizzbuzz(n)
    s = 'fizz'*((n%3==0)?1:0)+'buzz'*((n%5==0)?1:0)
    if s.length > 0 then return s else return n end
end

(0..15).each do |n|
    puts fizzbuzz(n)
end

On est obligé de transformer le booléen en entier via une opération ternaire, et d’inclure une seconde condition ternaire pour renvoyer la bonne valeur.

Aller hyper vite

Bon résoudre le problème, c’est une chose, mais et si on essayait de le résoudre très vite? Quelqu’un a posé la question de quel débit on pouvait avoir ?

La réponse du vainqueur est de l’ordre de 50GiB/s, soit environ 10x plus que le second. La solution est en assembleur. L’auteur y donne quelques explications, honnêtement j’ai été content de lire un second writeup.

En gros:

• des instructions SIMD pour faire des batch de traitement. L’appli traite 64 byte de fizz buzz toutes les 4 instructions CPU.
• utilisation des instructions AVX2 pour aller encore plus vite
• utilisation uniquement du cache L2, qu’on découpe en deux: une partie pour stocker l’affichage, un partie pour stocker le dernier résultat
• défragmentation de la mémoire (!) utilisée, via un appel système.
• alignement de la mémoire: 2 buffer d’I/O utilisent 2Mo, alors qu’ils n’ont pas besoin d’autant. Cela permet de rester sur des pages entières.
• utilisation de l’appel système vmsplice plutôt que write pour éviter des copies de mémoire inutiles.

Avec Tensorflow

Tensorflow est une librairie d’apprentissage statistique très largement surdimensionnée pour ce simple problème. Si vous avez aimé ce que vous avez lu jusqu’à présent, vous adorerez ce… compte rendu d’entretien.

FizzBuzz enterprise edition

Tant qu’on est dans l’overengineering, faut qu’on parle de FizzBuzz enterprise edition.