.. _hashdistributionrst: ============================== 2A.algo - Hash et distribution ============================== .. only:: html **Links:** :download:`notebook `, :downloadlink:`html `, :download:`python `, :downloadlink:`slides `, :githublink:`GitHub|_doc/notebooks/expose/hash_distribution.ipynb|*` Une `fonction de hash `__ a pour propriété statistiques de transformer une distribution quelconque en distribution uniforme. C’est pour cela que beaucoup d’algorithmes utilisent ce type de fonction avant tout traitement pour répartir les données de manières uniformes plutôt que d’utiliser une variable une colonne telle quelle. .. code:: ipython3 %matplotlib inline import matplotlib.pyplot as plt from jyquickhelper import add_notebook_menu add_notebook_menu() .. contents:: :local: Récupérer un fichier wikipédia ------------------------------ .. code:: ipython3 from mlstatpy.data.wikipedia import download_pageviews import os from datetime import datetime download_pageviews(datetime(2018,2,1), folder=".") .. parsed-literal:: '.\\pageviews-20180201-000000' On ne garde que les pages françaises. .. code:: ipython3 with open("pageviews-20180201-000000", "r", encoding="utf-8") as f: fr = filter(lambda line: line.startswith("fr "), f) with open("pageviews-20180201-000000.fr.txt", "w", encoding="utf-8") as g: for line in fr: g.write(line) .. code:: ipython3 import pandas df = pandas.read_csv("pageviews-20180201-000000.fr.txt", encoding="utf-8", sep=" ", header=None) df.columns="country page impressions _".split() df = df[["page", "impressions"]] df = df.sort_values("impressions", ascending=False) print(df.shape) df.head() .. parsed-literal:: (136440, 2) .. raw:: html
page impressions
131064 Wikipédia:Accueil_principal 10868
115817 Sp?cial:Search 8031
116771 Spécial:Recherche 2815
95020 Patrick_Dils 841
44847 France 668
Les données sont biaisées car les pages non démandées par les utilisateurs sur cett date ne sont pas répertoriées mais cela ne nuit pas à la démonstration faite ci-dessous. Distribution volume, impressions par rapprt au premier caractère ---------------------------------------------------------------- .. code:: ipython3 df["ch1"] = df["page"].apply(lambda r: r[0] if isinstance(r, str) else r) df.head() .. raw:: html
page impressions ch1
131064 Wikipédia:Accueil_principal 10868 W
115817 Sp?cial:Search 8031 S
116771 Spécial:Recherche 2815 S
95020 Patrick_Dils 841 P
44847 France 668 F
.. code:: ipython3 co = df.copy() co["volume"] = 1 gr = co.groupby("ch1", as_index=False).sum().sort_values("ch1") gr.head() .. raw:: html
ch1 impressions volume
0 $ 2 1
1 & 1 1
2 ' 8 4
3 ( 60 54
4 - 249 11
.. code:: ipython3 gr[(gr["ch1"] >= "A") & (gr["ch1"] <= "Z")].plot(x="ch1", y=["impressions", "volume"], kind="bar", figsize=(14,4)) .. parsed-literal:: c:\Python364_x64\lib\site-packages\pandas\plotting\_core.py:1716: UserWarning: Pandas doesn't allow columns to be created via a new attribute name - see https://pandas.pydata.org/pandas-docs/stable/indexing.html#attribute-access series.name = label .. parsed-literal:: .. image:: hash_distribution_11_2.png Il est possible de distribuer les impressions et les volumns sur plusieurs machines mais ce serait beaucoup plus simple si les volumes (volume de données) et les impressions (usage de ces données) suivent des distributions identiques. Distribution après hashage -------------------------- .. code:: ipython3 import hashlib def hash(text): md5 = hashlib.md5() md5.update(text.encode('utf-8')) return md5.hexdigest() hash("France") .. parsed-literal:: '0309a6c666a7a803fdb9db95de71cf01' .. code:: ipython3 ha = co.copy() ha["hash"] = ha["page"].apply(lambda r: hash(r) if isinstance(r, str) else r) ha.head() .. raw:: html
page impressions ch1 volume hash
131064 Wikipédia:Accueil_principal 10868 W 1 6cc68aa5234cb8c4e129d5b431eea95a
115817 Sp?cial:Search 8031 S 1 e4c619292a0e11c8afba20eb4531cbf8
116771 Spécial:Recherche 2815 S 1 6f86a30966129c5bf50147eb44c4e82c
95020 Patrick_Dils 841 P 1 624f2274ebdbb30187e57d430c58990d
44847 France 668 F 1 0309a6c666a7a803fdb9db95de71cf01
.. code:: ipython3 ha["ch2"] = ha["hash"].apply(lambda r: r[0] if isinstance(r, str) else r) ha.head() .. raw:: html
page impressions ch1 volume hash ch2
131064 Wikipédia:Accueil_principal 10868 W 1 6cc68aa5234cb8c4e129d5b431eea95a 6
115817 Sp?cial:Search 8031 S 1 e4c619292a0e11c8afba20eb4531cbf8 e
116771 Spécial:Recherche 2815 S 1 6f86a30966129c5bf50147eb44c4e82c 6
95020 Patrick_Dils 841 P 1 624f2274ebdbb30187e57d430c58990d 6
44847 France 668 F 1 0309a6c666a7a803fdb9db95de71cf01 0
.. code:: ipython3 gr = ha.groupby("ch2", as_index=False).sum().sort_values("ch2") gr.head() .. raw:: html
ch2 impressions volume
0 0 18493 8531
1 1 16615 8513
2 2 17276 8514
3 3 17219 8547
4 4 16847 8468
.. code:: ipython3 gr.plot(x="ch2", y=["impressions", "volume"], kind="bar", figsize=(14,4)) .. parsed-literal:: c:\Python364_x64\lib\site-packages\pandas\plotting\_core.py:1716: UserWarning: Pandas doesn't allow columns to be created via a new attribute name - see https://pandas.pydata.org/pandas-docs/stable/indexing.html#attribute-access series.name = label .. parsed-literal:: .. image:: hash_distribution_18_2.png Après avoir appliqué une fonction de hashage, les deux distributions volumes et impressions sont presque uniforme par rapport au premier caractère du hash. Il reste un pic : il provient de la page wikipédia la plus demandée. Ces pages très demandées sont très souvent en très petit nombre et on implémentera une mécanisme de cache s’il s’agit d’un site web. En revanche, lors d’un calcul distribué sur Map / Reduce, un des problèmes consistera à traiter ces clés de distributions qui regroupent une part trop importante des données. On recommence le même raisonnement en utilisant les deux premiers caractères du hash comme clé de distribution. .. code:: ipython3 def substr(s, size=2): if isinstance(s, str): if len(s) < size: return s else: return s[:size] else: return s ha["ch12"] = ha["hash"].apply(lambda r: substr(r)) gr = ha.groupby("ch12", as_index=False).sum().sort_values("ch12") gr.plot(x="ch12", y=["impressions", "volume"], figsize=(14,4)) .. parsed-literal:: c:\Python364_x64\lib\site-packages\pandas\plotting\_core.py:1716: UserWarning: Pandas doesn't allow columns to be created via a new attribute name - see https://pandas.pydata.org/pandas-docs/stable/indexing.html#attribute-access series.name = label .. parsed-literal:: .. image:: hash_distribution_20_2.png Dans ce cas précis, si le traitement appliqué aux données est d’un coût proportionnelle à la taille des données associées à chaque clé, cela signifie qu’une opération de type **reduce** aura un temps de traitement proportionnel au volume de données associée à la plus grande clé et non au nombre de machines puisque toutes les données d’une même clé sont envoyées sur la même machine.