.. _2022hashrst: ============================= Répartition, table de hashage ============================= .. only:: html **Links:** :download:`notebook <2022_hash.ipynb>`, :downloadlink:`html <2022_hash2html.html>`, :download:`python <2022_hash.py>`, :downloadlink:`slides <2022_hash.slides.html>`, :githublink:`GitHub|_doc/notebooks/td1a_home/2022_hash.ipynb|*` Il est facile de répartir des élèves en quatre groupe après les avoir triés par ordre croissant, les élèves dont les noms de famille commencent par *A* dans le premier groupe et ainsi de suite… Cette répartition peut poser un problème éthique parfois. On souhaite écrire une fonction de répartition qui affecte les étudiants dans un groupe parmi quatre : - Cette fonction prend comme entrée le nom et le prénom. - Le résultat ne dépend pas des autres noms présents dans la classe. - Les groupes sont à peu près de taille identique. .. code:: ipython3 from jyquickhelper import add_notebook_menu add_notebook_menu() .. contents:: :local: .. code:: ipython3 %matplotlib inline Q1 - première lettre -------------------- Ecrire une fonction qui retourne la distribution la première lettre de chaque personnage. Est-ce une distribution uniforme ? .. code:: ipython3 personnages = """ Jean Valjean Cosette Fantine Marius Pontmercy Gavroche Thénardier Antagonistes Javert Monsieur Thénardier Madame Thénardier Babet Claquesous Montparnasse Gueulemer Brujon Bamatabois Madame Victurnien Les Amis de l'ABC Enjolras Combeferre Courfeyrac Jean Prouvaire Feuilly Bahorel Lesgle Joly Grantaire Marius Pontmercy Personnages secondaires Amies de Fantine Favourite Dahlia Zéphine Amis de Félix Tholomyès Listolier Fameuil Blachevelle Autres Fauchelevent Mr Mabeuf Azelma Thénardier Toussaint Luc-Esprit Gillenormand Georges Pontmercy Évêque Myriel Baptistine Myriel Mme Magloire Petit-Gervais """ Q2 - somme ---------- On écrit une fonction qui fait la somme des lettres (avec la fonction `ord `__ par exemple). On calcule ensuite la distribution du résultat modulo 26. Est-ce uniforme ? Q3 - pseudo générateur ---------------------- On s’inspire d’un `générateur congruentiel linéaire `__. :math:`X_{n+1} = (22695477 X_n + 1) \mod 2^{32}` qu’on transforme en :math:`X_{n+1} = (22695477 (X_n + c_n) + 1) \mod 2^{32}` où :math:`c_n` est la n-énième lettre du nom du personnage. On prendra comme résultat le dernier nombre de la série :math:`X_n >> 16`, le tout module 26. On calcule de nouveau la distribution. Q4 - hash --------- On utilise un algorithme hashage implémenté par la librairie `hashlib `__. On transforme chaque nom des personnages et on calcule la distribution de la première lettre du *hash* obtenu. Q5 - light hash --------------- On s’inspire de la page `Hash Functions `__. .. code:: c unsigned long hash(unsigned char *str) { unsigned long hash = 5381; int c; while (c = *str++) hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ return hash; } De nouveau calculer la distribution du hash obtenu. Q6 - répartition ---------------- Imagine une façon de répartir des élèves en 4 groupes. Q7 - dictionnaire ----------------- Les dictionnaires en python s’appuient sur une table de hashage et non sur un arbre de recherche dichotomique (voir aussi son code : `taille de hash `__). Quelle expérience pourrait-on mener pour s’assurer ? Le module `timeit `__ pourrait vous mettre sur la voie. Quelques éléments de réponses ----------------------------- Première lettre ~~~~~~~~~~~~~~~ .. code:: ipython3 d = {} for m in personnages.split("\n"): if len(m) == 0: continue if m[0] in d: d[m[0]] += 1 else: d[m[0]] = 1 d .. parsed-literal:: {'J': 4, 'C': 4, 'F': 5, 'M': 8, 'G': 4, 'A': 5, 'B': 6, 'L': 4, 'E': 1, 'P': 2, 'D': 1, 'Z': 1, 'T': 1, 'É': 1} .. code:: ipython3 import matplotlib.pyplot as plt import pandas def draw(*ds_legends): fig, ax = plt.subplots(len(ds_legends) // 2, 1, figsize=(8, len(ds_legends))) i = 0 while i < len(ds_legends): d = ds_legends[i].copy() for a in "abcdefghijklmnopqrstuvwxyz".upper(): if a not in d: d[a] = 0 legend = ds_legends[i+1] df = pandas.DataFrame(d.items(), columns=["L", legend]).sort_values("L").set_index("L") df.plot.bar(ax=ax[i // 2] if len(ds_legends) > 2 else ax) i += 2 return ax draw(d, "lettre 1"); .. image:: 2022_hash_20_0.png Somme ~~~~~ .. code:: ipython3 def somme(mot): s = 0 for c in mot.lower(): s += ord(c) - ord("a") return chr(s % 26 + ord("A")) def repartition(fct): d = {} for m in personnages.split("\n"): if len(m) == 0: continue key = fct(m) if key in d: d[key] += 1 else: d[key] = 1 return d d2 = repartition(somme) draw(d, "lettre 1", d2, "somme"); .. image:: 2022_hash_22_0.png Pseudo ~~~~~~ .. code:: ipython3 def pseudo(mot): s = 0 for c in mot.lower(): n = ord(c) - ord("a") s = (22695477 * (s + n) + 1) % 2 ** 32 return chr(s % 26 + ord("A")) d3 = repartition(pseudo) draw(d, "lettre 1", d2, "somme", d3, "pseudo"); .. image:: 2022_hash_24_0.png Hash ~~~~ .. code:: ipython3 import hashlib def hash(mot): m = hashlib.sha256() m.update(mot.encode("utf-8")) h = m.digest() s = h[0] return chr(s % 26 + ord("A")) d4 = repartition(hash) draw(d, "lettre 1", d2, "somme", d3, "pseudo", d4, "hash"); .. image:: 2022_hash_26_0.png Light hash ~~~~~~~~~~ .. code:: ipython3 def light_hash(mot): mot = mot.encode("utf-8") x = 5381 for c in mot: x = ((x << 5) + x) + c return chr(x % 26 + ord("A")) d5 = repartition(light_hash) draw(d, "lettre 1", d2, "somme", d3, "pseudo", d4, "hash", d5, "light hash"); .. image:: 2022_hash_28_0.png Q7 ~~ Il faut mesurer l’accès à des éléments d’un dictionnaire de différentes tailles.