1A.algo - BJKST - calculer le nombre d’éléments distincts#
Links: notebook
, html, python
, slides, GitHub
Comment calculer le nombre d’éléments distincts d’un ensemble de données quand celui-ci est trop grand pour tenir en mémoire. C’est ce que fait l’algorithme BJKST.
from jyquickhelper import add_notebook_menu
add_notebook_menu()
Exercice 1 : première version#
L’extrait qui suit est tiré de Counting distinct elements in a data stream. Il faut implémenter l’idée développé dans le second paragraphe.
from pyquickhelper.helpgen import NbImage
NbImage("images/bjkst.png", width=600)
Saurez-vous convertir ce texte en un algorithme ?
Exercice 2 : version plus rapide#
L’extrait qui suit est tiré de CS85: Data Stream Algorithms, Lecture Notes (page 17). Il faut implémenter l’idée développé dans le second paragraphe.
from pyquickhelper.helpgen import NbImage
NbImage("images/bjkst2.png", width=600)
c:python36_x64libsite-packagessphinxutilcompat.py:40: RemovedInSphinx17Warning: sphinx.util.compat.Directive is deprecated and will be removed in Sphinx 1.7, please use docutils' instead. RemovedInSphinx17Warning)