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)
../_images/BJKST_enonce_3_0.png

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)
../_images/BJKST_enonce_6_1.png