GRAL - 2ème Partie
Master STL, 1er semestre 2015-2016 - Michèle Soria et Fabien Viger
Contact: fabien [point] viger sur gmail.
Planning
Le détail des séances est indicatif; il changera sans doute pour s'adapter à notre avancement.
Le cours a lieu à Jussieu, en salle T18 (plan), les Vendredi de 09:00 à 12:45, avec une pause au milieu.
- Vendredi 4 Décembre: 1ère séance.
- Implantation de la version "simple" d'HyperLogLog: Figure 1 de la page 3
- Tests basiques
- Mesure de performance, tuning: optimisations, utilisation de template<int p>
- Vendredi 11 Décembre: 2ème séance.
- Passage à 64bit
- Test étendu; choix de la fonction de hachage
- Mesure experimentale du biais de l'estimateur brut
- Mesure experimentale du biais de LINEARCOUNTING
- Correction de l'estimateur brut et adaptation du choix de l'algo
- Introduction des devoirs de vacances
- Vendredi 8 Janvier: 3ème séance.
- Représentation creuse pour les petites cardinalités
- Mise à jour batch
- Expériences
- Vendredi 15 Janvier: 4ème séance (dernier cours!)
- Passage à p=25 pour la représentation creuse.
- Compression de la représentation creuse (varint + delta).
- Compression de la représentation creuse (supprimer le compteur si inutile).
- Vendredi 22 Février: Soutenance de projet
- Vendredi 29 Février: Rendu des rapports (pas de séance)
Resources
- Squelette de la classe Hll, et des fichiers test:
hll.tar.gz
- Le projet xxhash
- Trucs et astuces:
- Utilisez les types uint32 et uint64
- Opérateurs << et >>, ^, |, &.
- Vous pouvez utiliser le très rapide __builtin_clz
(qui permet de compter le nombre de bits de poids forts à zéro, si vous utiliser g++!).
Vous pouvez aussi écrire votre propre boucle for