.. _BJKSTenoncerst: ========================================================= 1A.algo - BJKST - calculer le nombre d’éléments distincts ========================================================= .. only:: html **Links:** :download:`notebook `, :downloadlink:`html `, :download:`python `, :downloadlink:`slides `, :githublink:`GitHub|_doc/notebooks/td1a_algo/BJKST_enonce.ipynb|*` 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 `__. .. code:: ipython3 from jyquickhelper import add_notebook_menu add_notebook_menu() .. contents:: :local: 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. .. code:: ipython3 from pyquickhelper.helpgen import NbImage NbImage("images/bjkst.png", width=600) .. image:: BJKST_enonce_3_0.png :width: 600px 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. .. code:: ipython3 from pyquickhelper.helpgen import NbImage NbImage("images/bjkst2.png", width=600) .. parsed-literal:: c:\python36_x64\lib\site-packages\sphinx\util\compat.py:40: RemovedInSphinx17Warning: sphinx.util.compat.Directive is deprecated and will be removed in Sphinx 1.7, please use docutils' instead. RemovedInSphinx17Warning) .. image:: BJKST_enonce_6_1.png :width: 600px