API tools faq
paste
Guest User

Untitled

a guest
Nov 9th, 2017
78
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 97.88 KB | None | 0 0
raw download clone embed print report
  1. {
  2. "cells": [
  3. {
  4. "metadata": {},
  5. "cell_type": "markdown",
  6. "source": "<p style=\"text-align : center\"><font color=#c72b26 size=8>Wikipedia Pagecount</font></p>"
  7. },
  8. {
  9. "metadata": {
  10. "collapsed": true,
  11. "trusted": false
  12. },
  13. "cell_type": "markdown",
  14. "source": "<p style=\"text-align : center\"><font size=6>Sommaire</font></p>\n\n<p style=\"margin-left : 280px\">\n<font size=5>1. [Méthode avec base de données](#1)</font><br/>\n</p>\n<p style=\"margin-left : 300px\">\n 1.1 [Création de la base de données définition des commandes](#1.1)<br/>\n 1.2 [Estimation pour un fichier avec lecture en shell (commande sed)](#1.2)<br/>\n 1.3 [Estimation sur un jour avec lecture shell](#1.3)<br/>\n 1.4 [Estimation pour un fichier avec lecture Python](#1.4)<br/>\n 1.5 [Estimation sur un jour avec lecture Python](#1.5)<br/>\n 1.6 [Script pour exécuter du MySQL](#1.6)<br/>\n</p>\n<p style=\"margin-left : 280px\">\n<font size=5>2. [Méthode avec Hash](#2)</font><br/>\n</p>\n<p style=\"margin-left : 300px\">\n2.1 [Estimation pour un fichier](#2.1)<br/>\n2.2 [Estimation sur un jour](#2.2)<br/>\n</p>\n<p style=\"margin-left : 280px\">\n<font size=5>3. [Méthode Hash : amélioration](#3)</font><br/>\n</p>\n<p style=\"margin-left : 300px\">\n3.1 [Augmentation de la taille du bytearray](#3.1)<br/>\n3.2 [Fonctions de hashing différentes](#3.2)<br/>\n3.3 [Partition des noms de page](#3.3)<br/>\n3.4 [Gestion explicite de collision](#3.4)<br/>\n</p>"
  15. },
  16. {
  17. "metadata": {},
  18. "cell_type": "markdown",
  19. "source": "<a id='1'></a>\n# <font color=#c72b26>Méthode avec base de données</font>"
  20. },
  21. {
  22. "metadata": {},
  23. "cell_type": "markdown",
  24. "source": "><p style=\"text-align: justify;\"><font color=#206da1>Après visualisation des données, j'ai retenu les deux premières colonnes pour distinguer les pages, car en effet plusieurs pages peuvent avoir le même nom tout en ayant un contenu rédigé en langues différentes. </font></p>"
  25. },
  26. {
  27. "metadata": {
  28. "scrolled": true,
  29. "trusted": false
  30. },
  31. "cell_type": "code",
  32. "source": "!head pagecounts-20150501-000000",
  33. "execution_count": 21,
  34. "outputs": [
  35. {
  36. "name": "stdout",
  37. "output_type": "stream",
  38. "text": "CA El_somni_d'una_nit_d'estiu_(Britten) 1 54106\r\nCA Ignasi_Plana_i_Fontana 1 36270\r\nDe 1995 1 293711\r\nDe Adjungierter_Operator 1 52677\r\nDe Adolph-Kolping-Berufskolleg 1 36679\r\nDe Albrecht_Beutelspacher 1 49372\r\nDe Alfred_von_Gutschmid 1 46340\r\nDe Amherst_Island 1 31630\r\nDe Angerbach_(Rhein) 1 36678\r\nDe Anzeige_(Medien) 1 53864\r\n"
  39. }
  40. ]
  41. },
  42. {
  43. "metadata": {},
  44. "cell_type": "markdown",
  45. "source": "><p style=\"text-align: justify;\"><font color=#206da1>Pour compter le nombre total de pages distinctes visitées en une journée, la première idée qui m'était venue à l'esprit est une approche avec un dictionnaire.<br/>\nJ'ai tout d'abord essayé d'utiliser le type dictionary intégré dans python, cependant la taille requise pour stocker le nombre total de nom de page était trop importante et conduisait à une erreur de mémoire.</font></p>"
  46. },
  47. {
  48. "metadata": {},
  49. "cell_type": "markdown",
  50. "source": "<a id='1.1'></a>\n## Création de la base de données définition des commandes"
  51. },
  52. {
  53. "metadata": {},
  54. "cell_type": "markdown",
  55. "source": "><p style=\"text-align: justify;\"><font color=#206da1>Pour parer à ce problème, j'ai décidé d'utiliser un serveur de base de données externe, j'ai donc choisi d'utiliser MySQL qui possède déjà une interface de connexion pour Python.<br/>\nAu début, j'avais seulement créé une seule table avec le nom de la page comme clé primaire et un second attribut stockant le nombre de visites accumulé. En implémentant cette approche, des problèmes de taille des noms et d'encodage sont survenus. En effet, le nom de la page peut être très long pour certaine langue, et l'utilisation des émoticônes n'est pas assuré par l'encodage UTF-8.<br/>\nJ'ai donc décidé de créer deux tables, une pour toutes les pages qui ne posent pas de problème et une autre qui est appelée en cas d'erreur.</font></p>"
  56. },
  57. {
  58. "metadata": {
  59. "trusted": false
  60. },
  61. "cell_type": "code",
  62. "source": "import mysql.connector\nfrom mysql.connector import errorcode\nimport numpy as np\nimport timeit\nimport time\n\ncnx = mysql.connector.connect(user='root', password='pagecount', charset='utf8mb4')\ncursor=cnx.cursor()\n\n\n\nDB_NAME = 'pagecount'\n\ndropPages = (\"DROP TABLE pages\")\ndropLongPages = (\"DROP TABLE longpages\")\ncreatePages = (\"CREATE TABLE `pages` (\"\n \" `pageName` varchar(1000) BINARY NOT NULL,\"\n \" `times` int(11) NOT NULL,\"\n \" PRIMARY KEY (`pageName`)\"\n \") ENGINE=InnoDB\")\n\ncreateLongPages = (\"CREATE TABLE `longpages` (\"\n \" `id` int(11) NOT NULL AUTO_INCREMENT,\"\n \" `pageName` text CHARACTER SET utf8mb4 COLLATE utf8mb4_bin NOT NULL,\"\n \" `times` int(11) NOT NULL,\"\n \" PRIMARY KEY (`id`)\"\n \") ENGINE=InnoDB CHARACTER SET utf8mb4 COLLATE utf8mb4_bin\")\n\n#alterPages = (\"ALTER TABLE pages\"\n# \"MODIFY pageName varchar(500) NOT NULL\")\n\naddPage = (\"INSERT INTO pages \"\n \"(pageName, times) \"\n \"VALUES (%(pageName)s, %(times)s\")\n\naddLongPage = (\"INSERT INTO longpages (pageName, times) \"\n \"VALUES (%(pageName)s, %(times)s)\")\n\nupdatePage = (\"INSERT INTO pages (pageName, times)\"\n \"VALUES (%(pageName)s, %(times)s)\"\n \"ON DUPLICATE KEY UPDATE times = times+%(times)s\")\n\nupdateLongPage = (\"UPDATE longpages\"\n \"SET times = times+%(times)s \"\n \"WHERE pageName = %(pageName)s)\")\n\ncountPages = (\"SELECT count(*) FROM pages\")\n\ndef create_database(cursor):\n try:\n cursor.execute(\n \"CREATE DATABASE {} DEFAULT CHARACTER SET 'utf8'\".format(DB_NAME))\n except mysql.connector.Error as err:\n print(\"Failed creating database: {}\".format(err))\n exit(1)\n \ntry:\n cnx.database = DB_NAME \nexcept mysql.connector.Error as err:\n if err.errno == errorcode.ER_BAD_DB_ERROR:\n create_database(cursor)\n cnx.database = DB_NAME\n else:\n print(err)\n exit(1)\n\n\ntry: \n cursor.execute(dropPages)\n cursor.execute(dropLongPages)\nexcept mysql.connector.Error as err:\n print(\"table doesn't exist.\")\n\ntry:\n cursor.execute(createPages)\n cursor.execute(createLongPages)\nexcept mysql.connector.Error as err:\n if err.errno == errorcode.ER_TABLE_EXISTS_ERROR:\n print(\"table already exists.\")\n else:\n print(err.msg)\nelse:\n print(\"OK\")\n\n\n\n#cnx.close()",
  63. "execution_count": 142,
  64. "outputs": [
  65. {
  66. "name": "stdout",
  67. "output_type": "stream",
  68. "text": "OK\n"
  69. }
  70. ]
  71. },
  72. {
  73. "metadata": {},
  74. "cell_type": "markdown",
  75. "source": "<a id='1.2'></a>\n\n## Estimation pour un fichier avec lecture en shell (commande sed)"
  76. },
  77. {
  78. "metadata": {},
  79. "cell_type": "markdown",
  80. "source": "><p style=\"text-align: justify;\"><font color=#206da1>Pour lire les données des fichier j'ai utilisé la commande sed de la console bash avec une lecture en paquet de 10 000 lignes par bouble. Les données sont alors ajoutées dans le SGBD avec gestion d'erreur.</font></p>"
  81. },
  82. {
  83. "metadata": {
  84. "collapsed": true,
  85. "trusted": false
  86. },
  87. "cell_type": "code",
  88. "source": "def estimate(n, fileNumber):\n prefix = \"pagecounts-20150501-\"\n fname = prefix + \"{:02}0000\".format(fileNumber)\n !gunzip \"$fname\".gz\n nLine=9999\n firstLine=50000\n lastLine=firstLine+nLine\n bashArg=str(firstLine)+','+str(lastLine)+'p'\n data=!sed -n \"$bashArg\" \"$fname\"\n data=[i.rsplit(None, 2) for i in data]\n date0=time.perf_counter()\n k=0\n while data and firstLine < n:\n for datum in data:\n k+=1\n datum={\"pageName\" : datum[0], \"times\" : int(datum[1])}\n try:\n cursor.execute(updatePage, datum)\n cnx.commit()\n except mysql.connector.Error as err:\n print(k)\n print(err.msg)\n cursor.execute(\"SELECT * FROM longpages WHERE pageName = %(pageName)s\", datum)\n output=cursor.fetchall()\n if output:\n cursor.execute(updateLongPage, datum)\n else:\n cursor.execute(addLongPage, datum)\n cnx.commit()\n firstLine=lastLine+1\n lastLine=firstLine+nLine\n bashArg=str(firstLine)+','+str(lastLine)+'p'\n data=!sed -n \"$bashArg\" \"$fname\"\n data=[i.rsplit(None, 2) for i in data]\n date1=time.perf_counter()\n print(\"lignes comptées =\", k, date1-date0)\n date0=date1\n cursor.execute(countPages)\n numberPages = cursor.fetchall()\n print(numberPages)\n !gzip \"$fname\"\n return numberPages",
  89. "execution_count": null,
  90. "outputs": []
  91. },
  92. {
  93. "metadata": {},
  94. "cell_type": "markdown",
  95. "source": "><font color=#206da1><p style=\"text-align: justify;\">En exécutant la fonction d'estimation, on remarque le temps moyen pour traiter 10 000 lignes est d'environ 17 secondes ce qui est excessif pour un nombre total de ligne de 186 328 237 (environ 89h).<br/>\nPour avoir une idée des noms de page non conformes, j'ai ajouté une impression du numéro de ligne.</font></p>"
  96. },
  97. {
  98. "metadata": {
  99. "trusted": false
  100. },
  101. "cell_type": "code",
  102. "source": "timeit.timeit(\"estimate(10000000, 0)\", number=1, globals=globals())",
  103. "execution_count": 10,
  104. "outputs": [
  105. {
  106. "name": "stdout",
  107. "output_type": "stream",
  108. "text": "8208\nIncorrect string value: '\\xF0\\x9F\\x98\\x83' for column 'pageName' at row 1\n9207\nData too long for column 'pageName' at row 1\nlignes comptées = 10000 16.20146743999794\nlignes comptées = 20000 16.352786380040925\n24486\nData too long for column 'pageName' at row 1\n24487\nData too long for column 'pageName' at row 1\n26001\nData too long for column 'pageName' at row 1\n27405\nData too long for column 'pageName' at row 1\n28257\nData too long for column 'pageName' at row 1\nlignes comptées = 30000 16.32930146099534\nlignes comptées = 40000 15.955658496997785\nlignes comptées = 50000 18.174142932984978\n56398\nData too long for column 'pageName' at row 1\nlignes comptées = 60000 16.565723429026548\n61729\nData too long for column 'pageName' at row 1\nlignes comptées = 70000 16.46626388200093\n75520\nData too long for column 'pageName' at row 1\nlignes comptées = 80000 15.819014034001157\n80288\nData too long for column 'pageName' at row 1\n82306\nData too long for column 'pageName' at row 1\n83884\nData too long for column 'pageName' at row 1\n89454\nData too long for column 'pageName' at row 1\nlignes comptées = 90000 15.576532228966244\n90217\nData too long for column 'pageName' at row 1\n93984\nData too long for column 'pageName' at row 1\n96878\nData too long for column 'pageName' at row 1\n97256\nData too long for column 'pageName' at row 1\nlignes comptées = 100000 14.780718752997927\n101134\nData too long for column 'pageName' at row 1\nlignes comptées = 110000 15.751709830015898\nlignes comptées = 120000 16.040277426014654\nlignes comptées = 130000 17.242030738969333\nlignes comptées = 140000 16.25895033602137\nlignes comptées = 150000 16.158957159961574\nlignes comptées = 160000 16.655907083011698\nlignes comptées = 170000 16.292610122996848\nlignes comptées = 180000 16.41888574999757\nlignes comptées = 190000 16.50041846302338\nlignes comptées = 200000 16.65521987597458\nlignes comptées = 210000 16.701541059999727\n218102\nData too long for column 'pageName' at row 1\nlignes comptées = 220000 18.119987673009746\nlignes comptées = 230000 16.762455941992812\nlignes comptées = 240000 17.220298402011395\nlignes comptées = 250000 15.14550252101617\nlignes comptées = 260000 15.18619260599371\nlignes comptées = 270000 16.918055917019956\nlignes comptées = 280000 16.180350743990857\nlignes comptées = 290000 16.33139913197374\nlignes comptées = 300000 17.37974430702161\nlignes comptées = 310000 17.057668400986586\nlignes comptées = 320000 18.055828350014053\nlignes comptées = 330000 16.766374366998207\nlignes comptées = 340000 16.954802737978753\nlignes comptées = 350000 17.248349548026454\nlignes comptées = 360000 16.482231252011843\nlignes comptées = 370000 17.698806739004795\nlignes comptées = 380000 18.232503291976172\nlignes comptées = 390000 15.726030880992766\nlignes comptées = 400000 17.426310527021997\nlignes comptées = 410000 19.84000913798809\nlignes comptées = 420000 16.999280360003468\nlignes comptées = 430000 16.2573611009866\nlignes comptées = 440000 18.138745823001955\nlignes comptées = 450000 18.238348719023634\nlignes comptées = 460000 16.63632820098428\nlignes comptées = 470000 16.896903641987592\n471666\nData too long for column 'pageName' at row 1\n473439\nData too long for column 'pageName' at row 1\nlignes comptées = 480000 17.99651258002268\n486333\nData too long for column 'pageName' at row 1\nlignes comptées = 490000 18.58905456395587\nlignes comptées = 500000 17.44556323805591\nlignes comptées = 510000 18.011149296944495\n514945\nData too long for column 'pageName' at row 1\n514946\nData too long for column 'pageName' at row 1\n514947\nData too long for column 'pageName' at row 1\nlignes comptées = 520000 17.486175387050025\nlignes comptées = 530000 17.096832467999775\nlignes comptées = 540000 17.142959307995625\nlignes comptées = 550000 18.10696052800631\nlignes comptées = 560000 16.222235375957098\nlignes comptées = 570000 17.870656631013844\nlignes comptées = 580000 17.57953957800055\nlignes comptées = 590000 16.261519849998876\nlignes comptées = 600000 18.86161618900951\n"
  109. },
  110. {
  111. "ename": "KeyboardInterrupt",
  112. "evalue": "",
  113. "output_type": "error",
  114. "traceback": [
  115. "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
  116. "\u001b[0;31mKeyboardInterrupt\u001b[0m Traceback (most recent call last)",
  117. "\u001b[0;32m<ipython-input-10-66564e7db51b>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m 41\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0mnumberPages\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 42\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 43\u001b[0;31m \u001b[0mestimate\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m10000000\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 44\u001b[0m \u001b[0;31m#timeit.timeit(\"estimate(10000)\", number=1, globals=globals())\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 45\u001b[0m \u001b[0mcnx\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mclose\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
  118. "\u001b[0;32m<ipython-input-10-66564e7db51b>\u001b[0m in \u001b[0;36mestimate\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 17\u001b[0m \u001b[0;32mtry\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 18\u001b[0m \u001b[0mcursor\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mexecute\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mupdatePage\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdatum\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 19\u001b[0;31m \u001b[0mcnx\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcommit\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 20\u001b[0m \u001b[0;32mexcept\u001b[0m \u001b[0mmysql\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconnector\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mError\u001b[0m \u001b[0;32mas\u001b[0m \u001b[0merr\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 21\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mk\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
  119. "\u001b[0;32m~/anaconda3/lib/python3.6/site-packages/mysql/connector/connection.py\u001b[0m in \u001b[0;36mcommit\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m 1476\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mcommit\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 1477\u001b[0m \u001b[0;34m\"\"\"Commit current transaction\"\"\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 1478\u001b[0;31m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_execute_query\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"COMMIT\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 1479\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 1480\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mrollback\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
  120. "\u001b[0;32m~/anaconda3/lib/python3.6/site-packages/mysql/connector/connection.py\u001b[0m in \u001b[0;36m_execute_query\u001b[0;34m(self, query)\u001b[0m\n\u001b[1;32m 1497\u001b[0m \u001b[0;32mraise\u001b[0m \u001b[0merrors\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mInternalError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Unread result found.\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 1498\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 1499\u001b[0;31m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcmd_query\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mquery\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 1500\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 1501\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0m_info_query\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mquery\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
  121. "\u001b[0;32m~/anaconda3/lib/python3.6/site-packages/mysql/connector/connection.py\u001b[0m in \u001b[0;36mcmd_query\u001b[0;34m(self, query)\u001b[0m\n\u001b[1;32m 720\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0misinstance\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mquery\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mbytes\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 721\u001b[0m \u001b[0mquery\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mquery\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mencode\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'utf-8'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 722\u001b[0;31m \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_handle_result\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_send_cmd\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mServerCmd\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mQUERY\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mquery\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 723\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 724\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_have_next_result\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
  122. "\u001b[0;32m~/anaconda3/lib/python3.6/site-packages/mysql/connector/connection.py\u001b[0m in \u001b[0;36m_send_cmd\u001b[0;34m(self, command, argument, packet_number, packet, expect_response)\u001b[0m\n\u001b[1;32m 508\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0mexpect_response\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 509\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 510\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_socket\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mrecv\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 511\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 512\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0m_send_data\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdata_file\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msend_empty_packet\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mFalse\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
  123. "\u001b[0;32m~/anaconda3/lib/python3.6/site-packages/mysql/connector/network.py\u001b[0m in \u001b[0;36mrecv_plain\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m 224\u001b[0m \u001b[0mpacket_len\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 225\u001b[0m \u001b[0;32mwhile\u001b[0m \u001b[0mpacket_len\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0;36m4\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 226\u001b[0;31m \u001b[0mchunk\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msock\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mrecv\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m4\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0mpacket_len\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 227\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0mchunk\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 228\u001b[0m \u001b[0;32mraise\u001b[0m \u001b[0merrors\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mInterfaceError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0merrno\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;36m2013\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
  124. "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
  125. ]
  126. }
  127. ]
  128. },
  129. {
  130. "metadata": {},
  131. "cell_type": "markdown",
  132. "source": "<a id='1.3'></a>\n\n## Estimation sur un jour avec lecture shell"
  133. },
  134. {
  135. "metadata": {
  136. "collapsed": true,
  137. "trusted": false
  138. },
  139. "cell_type": "code",
  140. "source": "def estimateAllBasic():\n for i in range(24):\n estimate(200000000, i)#maximum number of lines\n cursor.execute(countPages)\n numberPages = cursor.fetchall()\n print(numberPages)\n return numberPages",
  141. "execution_count": null,
  142. "outputs": []
  143. },
  144. {
  145. "metadata": {
  146. "collapsed": true,
  147. "trusted": false
  148. },
  149. "cell_type": "code",
  150. "source": "timeit.timeit(\"estimateAllBasic()\", number=1, globals=globals())",
  151. "execution_count": null,
  152. "outputs": []
  153. },
  154. {
  155. "metadata": {
  156. "collapsed": true,
  157. "trusted": false
  158. },
  159. "cell_type": "code",
  160. "source": "cnx.close()",
  161. "execution_count": 4,
  162. "outputs": []
  163. },
  164. {
  165. "metadata": {},
  166. "cell_type": "markdown",
  167. "source": "<a id='1.4'></a>\n\n## Estimation pour un fichier avec lecture Python "
  168. },
  169. {
  170. "metadata": {},
  171. "cell_type": "markdown",
  172. "source": "><p style=\"text-align: justify;\"><font color=#206da1>Pour des soucis de performance et d'utilisation de mémoire, j'ai essayé d'utiliser la lecture par ligne native de Python.</font></p>"
  173. },
  174. {
  175. "metadata": {
  176. "collapsed": true,
  177. "trusted": false
  178. },
  179. "cell_type": "code",
  180. "source": "def estimatePerLine(fileNumber):\n prefix = \"pagecounts-20150501-\"\n fname = prefix + \"{:02}0000\".format(fileNumber)\n !gunzip \"$fname\".gz\n pageTableHeader=[\"pageName\", \"times\"]\n k=0\n date0=time.perf_counter()\n with open(fname) as file:\n for line in file:\n k+=1\n datum=line.rsplit(None, 2)\n datum={\"pageName\" : datum[0], \"times\" : int(datum[1])}\n try:\n cursor.execute(updatePage, datum)\n cnx.commit()\n except mysql.connector.Error as err:\n print(k)\n print(err.msg)\n cursor.execute(\"SELECT * FROM longpages WHERE pageName = %(pageName)s\", datum)\n output=cursor.fetchall()\n if output:\n cursor.execute(updateLongPage, datum)\n else:\n cursor.execute(addLongPage, datum)\n cnx.commit()\n if k%1000==0:\n date1=time.perf_counter()\n print(\"lignes comptées =\", k, date1-date0)\n date0=date1\n !gzip \"$fname\"\n return",
  181. "execution_count": 140,
  182. "outputs": []
  183. },
  184. {
  185. "metadata": {},
  186. "cell_type": "markdown",
  187. "source": "><p style=\"text-align: justify;\"><font color=#206da1>La lecture par Python conduit à une petite diminution au niveau du temps d'exécution de l'ordre d'une seconde pour 10 000 lignes. </font></p>"
  188. },
  189. {
  190. "metadata": {
  191. "trusted": false
  192. },
  193. "cell_type": "code",
  194. "source": "timeit.timeit(\"estimatePerLine(0)\", number=1, globals=globals())",
  195. "execution_count": 3,
  196. "outputs": [
  197. {
  198. "name": "stdout",
  199. "output_type": "stream",
  200. "text": "lignes comptées = 1000 1.5417487249942496\nlignes comptées = 2000 1.457579433976207\nlignes comptées = 3000 1.3231056380318478\nlignes comptées = 4000 1.395661253016442\nlignes comptées = 5000 1.4338762419647537\nlignes comptées = 6000 1.3210796160274185\nlignes comptées = 7000 1.4583511209930293\nlignes comptées = 8000 1.4341432430082932\nlignes comptées = 9000 1.4416038310155272\nlignes comptées = 10000 1.3564258969854563\nlignes comptées = 11000 1.4630796610144898\nlignes comptées = 12000 1.5044840459595434\nlignes comptées = 13000 1.4473854110110551\nlignes comptées = 14000 1.4002826630021445\nlignes comptées = 15000 1.6062588749919087\nlignes comptées = 16000 1.5039239540346898\nlignes comptées = 17000 1.3823459819541313\nlignes comptées = 18000 1.5775933040422387\nlignes comptées = 19000 1.569490648980718\nlignes comptées = 20000 1.4570419159717858\nlignes comptées = 21000 1.519626984023489\nlignes comptées = 22000 1.5830156850279309\nlignes comptées = 23000 1.5236302569974214\nlignes comptées = 24000 1.6009500989457592\nlignes comptées = 25000 1.6262820770498365\nlignes comptées = 26000 1.6295095999957994\nlignes comptées = 27000 1.5280413560103625\nlignes comptées = 28000 1.6178843759698793\nlignes comptées = 29000 1.5833510420052335\nlignes comptées = 30000 1.4599895689752884\nlignes comptées = 31000 1.575178279017564\nlignes comptées = 32000 1.6367270160117187\nlignes comptées = 33000 1.6461134079727344\nlignes comptées = 34000 1.4766214840346947\nlignes comptées = 35000 1.6759551810100675\nlignes comptées = 36000 1.6622583429561928\nlignes comptées = 37000 1.6160508019966073\nlignes comptées = 38000 1.476962568005547\nlignes comptées = 39000 1.553172165993601\nlignes comptées = 40000 1.6197935790405609\nlignes comptées = 41000 1.450463638000656\nlignes comptées = 42000 1.5689886930049397\nlignes comptées = 43000 1.5273501829942688\nlignes comptées = 44000 1.5496926949708723\nlignes comptées = 45000 1.5556120700202882\nlignes comptées = 46000 1.6634375500143506\nlignes comptées = 47000 1.5889187199645676\nlignes comptées = 48000 1.3587340870290063\nlignes comptées = 49000 1.5686314339982346\nlignes comptées = 50000 1.6156529579893686\nlignes comptées = 51000 1.5318036790122278\nlignes comptées = 52000 1.58810650795931\nlignes comptées = 53000 1.5888811200275086\nlignes comptées = 54000 1.528096732974518\nlignes comptées = 55000 1.5102694390225224\nlignes comptées = 56000 1.5168455400271341\n56912\nData too long for column 'pageName' at row 1\nlignes comptées = 57000 1.5962302929838188\nlignes comptées = 58000 1.398933238000609\nlignes comptées = 59000 1.410634118015878\nlignes comptées = 60000 1.5825467589893378\n60292\nData too long for column 'pageName' at row 1\n60810\nData too long for column 'pageName' at row 1\n60836\nData too long for column 'pageName' at row 1\nlignes comptées = 61000 1.5612627289956436\nlignes comptées = 62000 1.4640332839917392\nlignes comptées = 63000 1.6910006719990633\nlignes comptées = 64000 1.582559188012965\nlignes comptées = 65000 1.5619602049700916\nlignes comptées = 66000 1.48219163302565\nlignes comptées = 67000 1.5686878410051577\nlignes comptées = 68000 1.6134698059759103\nlignes comptées = 69000 1.5308097890228964\nlignes comptées = 70000 1.5953654919867404\nlignes comptées = 71000 1.5802478800178505\nlignes comptées = 72000 1.4563652239739895\nlignes comptées = 73000 1.5367572560207918\nlignes comptées = 74000 1.6627611799631268\nlignes comptées = 75000 1.4882308450178243\nlignes comptées = 76000 1.6690169420326129\nlignes comptées = 77000 1.6673467449727468\nlignes comptées = 78000 1.592057535017375\nlignes comptées = 79000 1.558873017958831\nlignes comptées = 80000 1.642294016026426\nlignes comptées = 81000 1.6440768290194683\nlignes comptées = 82000 1.5230169229907915\nlignes comptées = 83000 1.6022604589816183\nlignes comptées = 84000 1.645562082005199\nlignes comptées = 85000 1.497186338994652\nlignes comptées = 86000 1.6396643710322678\nlignes comptées = 87000 1.731139892945066\nlignes comptées = 88000 1.4865570190013386\nlignes comptées = 89000 1.5933590740314685\nlignes comptées = 90000 1.5676555919926614\nlignes comptées = 91000 1.4391547390259802\nlignes comptées = 92000 1.4882743089692667\nlignes comptées = 93000 1.579026032006368\n"
  201. },
  202. {
  203. "ename": "KeyboardInterrupt",
  204. "evalue": "",
  205. "output_type": "error",
  206. "traceback": [
  207. "\u001b[0;31m---------------------------------------------------------------------------\u001b[0m",
  208. "\u001b[0;31mKeyboardInterrupt\u001b[0m Traceback (most recent call last)",
  209. "\u001b[0;32m<ipython-input-3-cf5f5b805da8>\u001b[0m in \u001b[0;36m<module>\u001b[0;34m()\u001b[0m\n\u001b[1;32m 31\u001b[0m \u001b[0;32mreturn\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 32\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 33\u001b[0;31m \u001b[0mestimatePerLine\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m100000\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 34\u001b[0m \u001b[0;31m#timeit.timeit(\"estimate(10000)\", number=1, globals=globals())\u001b[0m\u001b[0;34m\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 35\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n",
  210. "\u001b[0;32m<ipython-input-3-cf5f5b805da8>\u001b[0m in \u001b[0;36mestimatePerLine\u001b[0;34m(n)\u001b[0m\n\u001b[1;32m 12\u001b[0m \u001b[0;32mtry\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 13\u001b[0m \u001b[0mcursor\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mexecute\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mupdatePage\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdatum\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m---> 14\u001b[0;31m \u001b[0mcnx\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcommit\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 15\u001b[0m \u001b[0;32mexcept\u001b[0m \u001b[0mmysql\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mconnector\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mError\u001b[0m \u001b[0;32mas\u001b[0m \u001b[0merr\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 16\u001b[0m \u001b[0mprint\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mk\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
  211. "\u001b[0;32m~/anaconda3/lib/python3.6/site-packages/mysql/connector/connection.py\u001b[0m in \u001b[0;36mcommit\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m 1476\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mcommit\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 1477\u001b[0m \u001b[0;34m\"\"\"Commit current transaction\"\"\"\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 1478\u001b[0;31m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_execute_query\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"COMMIT\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 1479\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 1480\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0mrollback\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
  212. "\u001b[0;32m~/anaconda3/lib/python3.6/site-packages/mysql/connector/connection.py\u001b[0m in \u001b[0;36m_execute_query\u001b[0;34m(self, query)\u001b[0m\n\u001b[1;32m 1497\u001b[0m \u001b[0;32mraise\u001b[0m \u001b[0merrors\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mInternalError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m\"Unread result found.\"\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 1498\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m-> 1499\u001b[0;31m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mcmd_query\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mquery\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 1500\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 1501\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0m_info_query\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mquery\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
  213. "\u001b[0;32m~/anaconda3/lib/python3.6/site-packages/mysql/connector/connection.py\u001b[0m in \u001b[0;36mcmd_query\u001b[0;34m(self, query)\u001b[0m\n\u001b[1;32m 720\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0misinstance\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mquery\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mbytes\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 721\u001b[0m \u001b[0mquery\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mquery\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mencode\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m'utf-8'\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 722\u001b[0;31m \u001b[0mresult\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_handle_result\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_send_cmd\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mServerCmd\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mQUERY\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mquery\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 723\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 724\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_have_next_result\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
  214. "\u001b[0;32m~/anaconda3/lib/python3.6/site-packages/mysql/connector/connection.py\u001b[0m in \u001b[0;36m_send_cmd\u001b[0;34m(self, command, argument, packet_number, packet, expect_response)\u001b[0m\n\u001b[1;32m 508\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0mexpect_response\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 509\u001b[0m \u001b[0;32mreturn\u001b[0m \u001b[0;32mNone\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 510\u001b[0;31m \u001b[0;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0m_socket\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mrecv\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 511\u001b[0m \u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 512\u001b[0m \u001b[0;32mdef\u001b[0m \u001b[0m_send_data\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0mself\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0mdata_file\u001b[0m\u001b[0;34m,\u001b[0m \u001b[0msend_empty_packet\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;32mFalse\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
  215. "\u001b[0;32m~/anaconda3/lib/python3.6/site-packages/mysql/connector/network.py\u001b[0m in \u001b[0;36mrecv_plain\u001b[0;34m(self)\u001b[0m\n\u001b[1;32m 224\u001b[0m \u001b[0mpacket_len\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0;36m0\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 225\u001b[0m \u001b[0;32mwhile\u001b[0m \u001b[0mpacket_len\u001b[0m \u001b[0;34m<\u001b[0m \u001b[0;36m4\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0;32m--> 226\u001b[0;31m \u001b[0mchunk\u001b[0m \u001b[0;34m=\u001b[0m \u001b[0mself\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0msock\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mrecv\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0;36m4\u001b[0m \u001b[0;34m-\u001b[0m \u001b[0mpacket_len\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[0m\u001b[1;32m 227\u001b[0m \u001b[0;32mif\u001b[0m \u001b[0;32mnot\u001b[0m \u001b[0mchunk\u001b[0m\u001b[0;34m:\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n\u001b[1;32m 228\u001b[0m \u001b[0;32mraise\u001b[0m \u001b[0merrors\u001b[0m\u001b[0;34m.\u001b[0m\u001b[0mInterfaceError\u001b[0m\u001b[0;34m(\u001b[0m\u001b[0merrno\u001b[0m\u001b[0;34m=\u001b[0m\u001b[0;36m2013\u001b[0m\u001b[0;34m)\u001b[0m\u001b[0;34m\u001b[0m\u001b[0m\n",
  216. "\u001b[0;31mKeyboardInterrupt\u001b[0m: "
  217. ]
  218. }
  219. ]
  220. },
  221. {
  222. "metadata": {},
  223. "cell_type": "markdown",
  224. "source": "<a id='1.5'></a>\n\n## Estimation sur un jour avec lecture Python"
  225. },
  226. {
  227. "metadata": {
  228. "collapsed": true,
  229. "trusted": false
  230. },
  231. "cell_type": "code",
  232. "source": "def estimateAllBasicPerLine():\n for i in range(24):\n estimate(200000000)#maximum number of lines\n cursor.execute(countPages)\n numberPages = cursor.fetchall()\n print(numberPages)\n return numberPages",
  233. "execution_count": null,
  234. "outputs": []
  235. },
  236. {
  237. "metadata": {
  238. "collapsed": true,
  239. "trusted": false
  240. },
  241. "cell_type": "code",
  242. "source": "timeit.timeit(\"estimateAllBasicPerLine()\", number=1, globals=globals())",
  243. "execution_count": null,
  244. "outputs": []
  245. },
  246. {
  247. "metadata": {
  248. "collapsed": true
  249. },
  250. "cell_type": "markdown",
  251. "source": "<a id='1.6'></a>\n## Script pour exécuter du MySQL"
  252. },
  253. {
  254. "metadata": {
  255. "trusted": false
  256. },
  257. "cell_type": "code",
  258. "source": "cnx = mysql.connector.connect(user='root', password='pagecount')\ncursor=cnx.cursor()\ntry:\n cnx.database = DB_NAME \nexcept mysql.connector.Error as err:\n if err.errno == errorcode.ER_BAD_DB_ERROR:\n create_database(cursor)\n cnx.database = DB_NAME\n else:\n print(err)\n exit(1)\n\ncursor.execute(\"SELECT count(*) FROM pages\")\nprint(cursor.fetchall())\ncursor.execute(\"SELECT count(*) FROM longpages\")\nprint(cursor.fetchall())\ncursor.execute(\"SELECT count(*) FROM pages WHERE times=2\")\nprint(cursor.fetchall())",
  259. "execution_count": 6,
  260. "outputs": [
  261. {
  262. "name": "stdout",
  263. "output_type": "stream",
  264. "text": "[(179151,)]\n[(11,)]\n[(17282,)]\n"
  265. }
  266. ]
  267. },
  268. {
  269. "metadata": {
  270. "collapsed": true,
  271. "trusted": false
  272. },
  273. "cell_type": "code",
  274. "source": "cnx = mysql.connector.connect(user='root', password='pagecount')\ncursor=cnx.cursor()\ntry:\n cnx.database = DB_NAME \nexcept mysql.connector.Error as err:\n if err.errno == errorcode.ER_BAD_DB_ERROR:\n create_database(cursor)\n cnx.database = DB_NAME\n else:\n print(err)\n exit(1)\n\ncursor.execute(\"SELECT * FROM pages WHERE times>=4\")\nprint(cursor.fetchall())\ncursor.execute(\"SELECT count(*) FROM pages WHERE times=3\")\nprint(cursor.fetchall())\ncursor.execute(\"SELECT count(*) FROM pages WHERE times=2\")\nprint(cursor.fetchall())\ncursor.execute(\"SELECT count(*) FROM pages WHERE times=1\")\nprint(cursor.fetchall())\ncursor.execute(\"SELECT count(*) FROM pages\")\nprint(cursor.fetchall())\ncursor.execute(\"SELECT * FROM pages WHERE pageName=\\\"ab %d0%90%d0%bb%d0%b0%d1%85%d3%99%d1%8b%d0%bb%d0%b0:Purodha\\\"\")\nprint(cursor.fetchall())",
  275. "execution_count": null,
  276. "outputs": []
  277. },
  278. {
  279. "metadata": {},
  280. "cell_type": "markdown",
  281. "source": "><p style=\"text-align: justify;\"><font color=#206da1>Finalement, l'approche avec l'utilisation d'une base de données est irréaliste, car le temps d'exécution est grandement allongé à cause des commandes d'insertion et de mise-à-jour.</font></p>"
  282. },
  283. {
  284. "metadata": {},
  285. "cell_type": "markdown",
  286. "source": "<a id='2'></a>\n# <font color=#c72b26>Méthode avec Hash</font>"
  287. },
  288. {
  289. "metadata": {},
  290. "cell_type": "markdown",
  291. "source": "><p style=\"text-align: justify;\"><font color=#206da1>La méthode présentée pendant le TP se base sur la connaissance à priori du nombre approxiatif de pages distinctes, cela nous permet de créer un objet de type bytearray qui demande peu d'espace mémoire.<br/>\nEt pour chaque page son index correspondant sera donné par une opération de hashing et de modulo (pour faire correspondre le hash à la taille du bytearray), on attribue la valeur 1 à chaque page visitée. <br/>\nAinsi, le nombre total de pages distinctes visitées peut être déduit de la somme des valeur du bytearray.</font></p>"
  292. },
  293. {
  294. "metadata": {
  295. "collapsed": true,
  296. "trusted": false
  297. },
  298. "cell_type": "code",
  299. "source": "import timeit\nimport time\nimport hashlib",
  300. "execution_count": 1,
  301. "outputs": []
  302. },
  303. {
  304. "metadata": {},
  305. "cell_type": "markdown",
  306. "source": "<a id='2.1'></a>\n## Estimation pour un fichier"
  307. },
  308. {
  309. "metadata": {
  310. "collapsed": true,
  311. "trusted": false
  312. },
  313. "cell_type": "code",
  314. "source": "def estimateHash(fileNumber, table):\n prefix = \"pagecounts-20150501-\"\n fname = prefix + \"{:02}0000\".format(fileNumber)\n !gunzip \"$fname\".gz\n k=0\n date0=time.perf_counter()\n with open(fname) as file:\n for line in file:\n k+=1\n datum=line.rsplit(None, 2)\n table[int(hashlib.sha1(datum[0].encode(\"UTF-8\")).hexdigest(), 16)%78000000]=1\n if k%1000000==0:\n date1=time.perf_counter()\n print(\"lignes comptées =\", k, date1-date0)\n date0=date1\n !gzip \"$fname\"\n return sum(table)",
  315. "execution_count": 2,
  316. "outputs": []
  317. },
  318. {
  319. "metadata": {},
  320. "cell_type": "markdown",
  321. "source": "><p style=\"text-align: justify;\"><font color=#206da1>L'exécution de la fonction nous montre que cette méthode est beaucoup plus rapide que celle précédente, pour 1 000 000 lignes 2,5 secondes suffisent. <br/>\nCependant, on constate qu'il y a un problème de collision pour la fonction de hashing, puisque le nombre total de pages distinctes retourné pour une heure ne correspond pas au nombre total théorique qui est le nombre de lignes.</font></p>"
  322. },
  323. {
  324. "metadata": {
  325. "scrolled": true,
  326. "trusted": false
  327. },
  328. "cell_type": "code",
  329. "source": "sumTable=bytearray(78000000)\nestimateHash(0, sumTable)\ndel sumTable",
  330. "execution_count": 18,
  331. "outputs": [
  332. {
  333. "name": "stdout",
  334. "output_type": "stream",
  335. "text": "lignes comptées = 1000000 2.738856936979573\nlignes comptées = 2000000 2.367499921005219\nlignes comptées = 3000000 2.350559971993789\nlignes comptées = 4000000 2.3313861889764667\nlignes comptées = 5000000 2.391034822037909\nlignes comptées = 6000000 2.436153232003562\nlignes comptées = 7000000 2.728035448992159\n"
  336. },
  337. {
  338. "data": {
  339. "text/plain": "6697477"
  340. },
  341. "execution_count": 18,
  342. "metadata": {},
  343. "output_type": "execute_result"
  344. }
  345. ]
  346. },
  347. {
  348. "metadata": {
  349. "trusted": false
  350. },
  351. "cell_type": "code",
  352. "source": "sumTable=bytearray(78000000)\ntimeit.timeit(\"estimateHash(0, sumTable)\", number=1, globals=globals())\ndel sumTable",
  353. "execution_count": 20,
  354. "outputs": [
  355. {
  356. "name": "stdout",
  357. "output_type": "stream",
  358. "text": "lignes comptées = 1000000 2.696550427994225\nlignes comptées = 2000000 2.390967476007063\nlignes comptées = 3000000 2.393663077033125\nlignes comptées = 4000000 2.3836354030063376\nlignes comptées = 5000000 2.438323018955998\nlignes comptées = 6000000 2.479662792000454\nlignes comptées = 7000000 2.775245661032386\n"
  359. },
  360. {
  361. "data": {
  362. "text/plain": "40.88963726902148"
  363. },
  364. "execution_count": 20,
  365. "metadata": {},
  366. "output_type": "execute_result"
  367. }
  368. ]
  369. },
  370. {
  371. "metadata": {},
  372. "cell_type": "markdown",
  373. "source": "<a id='2.2'></a>\n## Estimation sur un jour"
  374. },
  375. {
  376. "metadata": {
  377. "collapsed": true,
  378. "trusted": false
  379. },
  380. "cell_type": "code",
  381. "source": "def estimateAllHash():\n sumTable=bytearray(78000000)\n for i in range(24):\n estimateHash(i, sumTable)\n print(sum(sumTable))\n return sum(sumTable)",
  382. "execution_count": 23,
  383. "outputs": []
  384. },
  385. {
  386. "metadata": {},
  387. "cell_type": "markdown",
  388. "source": "><p style=\"text-align: justify;\"><font color=#206da1>La valeur estimée est de l'ordre de la valeur exacte donnée (78 000 000).<br/>\nMais elle est quand même assez grossière avec une erreur relative d'environ 33%.</font></p>"
  389. },
  390. {
  391. "metadata": {
  392. "trusted": false
  393. },
  394. "cell_type": "code",
  395. "source": "estimateAllHash()",
  396. "execution_count": 5,
  397. "outputs": [
  398. {
  399. "name": "stdout",
  400. "output_type": "stream",
  401. "text": "lignes comptées = 1000000 2.3340337990084663\nlignes comptées = 2000000 2.1042312490171753\nlignes comptées = 3000000 2.122077266976703\nlignes comptées = 4000000 2.1011148099787533\nlignes comptées = 5000000 2.1499028550460935\nlignes comptées = 6000000 2.2149174039950594\nlignes comptées = 7000000 2.4944520719582215\nlignes comptées = 1000000 2.4010007940232754\nlignes comptées = 2000000 2.1146330279880203\nlignes comptées = 3000000 2.148885894974228\nlignes comptées = 4000000 2.1035014160443097\nlignes comptées = 5000000 2.1663973149843514\nlignes comptées = 6000000 2.188354765996337\nlignes comptées = 1000000 2.3519532100181095\nlignes comptées = 2000000 2.1095603939611465\nlignes comptées = 3000000 2.1275065180379897\nlignes comptées = 4000000 2.115973401989322\nlignes comptées = 5000000 2.158900832000654\nlignes comptées = 6000000 2.226938906009309\nlignes comptées = 7000000 2.4099803270073608\nlignes comptées = 1000000 2.3702584429993294\nlignes comptées = 2000000 2.13276654999936\nlignes comptées = 3000000 2.1391375199891627\nlignes comptées = 4000000 2.1328889139695093\nlignes comptées = 5000000 2.1764597360161133\nlignes comptées = 6000000 2.216086541011464\nlignes comptées = 7000000 2.2632107280078344\nlignes comptées = 1000000 2.3745187610038556\nlignes comptées = 2000000 2.105182542989496\nlignes comptées = 3000000 2.119562749983743\nlignes comptées = 4000000 2.120086334994994\nlignes comptées = 5000000 2.1763733020052314\nlignes comptées = 6000000 2.207549843005836\nlignes comptées = 1000000 2.369731752027292\nlignes comptées = 2000000 2.10211821901612\nlignes comptées = 3000000 2.1194358819629997\nlignes comptées = 4000000 2.124724599008914\nlignes comptées = 5000000 2.1841655090101995\nlignes comptées = 6000000 2.2163026059861295\nlignes comptées = 1000000 2.405928891035728\nlignes comptées = 2000000 2.1146296850056387\nlignes comptées = 3000000 2.1091489399550483\nlignes comptées = 4000000 2.1369255729950964\nlignes comptées = 5000000 2.1812689510406926\nlignes comptées = 6000000 2.2122767369728535\nlignes comptées = 7000000 2.4567218989832327\nlignes comptées = 1000000 2.348884987994097\nlignes comptées = 2000000 2.119203509995714\nlignes comptées = 3000000 2.1123256019782275\nlignes comptées = 4000000 2.1203118890407495\nlignes comptées = 5000000 2.168991055979859\nlignes comptées = 6000000 2.1985843000002205\nlignes comptées = 1000000 2.318699021008797\nlignes comptées = 2000000 2.131013962032739\nlignes comptées = 3000000 2.1025503400014713\nlignes comptées = 4000000 2.122457865974866\nlignes comptées = 5000000 2.145487921021413\nlignes comptées = 6000000 2.183375750959385\nlignes comptées = 7000000 2.2710090270265937\nlignes comptées = 1000000 2.3531640939763747\nlignes comptées = 2000000 2.120760209974833\nlignes comptées = 3000000 2.1175346780219115\nlignes comptées = 4000000 2.1100815220270306\nlignes comptées = 5000000 2.141443979984615\nlignes comptées = 6000000 2.197744780976791\nlignes comptées = 7000000 2.2466658710036427\nlignes comptées = 1000000 2.347803540993482\nlignes comptées = 2000000 2.120093800011091\nlignes comptées = 3000000 2.1206498609972186\nlignes comptées = 4000000 2.107656619977206\nlignes comptées = 5000000 2.176918380020652\nlignes comptées = 6000000 2.278726438002195\nlignes comptées = 7000000 2.232302662974689\nlignes comptées = 1000000 2.4040404729894362\nlignes comptées = 2000000 2.1078570450190455\nlignes comptées = 3000000 2.177767952962313\nlignes comptées = 4000000 2.1072764089913107\nlignes comptées = 5000000 2.1562504390021786\nlignes comptées = 6000000 2.1875464360346086\nlignes comptées = 7000000 2.2147514820098877\nlignes comptées = 8000000 2.2686241579940543\nlignes comptées = 1000000 2.3603540789918043\nlignes comptées = 2000000 2.120601586997509\nlignes comptées = 3000000 2.1361187900183722\nlignes comptées = 4000000 2.0892717509996146\nlignes comptées = 5000000 2.1509202499873936\nlignes comptées = 6000000 2.1663473970256746\nlignes comptées = 7000000 2.2121841280022636\nlignes comptées = 1000000 2.334596956963651\nlignes comptées = 2000000 2.112707888998557\nlignes comptées = 3000000 2.136019369994756\nlignes comptées = 4000000 2.0981460210168734\nlignes comptées = 5000000 2.1303880530176684\nlignes comptées = 6000000 2.170369874977041\nlignes comptées = 7000000 2.1858169920160435\nlignes comptées = 8000000 2.205970105016604\nlignes comptées = 1000000 2.3854673739988357\nlignes comptées = 2000000 2.117052849032916\nlignes comptées = 3000000 2.122467611974571\nlignes comptées = 4000000 2.0943751240265556\nlignes comptées = 5000000 2.1352934109745547\nlignes comptées = 6000000 2.160450753988698\nlignes comptées = 7000000 2.1795719250221737\nlignes comptées = 8000000 2.195537501014769\nlignes comptées = 1000000 2.368364652968012\nlignes comptées = 2000000 2.12418072798755\nlignes comptées = 3000000 2.1266723060398363\nlignes comptées = 4000000 2.0806756409583613\nlignes comptées = 5000000 2.135603330039885\nlignes comptées = 6000000 2.156069780001417\nlignes comptées = 7000000 2.172398181981407\nlignes comptées = 8000000 2.2650500549934804\nlignes comptées = 1000000 2.360622695006896\nlignes comptées = 2000000 2.1274649960105307\nlignes comptées = 3000000 2.1282469920115545\nlignes comptées = 4000000 2.115556859993376\nlignes comptées = 5000000 2.124373674974777\nlignes comptées = 6000000 2.1471153480233625\nlignes comptées = 7000000 2.184729859989602\nlignes comptées = 8000000 2.2611858809832484\nlignes comptées = 1000000 2.368719157006126\nlignes comptées = 2000000 2.1182214620057493\nlignes comptées = 3000000 2.1221491300384514\nlignes comptées = 4000000 2.10240019595949\nlignes comptées = 5000000 2.133677816018462\nlignes comptées = 6000000 2.173518661002163\nlignes comptées = 7000000 2.1806885339901783\nlignes comptées = 8000000 2.252467248006724\nlignes comptées = 1000000 2.385356211976614\nlignes comptées = 2000000 2.123432459018659\nlignes comptées = 3000000 2.148059496015776\nlignes comptées = 4000000 2.1040521149989218\nlignes comptées = 5000000 2.1210499639855698\nlignes comptées = 6000000 2.1422108330298215\nlignes comptées = 7000000 2.1571419179672375\nlignes comptées = 8000000 2.251774991978891\nlignes comptées = 1000000 2.3169710770016536\nlignes comptées = 2000000 2.13592306204373\nlignes comptées = 3000000 2.1462042559869587\nlignes comptées = 4000000 2.1044367069844157\nlignes comptées = 5000000 2.1178905480192043\nlignes comptées = 6000000 2.1360291719902307\nlignes comptées = 7000000 2.1696316900197417\nlignes comptées = 8000000 2.2731918639619835\nlignes comptées = 1000000 2.3421697359881364\nlignes comptées = 2000000 2.1222591520054266\nlignes comptées = 3000000 2.1456943129887804\nlignes comptées = 4000000 2.1062733420403674\nlignes comptées = 5000000 2.124090517987497\nlignes comptées = 6000000 2.157334206975065\nlignes comptées = 7000000 2.166176555037964\nlignes comptées = 8000000 2.247595069988165\nlignes comptées = 1000000 2.3837170589831658\nlignes comptées = 2000000 2.12703903100919\nlignes comptées = 3000000 2.12018921301933\nlignes comptées = 4000000 2.1030840799794532\nlignes comptées = 5000000 2.117272528994363\nlignes comptées = 6000000 2.166925291006919\nlignes comptées = 7000000 2.1841966829961166\nlignes comptées = 8000000 2.2611318550189026\nlignes comptées = 1000000 2.3921215379959904\nlignes comptées = 2000000 2.1312389799859375\nlignes comptées = 3000000 2.1241798360133544\nlignes comptées = 4000000 2.0914006259990856\nlignes comptées = 5000000 2.1369382580160163\nlignes comptées = 6000000 2.175109382951632\nlignes comptées = 7000000 2.2147888489998877\nlignes comptées = 1000000 2.436071751988493\nlignes comptées = 2000000 2.1289610440144315\nlignes comptées = 3000000 2.1357039349968545\nlignes comptées = 4000000 2.1060258289799094\nlignes comptées = 5000000 2.1464496750268154\nlignes comptées = 6000000 2.1665598480030894\nlignes comptées = 7000000 2.2309849949670024\n50091453\n"
  402. },
  403. {
  404. "data": {
  405. "text/plain": "50091453"
  406. },
  407. "execution_count": 5,
  408. "metadata": {},
  409. "output_type": "execute_result"
  410. }
  411. ]
  412. },
  413. {
  414. "metadata": {},
  415. "cell_type": "markdown",
  416. "source": "><p style=\"text-align: justify;\"><font color=#206da1>Le temps d'exécution étant d'environ 17 minutes est raisonnable, cela correspond à 45 seconde pour l'analyse d'un fichier.</font></p>"
  417. },
  418. {
  419. "metadata": {
  420. "scrolled": true,
  421. "trusted": false
  422. },
  423. "cell_type": "code",
  424. "source": "timeit.timeit(\"estimateAllHash()\", number=1, globals=globals())",
  425. "execution_count": 154,
  426. "outputs": [
  427. {
  428. "name": "stdout",
  429. "output_type": "stream",
  430. "text": "lignes comptées = 1000000 2.7124534780159593\nlignes comptées = 2000000 2.1750711639760993\nlignes comptées = 3000000 2.1676109840045683\nlignes comptées = 4000000 2.1729206719901413\nlignes comptées = 5000000 2.2340669370023534\nlignes comptées = 6000000 2.268510056019295\nlignes comptées = 7000000 2.560438584012445\nlignes comptées = 1000000 2.846118544053752\nlignes comptées = 2000000 2.1690552429645322\nlignes comptées = 3000000 2.2168255189899355\nlignes comptées = 4000000 2.149522577004973\nlignes comptées = 5000000 2.2293898970237933\nlignes comptées = 6000000 2.261234058008995\nlignes comptées = 1000000 2.633330091019161\nlignes comptées = 2000000 2.174927008978557\nlignes comptées = 3000000 2.1666312409797683\nlignes comptées = 4000000 2.155994051019661\nlignes comptées = 5000000 2.2243955539888702\nlignes comptées = 6000000 2.2633991080219857\nlignes comptées = 7000000 2.4838943340000696\nlignes comptées = 1000000 2.692393967008684\nlignes comptées = 2000000 2.175709659990389\nlignes comptées = 3000000 2.164218374993652\nlignes comptées = 4000000 2.174327426007949\nlignes comptées = 5000000 2.196390283992514\nlignes comptées = 6000000 2.2586109020048752\nlignes comptées = 7000000 2.3261873070150614\nlignes comptées = 1000000 2.595681246020831\nlignes comptées = 2000000 2.2209177269833162\nlignes comptées = 3000000 2.180418278032448\nlignes comptées = 4000000 2.1808447059593163\nlignes comptées = 5000000 2.2588474210351706\nlignes comptées = 6000000 2.2713235359988175\nlignes comptées = 1000000 2.6446336090448312\nlignes comptées = 2000000 2.155576864955947\nlignes comptées = 3000000 2.168810627015773\nlignes comptées = 4000000 2.1809917640057392\nlignes comptées = 5000000 2.249481270031538\nlignes comptées = 6000000 2.2570705519756302\nlignes comptées = 1000000 2.5378687589545734\nlignes comptées = 2000000 2.159323737025261\nlignes comptées = 3000000 2.1584185179672204\nlignes comptées = 4000000 2.177011334046256\nlignes comptées = 5000000 2.2515804729773663\nlignes comptées = 6000000 2.271638994978275\nlignes comptées = 7000000 2.497946012998\nlignes comptées = 1000000 2.5335839170147665\nlignes comptées = 2000000 2.1734841609722935\nlignes comptées = 3000000 2.1744770020013675\nlignes comptées = 4000000 2.1874243590282276\nlignes comptées = 5000000 2.2453955539967865\nlignes comptées = 6000000 2.285622276016511\nlignes comptées = 1000000 2.4976847489597276\nlignes comptées = 2000000 2.192647443036549\nlignes comptées = 3000000 2.197141784010455\nlignes comptées = 4000000 2.183005240978673\nlignes comptées = 5000000 2.2228714139782824\nlignes comptées = 6000000 2.2611665410222486\nlignes comptées = 7000000 2.33809748000931\nlignes comptées = 1000000 2.507470755954273\nlignes comptées = 2000000 2.220543855044525\nlignes comptées = 3000000 2.2625526299816556\nlignes comptées = 4000000 2.1578629669966176\nlignes comptées = 5000000 2.22034054499818\nlignes comptées = 6000000 2.2388997899834067\nlignes comptées = 7000000 2.309826350014191\nlignes comptées = 1000000 2.3961256799520925\nlignes comptées = 2000000 2.187970981001854\nlignes comptées = 3000000 2.1984230040106922\nlignes comptées = 4000000 2.1767480470007285\nlignes comptées = 5000000 2.1970407550106756\nlignes comptées = 6000000 2.2467214959906414\nlignes comptées = 7000000 2.309615050035063\nlignes comptées = 1000000 2.4121940479963087\nlignes comptées = 2000000 2.1714819920016453\nlignes comptées = 3000000 2.1768940549809486\nlignes comptées = 4000000 2.1540855560451746\nlignes comptées = 5000000 2.195291306008585\nlignes comptées = 6000000 2.2343692729482427\nlignes comptées = 7000000 2.261669210041873\nlignes comptées = 8000000 2.32574574399041\nlignes comptées = 1000000 2.4067881499649957\nlignes comptées = 2000000 2.1811567500117235\nlignes comptées = 3000000 2.167096154007595\nlignes comptées = 4000000 2.158731887000613\nlignes comptées = 5000000 2.200948357989546\nlignes comptées = 6000000 2.229869751026854\nlignes comptées = 7000000 2.2822369529749267\nlignes comptées = 1000000 2.371641887992155\nlignes comptées = 2000000 2.184601376997307\nlignes comptées = 3000000 2.1742648030049168\nlignes comptées = 4000000 2.1669395189965144\nlignes comptées = 5000000 2.194421771040652\nlignes comptées = 6000000 2.2386904569575563\nlignes comptées = 7000000 2.2498667979962192\nlignes comptées = 8000000 2.275219138013199\nlignes comptées = 1000000 2.4056815179646946\nlignes comptées = 2000000 2.2693552230484784\nlignes comptées = 3000000 2.173966367961839\nlignes comptées = 4000000 2.153113820008002\nlignes comptées = 5000000 2.17986401199596\nlignes comptées = 6000000 2.2464676669915207\nlignes comptées = 7000000 2.2330831100116484\nlignes comptées = 8000000 2.280345887003932\nlignes comptées = 1000000 2.3400816849898547\nlignes comptées = 2000000 2.1970777040114626\nlignes comptées = 3000000 2.1701835470157675\nlignes comptées = 4000000 2.160338786954526\nlignes comptées = 5000000 2.185635114030447\nlignes comptées = 6000000 2.222902223991696\nlignes comptées = 7000000 2.2290327370283194\nlignes comptées = 8000000 2.3184239869588055\nlignes comptées = 1000000 2.436520492017735\nlignes comptées = 2000000 2.1945223389775492\nlignes comptées = 3000000 2.1817815370159224\nlignes comptées = 4000000 2.148232334002387\nlignes comptées = 5000000 2.1696326609817334\nlignes comptées = 6000000 2.199182260024827\nlignes comptées = 7000000 2.237186054990161\nlignes comptées = 8000000 2.3204015369992703\nlignes comptées = 1000000 2.3401545269880444\nlignes comptées = 2000000 2.1914028159808367\nlignes comptées = 3000000 2.1959687329945154\nlignes comptées = 4000000 2.158988092036452\nlignes comptées = 5000000 2.1760116610093974\nlignes comptées = 6000000 2.198099125002045\nlignes comptées = 7000000 2.2265521899680607\nlignes comptées = 8000000 2.324316677986644\nlignes comptées = 1000000 2.3637406050111167\nlignes comptées = 2000000 2.184752044035122\nlignes comptées = 3000000 2.167104779975489\nlignes comptées = 4000000 2.160589240025729\nlignes comptées = 5000000 2.1908836599905044\nlignes comptées = 6000000 2.217145595001057\nlignes comptées = 7000000 2.2287675889674574\nlignes comptées = 8000000 2.328001638990827\nlignes comptées = 1000000 2.37793935299851\nlignes comptées = 2000000 2.172695145010948\nlignes comptées = 3000000 2.165311800024938\nlignes comptées = 4000000 2.1573957129730843\nlignes comptées = 5000000 2.1907775460276753\nlignes comptées = 6000000 2.203708947985433\nlignes comptées = 7000000 2.223754510981962\nlignes comptées = 8000000 2.319817444018554\nlignes comptées = 1000000 2.3372212680405937\nlignes comptées = 2000000 2.178312105999794\nlignes comptées = 3000000 2.1728107479866594\nlignes comptées = 4000000 2.1600150039885193\nlignes comptées = 5000000 2.180367348017171\nlignes comptées = 6000000 2.2167890630080365\nlignes comptées = 7000000 2.2212976629962213\nlignes comptées = 8000000 2.621777491993271\nlignes comptées = 1000000 2.4301244220114313\nlignes comptées = 2000000 2.189249694987666\nlignes comptées = 3000000 2.1908847889862955\nlignes comptées = 4000000 2.1859710100106895\nlignes comptées = 5000000 2.20030427898746\nlignes comptées = 6000000 2.2374076030100696\nlignes comptées = 7000000 2.2401333349989727\nlignes comptées = 8000000 2.31555160501739\nlignes comptées = 1000000 2.360444230027497\nlignes comptées = 2000000 2.1813379770028405\nlignes comptées = 3000000 2.194706344977021\nlignes comptées = 4000000 2.150533006002661\nlignes comptées = 5000000 2.187561883009039\nlignes comptées = 6000000 2.2306446509901434\nlignes comptées = 7000000 2.2708005270105787\nlignes comptées = 1000000 2.38879180297954\nlignes comptées = 2000000 2.177016380999703\nlignes comptées = 3000000 2.1742948920000345\nlignes comptées = 4000000 2.1659792860154994\nlignes comptées = 5000000 2.210127038997598\nlignes comptées = 6000000 2.2302919320063666\nlignes comptées = 7000000 2.2848666260251775\n"
  431. },
  432. {
  433. "data": {
  434. "text/plain": "1043.3873954479932"
  435. },
  436. "execution_count": 154,
  437. "metadata": {},
  438. "output_type": "execute_result"
  439. }
  440. ]
  441. },
  442. {
  443. "metadata": {},
  444. "cell_type": "markdown",
  445. "source": "<a id='3'></a>\n# <font color=#c72b26>Méthode Hash : amélioration</font>"
  446. },
  447. {
  448. "metadata": {},
  449. "cell_type": "markdown",
  450. "source": "><p style=\"text-align: justify;\"><font color=#206da1 size=4px>Pour améliorer la performance de l'algorithme, j'ai eu 4 approches différentes :</font></p>\n- <font color=#206da1>Augmentation de la taille du bytearray</font>\n- <font color=#206da1>Fonctions de hashing différentes</font>\n- <font color=#206da1>Partition des noms de page</font>\n- <font color=#206da1>Gestion explicite de collision</font>"
  451. },
  452. {
  453. "metadata": {},
  454. "cell_type": "markdown",
  455. "source": "<a id='3.1'></a>\n## Augmentation de la taille du bytearray"
  456. },
  457. {
  458. "metadata": {},
  459. "cell_type": "markdown",
  460. "source": "><p style=\"text-align: justify;\"><font color=#206da1>Précédemment, le nombre de collisions était assez grand, cela entraîne une erreur de 33%. Pour diminuer le nombre de collisions, on peut augmenter la taille du bytearray, ainsi après l'opération de modulo, l'index résultant sera moins redondant pour des noms de page différent.<br/>\nJ'ai choisi arbitrairement de doubler sa taille, on passe donc à 160 000 000.</font></p>"
  461. },
  462. {
  463. "metadata": {
  464. "collapsed": true,
  465. "trusted": false
  466. },
  467. "cell_type": "code",
  468. "source": "def estimateHashImp1(fileNumber, table):\n prefix = \"pagecounts-20150501-\"\n fname = prefix + \"{:02}0000\".format(fileNumber)\n !gunzip \"$fname\".gz\n k=0\n date0=time.perf_counter()\n with open(fname) as file:\n for line in file:\n k+=1\n datum=line.rsplit(None, 2)\n table[int(hashlib.sha1(datum[0].encode(\"UTF-8\")).hexdigest(), 16)%160000000]=1\n if k%1000000==0:\n date1=time.perf_counter()\n print(\"lignes comptées =\", k, date1-date0)\n date0=date1\n !gzip \"$fname\"\n return sum(table)",
  469. "execution_count": null,
  470. "outputs": []
  471. },
  472. {
  473. "metadata": {},
  474. "cell_type": "markdown",
  475. "source": "><p style=\"text-align: justify;\"><font color=#206da1>Pour l'analyse d'un fichier, le nombre de pages distinctes estimé 6 852 132 se rapproche plus de la valeur théorique au tour de 7 000 000.</font></p>"
  476. },
  477. {
  478. "metadata": {
  479. "scrolled": true,
  480. "trusted": false
  481. },
  482. "cell_type": "code",
  483. "source": "sumTable=bytearray(160000000)\nestimateHashImp1(0, sumTable)\ndel sumTable",
  484. "execution_count": 22,
  485. "outputs": [
  486. {
  487. "name": "stdout",
  488. "output_type": "stream",
  489. "text": "lignes comptées = 1000000 2.6545328029897064\nlignes comptées = 2000000 2.3423527640406974\nlignes comptées = 3000000 2.375286269991193\nlignes comptées = 4000000 2.3528402189840563\nlignes comptées = 5000000 2.4067155109951273\nlignes comptées = 6000000 2.4645981999929063\nlignes comptées = 7000000 2.779305207019206\n"
  490. },
  491. {
  492. "data": {
  493. "text/plain": "6852132"
  494. },
  495. "execution_count": 22,
  496. "metadata": {},
  497. "output_type": "execute_result"
  498. }
  499. ]
  500. },
  501. {
  502. "metadata": {
  503. "collapsed": true,
  504. "trusted": false
  505. },
  506. "cell_type": "code",
  507. "source": "def estimateAllHashImp1():\n sumTable=bytearray(160000000)\n for i in range(24):\n estimateHash(i, sumTable)\n print(sum(sumTable))\n return sum(sumTable)",
  508. "execution_count": null,
  509. "outputs": []
  510. },
  511. {
  512. "metadata": {},
  513. "cell_type": "markdown",
  514. "source": "><p style=\"text-align: justify;\"><font color=#206da1>En ce qui concerne l'analyse pour la journée entière, le résultat donné par l'algorithme est de 63 050 252 ce qui représente une erreur relative de 16%.<br/>\nL'erreur relative a été divisée par deux en doublant la taille du bytearray, on aurait ici une relation linéaire. </font></p>"
  515. },
  516. {
  517. "metadata": {
  518. "scrolled": true,
  519. "trusted": false
  520. },
  521. "cell_type": "code",
  522. "source": "estimateAllHashImp1()",
  523. "execution_count": 4,
  524. "outputs": [
  525. {
  526. "name": "stdout",
  527. "output_type": "stream",
  528. "text": "lignes comptées = 1000000 2.401384466968011\nlignes comptées = 2000000 2.11243859102251\nlignes comptées = 3000000 2.120632749982178\nlignes comptées = 4000000 2.102987401012797\nlignes comptées = 5000000 2.1884042359888554\nlignes comptées = 6000000 2.2369548430433497\nlignes comptées = 7000000 2.5121270079980604\nlignes comptées = 1000000 2.432590060052462\nlignes comptées = 2000000 2.0804387099924497\nlignes comptées = 3000000 2.0740957689704373\nlignes comptées = 4000000 2.07550038699992\nlignes comptées = 5000000 2.148914750025142\nlignes comptées = 6000000 2.1999930900055915\nlignes comptées = 1000000 2.420702012022957\nlignes comptées = 2000000 2.0940825309953652\nlignes comptées = 3000000 2.095276270993054\nlignes comptées = 4000000 2.0925840539857745\nlignes comptées = 5000000 2.1446560590411536\nlignes comptées = 6000000 2.2114182939985767\nlignes comptées = 7000000 2.4288150889915414\nlignes comptées = 1000000 2.4216810170328245\nlignes comptées = 2000000 2.1159769889782183\nlignes comptées = 3000000 2.1528745259856805\nlignes comptées = 4000000 2.115139889996499\nlignes comptées = 5000000 2.157310303009581\nlignes comptées = 6000000 2.1945702329976484\nlignes comptées = 7000000 2.2626790280337445\nlignes comptées = 1000000 2.430614539014641\nlignes comptées = 2000000 2.1019564360030927\nlignes comptées = 3000000 2.092465634981636\nlignes comptées = 4000000 2.1027981369988993\nlignes comptées = 5000000 2.1815159589750692\nlignes comptées = 6000000 2.1998739460250363\nlignes comptées = 1000000 2.438102793006692\nlignes comptées = 2000000 2.104723604978062\nlignes comptées = 3000000 2.1149607520201243\nlignes comptées = 4000000 2.113057848007884\nlignes comptées = 5000000 2.186840287002269\nlignes comptées = 6000000 2.189291017013602\nlignes comptées = 1000000 2.3924908650224097\nlignes comptées = 2000000 2.142537153966259\nlignes comptées = 3000000 2.1274995830026455\nlignes comptées = 4000000 2.114174341026228\nlignes comptées = 5000000 2.177617678011302\nlignes comptées = 6000000 2.19599764799932\nlignes comptées = 7000000 2.4552889699698426\nlignes comptées = 1000000 2.3224376320140436\nlignes comptées = 2000000 2.1109133940190077\nlignes comptées = 3000000 2.126914524997119\nlignes comptées = 4000000 2.104819905012846\nlignes comptées = 5000000 2.1874868539744057\nlignes comptées = 6000000 2.2109117829822935\nlignes comptées = 1000000 2.341909668990411\nlignes comptées = 2000000 2.1133191169938073\nlignes comptées = 3000000 2.1219072380336\nlignes comptées = 4000000 2.101508550986182\nlignes comptées = 5000000 2.115863013023045\nlignes comptées = 6000000 2.146952639974188\nlignes comptées = 7000000 2.259743511036504\nlignes comptées = 1000000 2.370058786997106\nlignes comptées = 2000000 2.1161160600022413\nlignes comptées = 3000000 2.1873838549945503\nlignes comptées = 4000000 2.087549122981727\nlignes comptées = 5000000 2.131589481025003\nlignes comptées = 6000000 2.164825430023484\nlignes comptées = 7000000 2.2294444019789807\nlignes comptées = 1000000 2.33538603404304\nlignes comptées = 2000000 2.110035607998725\nlignes comptées = 3000000 2.1146882079774514\nlignes comptées = 4000000 2.093808865000028\nlignes comptées = 5000000 2.150079693994485\nlignes comptées = 6000000 2.1736403460381553\nlignes comptées = 7000000 2.244931002962403\nlignes comptées = 1000000 2.3561539740185253\nlignes comptées = 2000000 2.1269246530137025\nlignes comptées = 3000000 2.1086448970017955\nlignes comptées = 4000000 2.0909634679555893\nlignes comptées = 5000000 2.1285366149968468\nlignes comptées = 6000000 2.1770365400006995\nlignes comptées = 7000000 2.1963121400331147\nlignes comptées = 8000000 2.2773921450134367\nlignes comptées = 1000000 2.3757019320037216\nlignes comptées = 2000000 2.1370866050128825\nlignes comptées = 3000000 2.132911927998066\nlignes comptées = 4000000 2.1086479609948583\nlignes comptées = 5000000 2.142482391966041\nlignes comptées = 6000000 2.176297788042575\nlignes comptées = 7000000 2.2316787139861844\nlignes comptées = 1000000 2.4135152010130696\nlignes comptées = 2000000 2.135945571004413\nlignes comptées = 3000000 2.125419289979618\nlignes comptées = 4000000 2.0921644110349007\nlignes comptées = 5000000 2.1294631239725277\nlignes comptées = 6000000 2.1748431200394407\nlignes comptées = 7000000 2.199464467994403\nlignes comptées = 8000000 2.2262662060093135\nlignes comptées = 1000000 2.3817805989529006\nlignes comptées = 2000000 2.131990151014179\nlignes comptées = 3000000 2.1278035360155627\nlignes comptées = 4000000 2.0782622330007143\nlignes comptées = 5000000 2.1186944019864313\nlignes comptées = 6000000 2.1841909530339763\nlignes comptées = 7000000 2.183295733993873\nlignes comptées = 8000000 2.2109531089663506\nlignes comptées = 1000000 2.3639000129769556\nlignes comptées = 2000000 2.1219877210096456\nlignes comptées = 3000000 2.120451711001806\nlignes comptées = 4000000 2.095573742000852\nlignes comptées = 5000000 2.107385626004543\nlignes comptées = 6000000 2.143359816982411\nlignes comptées = 7000000 2.1742392880260013\nlignes comptées = 8000000 2.2443905199761502\nlignes comptées = 1000000 2.3863539379672147\nlignes comptées = 2000000 2.1143443200271577\nlignes comptées = 3000000 2.118349300988484\nlignes comptées = 4000000 2.098547635017894\nlignes comptées = 5000000 2.088935215957463\nlignes comptées = 6000000 2.1204433210077696\nlignes comptées = 7000000 2.1556823099963367\nlignes comptées = 8000000 2.2446890129940584\nlignes comptées = 1000000 2.3524639399838634\nlignes comptées = 2000000 2.120831035019364\nlignes comptées = 3000000 2.1663687079562806\nlignes comptées = 4000000 2.08609456801787\nlignes comptées = 5000000 2.0996304500149563\nlignes comptées = 6000000 2.1206088089966215\nlignes comptées = 7000000 2.148395472962875\nlignes comptées = 8000000 2.2483085690182634\nlignes comptées = 1000000 2.359656930959318\nlignes comptées = 2000000 2.0926140770316124\nlignes comptées = 3000000 2.1083083850098774\nlignes comptées = 4000000 2.084790834982414\nlignes comptées = 5000000 2.121022956969682\nlignes comptées = 6000000 2.1364699600380845\nlignes comptées = 7000000 2.1676501909969375\nlignes comptées = 8000000 2.2677934789680876\nlignes comptées = 1000000 2.3270349929807708\nlignes comptées = 2000000 2.1034068720182404\nlignes comptées = 3000000 2.079944349010475\nlignes comptées = 4000000 2.079946818994358\nlignes comptées = 5000000 2.0929653630009852\nlignes comptées = 6000000 2.115906698978506\nlignes comptées = 7000000 2.148354316013865\nlignes comptées = 8000000 2.252659271005541\nlignes comptées = 1000000 2.3321329969912767\nlignes comptées = 2000000 2.0916155240265653\nlignes comptées = 3000000 2.1041285829851404\nlignes comptées = 4000000 2.0667744830134325\nlignes comptées = 5000000 2.0984611379681155\nlignes comptées = 6000000 2.129444853984751\nlignes comptées = 7000000 2.1476286870311014\nlignes comptées = 8000000 2.2402445700136013\nlignes comptées = 1000000 2.3738289659959264\nlignes comptées = 2000000 2.1311121479957364\nlignes comptées = 3000000 2.1081369079765864\nlignes comptées = 4000000 2.0968880750006065\nlignes comptées = 5000000 2.115921108983457\nlignes comptées = 6000000 2.125563515990507\nlignes comptées = 7000000 2.1621447530342266\nlignes comptées = 8000000 2.222206100996118\nlignes comptées = 1000000 2.364065384026617\nlignes comptées = 2000000 2.115887440973893\nlignes comptées = 3000000 2.1277842450072058\nlignes comptées = 4000000 2.0939636530238204\nlignes comptées = 5000000 2.13162400200963\nlignes comptées = 6000000 2.176841003994923\nlignes comptées = 7000000 2.2176010650000535\nlignes comptées = 1000000 2.309131089015864\nlignes comptées = 2000000 2.10390244203154\nlignes comptées = 3000000 2.127306623966433\nlignes comptées = 4000000 2.098589316010475\nlignes comptées = 5000000 2.1433061020215973\nlignes comptées = 6000000 2.158190219954122\nlignes comptées = 7000000 2.2259344840422273\n63050252\n"
  529. },
  530. {
  531. "data": {
  532. "text/plain": "63050252"
  533. },
  534. "execution_count": 4,
  535. "metadata": {},
  536. "output_type": "execute_result"
  537. }
  538. ]
  539. },
  540. {
  541. "metadata": {},
  542. "cell_type": "markdown",
  543. "source": "<a id='3.2'></a>\n## Fonctions de hashing différentes"
  544. },
  545. {
  546. "metadata": {},
  547. "cell_type": "markdown",
  548. "source": "><p style=\"text-align: justify;\"><font color=#206da1>Il existe plusieurs algorithmes pour le hashing, je propose donc d'analyser la performances des différents algorithmes en ce qui concerne les collision.</font></p>"
  549. },
  550. {
  551. "metadata": {
  552. "collapsed": true,
  553. "trusted": false
  554. },
  555. "cell_type": "code",
  556. "source": "def estimateHashImp2(fileNumber, table, hashFunction):\n prefix = \"pagecounts-20150501-\"\n fname = prefix + \"{:02}0000\".format(fileNumber)\n !gunzip \"$fname\".gz\n k=0\n date0=time.perf_counter()\n with open(fname) as file:\n for line in file:\n k+=1\n datum=line.rsplit(None, 2)\n table[int(hashFunction(datum[0].encode(\"UTF-8\")).hexdigest(), 16)%78000000]=1\n date1=time.perf_counter()\n !gzip \"$fname\"\n print(\"Temps d'exécution\", date1-date0)\n ret=sum(table)\n print(\"Pages distinctes\", ret)\n return ret",
  557. "execution_count": 9,
  558. "outputs": []
  559. },
  560. {
  561. "metadata": {},
  562. "cell_type": "markdown",
  563. "source": "><p style=\"text-align: justify;\"><font color=#206da1>En utilisant différents algorithmes sur le premier fichier comme le montre les sorties affichées ci-dessous, les valeurs estimées par ces algorithmes sont très proches, on n'aura donc pas une amélioration nette en changeant la fonction de hashing.</font></p>"
  564. },
  565. {
  566. "metadata": {
  567. "trusted": false
  568. },
  569. "cell_type": "code",
  570. "source": "sumTable=bytearray(78000000)\nestimateHashImp2(0, sumTable, hashlib.md5)\ndel sumTable",
  571. "execution_count": 10,
  572. "outputs": [
  573. {
  574. "name": "stdout",
  575. "output_type": "stream",
  576. "text": "Temps d'exécution 14.343614206998609\n"
  577. },
  578. {
  579. "data": {
  580. "text/plain": "6698405"
  581. },
  582. "execution_count": 10,
  583. "metadata": {},
  584. "output_type": "execute_result"
  585. }
  586. ]
  587. },
  588. {
  589. "metadata": {
  590. "trusted": false
  591. },
  592. "cell_type": "code",
  593. "source": "sumTable=bytearray(78000000)\nestimateHashImp2(0, sumTable, hashlib.sha224)\ndel sumTable",
  594. "execution_count": 24,
  595. "outputs": [
  596. {
  597. "name": "stdout",
  598. "output_type": "stream",
  599. "text": "Temps d'exécution 16.078969347989187\n"
  600. }
  601. ]
  602. },
  603. {
  604. "metadata": {
  605. "trusted": false
  606. },
  607. "cell_type": "code",
  608. "source": "sumTable=bytearray(78000000)\nestimateHashImp2(0, sumTable, hashlib.sha256)\ndel sumTable",
  609. "execution_count": 17,
  610. "outputs": [
  611. {
  612. "name": "stdout",
  613. "output_type": "stream",
  614. "text": "Temps d'exécution 16.72676704498008\n"
  615. },
  616. {
  617. "data": {
  618. "text/plain": "6698133"
  619. },
  620. "execution_count": 17,
  621. "metadata": {},
  622. "output_type": "execute_result"
  623. }
  624. ]
  625. },
  626. {
  627. "metadata": {
  628. "trusted": false
  629. },
  630. "cell_type": "code",
  631. "source": "sumTable=bytearray(78000000)\nestimateHashImp2(0, sumTable, hashlib.sha384)\ndel sumTable",
  632. "execution_count": 18,
  633. "outputs": [
  634. {
  635. "name": "stdout",
  636. "output_type": "stream",
  637. "text": "Temps d'exécution 18.951399962999858\n"
  638. },
  639. {
  640. "data": {
  641. "text/plain": "6697368"
  642. },
  643. "execution_count": 18,
  644. "metadata": {},
  645. "output_type": "execute_result"
  646. }
  647. ]
  648. },
  649. {
  650. "metadata": {
  651. "trusted": false
  652. },
  653. "cell_type": "code",
  654. "source": "sumTable=bytearray(78000000)\nestimateHashImp2(0, sumTable, hashlib.sha512)\ndel sumTable",
  655. "execution_count": 22,
  656. "outputs": [
  657. {
  658. "name": "stdout",
  659. "output_type": "stream",
  660. "text": "Temps d'exécution 20.012935240054503\n"
  661. },
  662. {
  663. "data": {
  664. "text/plain": "6698144"
  665. },
  666. "execution_count": 22,
  667. "metadata": {},
  668. "output_type": "execute_result"
  669. }
  670. ]
  671. },
  672. {
  673. "metadata": {},
  674. "cell_type": "markdown",
  675. "source": "><p style=\"text-align: justify;\"><font color=#206da1>Au premier abord, le hashing md5 semble retourner un résultat avec le moins de collisions, on regarde donc son erreur pour la journée. Comme le hashing avec sha1, l'erreur relative est très élevée. Un changement d'algorithme de hashing ne semble donc pas utile.</font></p>"
  676. },
  677. {
  678. "metadata": {
  679. "collapsed": true,
  680. "trusted": false
  681. },
  682. "cell_type": "code",
  683. "source": "def estimateAllHashImp2Md5():\n sumTable=bytearray(78000000)\n for i in range(24):\n estimateHashImp2(i, sumTable, hashlib.md5)\n print(sum(sumTable))\n return sum(sumTable)",
  684. "execution_count": 25,
  685. "outputs": []
  686. },
  687. {
  688. "metadata": {},
  689. "cell_type": "markdown",
  690. "source": "><p style=\"text-align: justify;\"><font color=#206da1></font></p>"
  691. },
  692. {
  693. "metadata": {},
  694. "cell_type": "markdown",
  695. "source": "><p style=\"text-align: justify;\"><font color=#206da1>Cependant, en analysant les fichiers sur un jour, le résultat donné est presqu'identique que celui obtenu avec l'algorithme sha1. Il est donc inutile de changer l'algorithme.</font></p>"
  696. },
  697. {
  698. "metadata": {
  699. "scrolled": true,
  700. "trusted": false
  701. },
  702. "cell_type": "code",
  703. "source": "estimateAllHashImp2Md5()",
  704. "execution_count": null,
  705. "outputs": [
  706. {
  707. "name": "stdout",
  708. "output_type": "stream",
  709. "text": "Temps d'exécution 13.92910977290012\nTemps d'exécution 13.704207394970581\nTemps d'exécution 13.909543638932519\nTemps d'exécution 14.332428200053982\nTemps d'exécution 13.19977273303084\nTemps d'exécution 13.257526044966653\nTemps d'exécution 14.093512048013508\nTemps d'exécution 13.751186621957459\nTemps d'exécution 14.381871724966913\nTemps d'exécution 15.585227194940671\nTemps d'exécution 15.158733748015948\nTemps d'exécution 16.021849368000403\nTemps d'exécution 16.873342160950415\nTemps d'exécution 16.929027911974117\nTemps d'exécution 16.806463406071998\nTemps d'exécution 16.796897558961064\nTemps d'exécution 16.67847050493583\nTemps d'exécution 16.575538872973993\nTemps d'exécution 16.237389824935235\nTemps d'exécution 15.724835539935157\nTemps d'exécution 14.725747241987847\n50088246\n"
  710. },
  711. {
  712. "data": {
  713. "text/plain": "50088246"
  714. },
  715. "execution_count": 27,
  716. "metadata": {},
  717. "output_type": "execute_result"
  718. }
  719. ]
  720. },
  721. {
  722. "metadata": {
  723. "collapsed": true
  724. },
  725. "cell_type": "markdown",
  726. "source": "<a id='3.3'></a>\n## Partition des noms de page"
  727. },
  728. {
  729. "metadata": {},
  730. "cell_type": "markdown",
  731. "source": "><p style=\"text-align: justify;\"><font color=#206da1>Diviser pour mieux régner, j'ai eu l'idée de partitionner les noms de pages en fonction de leur première lettre. Ainsi, il y aurait moins de collisions étant donnés deux bytearrays différents. <br/>\nOn commence par une analyse des cardinaux des partitions en fonction de la lettre initiale</font></p>"
  732. },
  733. {
  734. "metadata": {
  735. "collapsed": true,
  736. "trusted": false
  737. },
  738. "cell_type": "code",
  739. "source": "def analyse(fileNumber):\n initials={}\n prefix = \"pagecounts-20150501-\"\n fname = prefix + \"{:02}0000\".format(fileNumber)\n !gunzip \"$fname\".gz\n date0=time.perf_counter()\n with open(fname) as file:\n for line in file:\n datum=line.rsplit(None, 2)[0]\n try:\n initials[datum[0]]+=1\n except:\n initials[datum[0]]=1\n date1=time.perf_counter()\n !gzip \"$fname\"\n print(\"Temps d'exécution\", date1-date0)\n return initials",
  740. "execution_count": 2,
  741. "outputs": []
  742. },
  743. {
  744. "metadata": {
  745. "collapsed": true,
  746. "trusted": false
  747. },
  748. "cell_type": "code",
  749. "source": "def analyse(fileNumber, initials):\n prefix = \"pagecounts-20150501-\"\n fname = prefix + \"{:02}0000\".format(fileNumber)\n !gunzip \"$fname\".gz\n date0=time.perf_counter()\n with open(fname) as file:\n for line in file:\n datum=line.rsplit(None, 2)[0]\n try:\n initials[datum[0]]+=1\n except:\n initials[datum[0]]=1\n date1=time.perf_counter()\n !gzip \"$fname\"\n print(\"Temps d'exécution\", date1-date0)\n return initials",
  750. "execution_count": 2,
  751. "outputs": []
  752. },
  753. {
  754. "metadata": {
  755. "collapsed": true,
  756. "trusted": false
  757. },
  758. "cell_type": "code",
  759. "source": "dict={}\nfor i in range(24):\n analyse(i, dict)",
  760. "execution_count": 3,
  761. "outputs": [
  762. {
  763. "name": "stdout",
  764. "output_type": "stream",
  765. "text": "Temps d'exécution 5.51520077988971\nTemps d'exécution 4.608745029894635\nTemps d'exécution 4.454333508969285\nTemps d'exécution 4.816401167074218\nTemps d'exécution 4.171689521986991\nTemps d'exécution 4.262707054964267\nTemps d'exécution 4.590054841944948\nTemps d'exécution 4.526076194946654\nTemps d'exécution 4.727772757061757\nTemps d'exécution 4.994065684033558\nTemps d'exécution 4.924143532989547\nTemps d'exécution 5.094968648976646\nTemps d'exécution 5.091031903051771\nTemps d'exécution 5.318934308947064\nTemps d'exécution 5.303141370997764\nTemps d'exécution 6.904400969971903\nTemps d'exécution 6.826676043099724\nTemps d'exécution 6.822298737009987\nTemps d'exécution 6.810457425075583\nTemps d'exécution 6.728337732958607\nTemps d'exécution 6.820183641044423\nTemps d'exécution 5.195279472973198\nTemps d'exécution 5.072518615983427\nTemps d'exécution 4.759207720984705\n"
  766. }
  767. ]
  768. },
  769. {
  770. "metadata": {},
  771. "cell_type": "markdown",
  772. "source": "><p style=\"text-align: justify;\"><font color=#206da1>En observant la répartition, j'ai décidé de regrouper les lettres minuscules : a, b, c, d, e, f. Pour qu'on ait deux sous-ensembles équilibrés</font></p>"
  773. },
  774. {
  775. "metadata": {
  776. "scrolled": true,
  777. "trusted": false
  778. },
  779. "cell_type": "code",
  780. "source": "dict",
  781. "execution_count": 4,
  782. "outputs": [
  783. {
  784. "data": {
  785. "text/plain": "{'A': 1,\n 'C': 15,\n 'D': 3243,\n 'E': 3229,\n 'F': 46,\n 'H': 1,\n 'I': 380,\n 'J': 1,\n 'P': 2,\n 'S': 1273,\n 'T': 3,\n 'U': 203,\n 'a': 2308943,\n 'b': 1245584,\n 'c': 11954348,\n 'd': 11558332,\n 'e': 75515412,\n 'f': 12980718,\n 'g': 359986,\n 'h': 2830308,\n 'i': 7283747,\n 'j': 8720761,\n 'k': 1926000,\n 'l': 783453,\n 'm': 1327014,\n 'n': 4254949,\n 'o': 171754,\n 'p': 9255532,\n 'q': 27118,\n 'r': 9661148,\n 's': 4736160,\n 't': 2974611,\n 'u': 1148248,\n 'v': 1336751,\n 'w': 2345171,\n 'x': 24091,\n 'y': 56463,\n 'z': 11533238}"
  786. },
  787. "execution_count": 4,
  788. "metadata": {},
  789. "output_type": "execute_result"
  790. }
  791. ]
  792. },
  793. {
  794. "metadata": {
  795. "collapsed": true,
  796. "trusted": false
  797. },
  798. "cell_type": "code",
  799. "source": "def estimateHashImp3(fileNumber, table1, table2):\n prefix = \"pagecounts-20150501-\"\n fname = prefix + \"{:02}0000\".format(fileNumber)\n !gunzip \"$fname\".gz\n date0=time.perf_counter()\n with open(fname) as file:\n for line in file:\n datum=line.rsplit(None, 2)[0] \n if datum[0] in ['a','b','c','d','e','f']:\n table1[int(hashlib.sha1(datum.encode(\"UTF-8\")).hexdigest(), 16)%78000000]=1\n else:\n table2[int(hashlib.sha1(datum.encode(\"UTF-8\")).hexdigest(), 16)%78000000]=1\n !gzip \"$fname\"\n date1=time.perf_counter()\n print(\"Temps d'exécution\", date1-date0)\n ret=sum(table1)+sum(table2)\n print(\"Pages distinctes\", ret)\n return ret",
  800. "execution_count": 2,
  801. "outputs": []
  802. },
  803. {
  804. "metadata": {
  805. "collapsed": true,
  806. "trusted": false
  807. },
  808. "cell_type": "code",
  809. "source": "def estimateAllHashImp3(sumTable1, sumTable2):\n for i in range(24):\n estimateHashImp3(i, sumTable1, sumTable2)\n ret=sum(sumTable1)+sum(sumTable2)\n print(\"Pages distinctes\", ret)\n return ret",
  810. "execution_count": 3,
  811. "outputs": []
  812. },
  813. {
  814. "metadata": {},
  815. "cell_type": "markdown",
  816. "source": "><p style=\"text-align: justify;\"><font color=#206da1>Le résultat de cette méthode n'est pas très satisfaisant, car elle comporte plus d'opérations sans pour autant donner une meilleure performance comparée à la méthode simple d'augmentation de taille.<br/>\nOn peut quand même remarquer que la partition est assez judicieuse, en effet, les deux bytearray comporte le même ordre de pages distinctes.</font></p>"
  817. },
  818. {
  819. "metadata": {
  820. "scrolled": true,
  821. "trusted": false
  822. },
  823. "cell_type": "code",
  824. "source": "sumTable1=bytearray(78000000)\nsumTable2=bytearray(78000000)\nestimateAllHashImp3(sumTable1, sumTable2)",
  825. "execution_count": 4,
  826. "outputs": [
  827. {
  828. "name": "stdout",
  829. "output_type": "stream",
  830. "text": "Temps d'exécution 33.558185070054606\nPages distinctes 6836252\nTemps d'exécution 33.434226211044006\nPages distinctes 11460341\nTemps d'exécution 33.13811133801937\nPages distinctes 15496419\nTemps d'exécution 34.67108123691287\nPages distinctes 19321755\nTemps d'exécution 31.53040120995138\nPages distinctes 22427676\nTemps d'exécution 32.34175356396008\nPages distinctes 25427623\nTemps d'exécution 34.76316177099943\nPages distinctes 28436904\nTemps d'exécution 33.63160036795307\nPages distinctes 31135809\nTemps d'exécution 34.769890398019925\nPages distinctes 33760178\nTemps d'exécution 37.63445752195548\nPages distinctes 36424314\nTemps d'exécution 36.295785618014634\nPages distinctes 38763287\nTemps d'exécution 37.62453299900517\nPages distinctes 41058108\nTemps d'exécution 36.95849497895688\nPages distinctes 43175875\nTemps d'exécution 38.63739379995968\nPages distinctes 45301995\nTemps d'exécution 38.25581490097102\nPages distinctes 47272909\nTemps d'exécution 40.134742108988576\nPages distinctes 49228306\nTemps d'exécution 40.00636875501368\nPages distinctes 51141611\nTemps d'exécution 39.99134923401289\nPages distinctes 52972704\nTemps d'exécution 39.69300481805112\nPages distinctes 54748446\nTemps d'exécution 39.381327389972284\nPages distinctes 56452677\nTemps d'exécution 39.52118187700398\nPages distinctes 58117297\nTemps d'exécution 38.11275185702834\nPages distinctes 59675746\nTemps d'exécution 37.81010903790593\nPages distinctes 61167165\nTemps d'exécution 35.347362112952396\nPages distinctes 62565052\nPages distinctes 62565052\n"
  831. },
  832. {
  833. "data": {
  834. "text/plain": "62565052"
  835. },
  836. "execution_count": 4,
  837. "metadata": {},
  838. "output_type": "execute_result"
  839. }
  840. ]
  841. },
  842. {
  843. "metadata": {
  844. "trusted": false
  845. },
  846. "cell_type": "code",
  847. "source": "sum(sumTable1)",
  848. "execution_count": 5,
  849. "outputs": [
  850. {
  851. "data": {
  852. "text/plain": "33611169"
  853. },
  854. "execution_count": 5,
  855. "metadata": {},
  856. "output_type": "execute_result"
  857. }
  858. ]
  859. },
  860. {
  861. "metadata": {
  862. "trusted": false
  863. },
  864. "cell_type": "code",
  865. "source": "sum(sumTable2)",
  866. "execution_count": 6,
  867. "outputs": [
  868. {
  869. "data": {
  870. "text/plain": "28953883"
  871. },
  872. "execution_count": 6,
  873. "metadata": {},
  874. "output_type": "execute_result"
  875. }
  876. ]
  877. },
  878. {
  879. "metadata": {},
  880. "cell_type": "markdown",
  881. "source": "<a id='3.4'></a>\n## Gestion explicite de collision"
  882. },
  883. {
  884. "metadata": {},
  885. "cell_type": "markdown",
  886. "source": "><p style=\"text-align: justify;\"><font color=#206da1>Il reste encore la méthode de gestion des collisions. Pour parvenir à cette gestion, j'ai décidé d'utiliser un deuxième bytearray pour stocker la longueur du nom de la page, ainsi lorsque deux pages ont le même indice, on peut les distinguer grâce à leur longueur.</font></p>"
  887. },
  888. {
  889. "metadata": {},
  890. "cell_type": "markdown",
  891. "source": "<a id='3.4.1'></a>\n### Une collision"
  892. },
  893. {
  894. "metadata": {
  895. "collapsed": true,
  896. "trusted": false
  897. },
  898. "cell_type": "code",
  899. "source": "def estimateHashImp4(fileNumber, countTable, collisionTable):\n prefix = \"pagecounts-20150501-\"\n fname = prefix + \"{:02}0000\".format(fileNumber)\n !gunzip \"$fname\".gz\n date0=time.perf_counter()\n with open(fname) as file:\n for line in file:\n datum=line.rsplit(None, 2)[0]\n index=int(hashlib.sha1(datum.encode(\"UTF-8\")).hexdigest(), 16)%78000000\n collisionValue=len(datum)%255 if (len(datum)%255 != 0 or len(datum)%255 != 1) else 2\n if countTable[index]==0:\n countTable[index]=1\n collisionTable[index]=collisionValue\n elif collisionTable[index]==1:\n collisionTable[index]=1\n elif collisionTable[index] != collisionValue:\n countTable[index]+=1\n collisionTable[index]=1\n !gzip \"$fname\"\n date1=time.perf_counter()\n print(\"Temps d'exécution\", date1-date0)\n ret=sum(countTable)\n print(\"Pages distinctes\", ret)\n return ret",
  900. "execution_count": 2,
  901. "outputs": []
  902. },
  903. {
  904. "metadata": {
  905. "collapsed": true,
  906. "trusted": false
  907. },
  908. "cell_type": "code",
  909. "source": "def estimateAllHashImp4(countTable, collisionTable):\n for i in range(24):\n estimateHashImp4(i, countTable, collisionTable)\n return",
  910. "execution_count": 3,
  911. "outputs": []
  912. },
  913. {
  914. "metadata": {},
  915. "cell_type": "markdown",
  916. "source": "><p style=\"text-align: justify;\"><font color=#206da1>L'utilisation d'un bytearray de taille 78 000 000 en plus pour la gestion d'une collision, nous a permis de distinguer 71 220 169 de pages distinctes. Cela représente une erreur relative de 0,09.<br/>\nCette méthode est donc plus efficace que celle de l'augmentation sans traitement vue précédemment tout en utilisant la même quantité de ressource.</font></p>"
  917. },
  918. {
  919. "metadata": {
  920. "scrolled": true,
  921. "trusted": false
  922. },
  923. "cell_type": "code",
  924. "source": "table1=bytearray(78000000)\ntable2=bytearray(78000000)\nestimateAllHashImp4(table1, table2)",
  925. "execution_count": 4,
  926. "outputs": [
  927. {
  928. "name": "stdout",
  929. "output_type": "stream",
  930. "text": "Temps d'exécution 35.335078625999984\nPages distinctes 6988828\nTemps d'exécution 34.434815216000004\nPages distinctes 11870495\nTemps d'exécution 34.53602611499997\nPages distinctes 16223602\nTemps d'exécution 35.78324474300001\nPages distinctes 20424127\nTemps d'exécution 32.98364657400003\nPages distinctes 23885220\nTemps d'exécution 33.81640366500005\nPages distinctes 27265860\nTemps d'exécution 36.961570116000075\nPages distinctes 30686911\nTemps d'exécution 35.1773089400001\nPages distinctes 33787590\nTemps d'exécution 36.40998994200004\nPages distinctes 36827610\nTemps d'exécution 39.94247989999997\nPages distinctes 39936498\nTemps d'exécution 38.173293994000005\nPages distinctes 42683541\nTemps d'exécution 40.24919089299999\nPages distinctes 45393594\nTemps d'exécution 39.49537865699995\nPages distinctes 47905089\nTemps d'exécution 41.40099283999996\nPages distinctes 50433156\nTemps d'exécution 40.70741622700007\nPages distinctes 52787412\nTemps d'exécution 42.760693403999994\nPages distinctes 55129135\nTemps d'exécution 42.89222517099995\nPages distinctes 57427814\nTemps d'exécution 42.625398083000164\nPages distinctes 59633617\nTemps d'exécution 42.2230824899998\nPages distinctes 61776086\nTemps d'exécution 42.19438768200007\nPages distinctes 63836028\nTemps d'exécution 41.912750096999844\nPages distinctes 65847222\nTemps d'exécution 41.00000461200011\nPages distinctes 67733704\nTemps d'exécution 39.88072333299988\nPages distinctes 69535021\nTemps d'exécution 36.99213183500001\nPages distinctes 71220169\n"
  931. }
  932. ]
  933. },
  934. {
  935. "metadata": {},
  936. "cell_type": "markdown",
  937. "source": "<a id='3.4.2'></a>\n### Deux collisions"
  938. },
  939. {
  940. "metadata": {},
  941. "cell_type": "markdown",
  942. "source": "><p style=\"text-align: justify;\"><font color=#206da1>La mémoire vive disponible de notre machine virtuelle nous autorise à avoir deux tables gérant les collisions. Je réimplémente donc la même méthode mais cette fois-ci avec une table en plus.</font></p>"
  943. },
  944. {
  945. "metadata": {
  946. "collapsed": true,
  947. "trusted": false
  948. },
  949. "cell_type": "code",
  950. "source": "def estimateHashImp5(fileNumber, countTable, collisionTable1, collisionTable2):\n prefix = \"pagecounts-20150501-\"\n fname = prefix + \"{:02}0000\".format(fileNumber)\n !gunzip \"$fname\".gz\n date0=time.perf_counter()\n with open(fname) as file:\n for line in file:\n datum=line.rsplit(None, 2)[0]\n index=int(hashlib.sha1(datum.encode(\"UTF-8\")).hexdigest(), 16)%78000000\n collisionValue=len(datum)%255 if (len(datum)%255 != 0 or len(datum)%255 != 1) else 2\n if countTable[index]==0:\n countTable[index]=1\n collisionTable1[index]=collisionValue\n elif collisionTable2[index]==1:\n collisionTable2[index]=1\n elif collisionTable1[index] != collisionValue:\n if collisionTable2[index] == 0:\n countTable[index]+=1\n collisionTable2[index]=collisionValue\n elif collisionTable2[index] != collisionValue:\n countTable[index]+=1\n collisionTable2[index]=1\n !gzip \"$fname\"\n date1=time.perf_counter()\n print(\"Temps d'exécution\", date1-date0)\n ret=sum(countTable)\n print(\"Pages distinctes\", ret)\n return ret",
  951. "execution_count": 2,
  952. "outputs": []
  953. },
  954. {
  955. "metadata": {
  956. "collapsed": true,
  957. "trusted": false
  958. },
  959. "cell_type": "code",
  960. "source": "def estimateAllHashImp5(countTable, collisionTable1, collisionTable2):\n for i in range(24):\n estimateHashImp4(i, countTable, collisionTable1, collisionTable2)\n return",
  961. "execution_count": 3,
  962. "outputs": []
  963. },
  964. {
  965. "metadata": {},
  966. "cell_type": "markdown",
  967. "source": "><p style=\"text-align: justify;\"><font color=#206da1>Avec deux tables de gestion de collisions, on obtient 77 735 280 pages distinctes. Son taux d'erreur est donc de 0,003. Cela est assez satisfaisant.</font></p>"
  968. },
  969. {
  970. "metadata": {
  971. "scrolled": true,
  972. "trusted": false
  973. },
  974. "cell_type": "code",
  975. "source": "table1=bytearray(78000000)\ntable2=bytearray(78000000)\ntable3=bytearray(78000000)\nestimateAllHashImp5(table1, table2, table3)",
  976. "execution_count": 4,
  977. "outputs": [
  978. {
  979. "name": "stdout",
  980. "output_type": "stream",
  981. "text": "Temps d'exécution 35.01131310407072\nPages distinctes 6997226\nTemps d'exécution 34.926083894097246\nPages distinctes 11911437\nTemps d'exécution 34.887826227000915\nPages distinctes 16325125\nTemps d'exécution 36.56159837299492\nPages distinctes 20619998\nTemps d'exécution 33.659675003029406\nPages distinctes 24190588\nTemps d'exécution 34.09264515596442\nPages distinctes 27709914\nTemps d'exécution 36.917825931101106\nPages distinctes 31306935\nTemps d'exécution 35.65157296299003\nPages distinctes 34600101\nTemps d'exécution 37.18374283297453\nPages distinctes 37862834\nTemps d'exécution 40.06027609901503\nPages distinctes 41235357\nTemps d'exécution 38.9528606539825\nPages distinctes 44247797\nTemps d'exécution 40.732968761003576\nPages distinctes 47250492\nTemps d'exécution 40.38018654007465\nPages distinctes 50062702\nTemps d'exécution 41.55720594804734\nPages distinctes 52923849\nTemps d'exécution 41.388747446006164\nPages distinctes 55614166\nTemps d'exécution 43.499829718028195\nPages distinctes 58317840\nTemps d'exécution 43.12701625900809\nPages distinctes 61001780\nTemps d'exécution 43.26149310194887\nPages distinctes 63601981\nTemps d'exécution 42.86026588198729\nPages distinctes 66152722\nTemps d'exécution 42.43018832500093\nPages distinctes 68632654\nTemps d'exécution 42.44868988695089\nPages distinctes 71078422\nTemps d'exécution 41.61522384500131\nPages distinctes 73395043\nTemps d'exécution 40.2704160149442\nPages distinctes 75627358\nTemps d'exécution 38.1069441169966\nPages distinctes 77735280\n"
  982. }
  983. ]
  984. }
  985. ],
  986. "metadata": {
  987. "kernelspec": {
  988. "name": "python3",
  989. "display_name": "Python 3",
  990. "language": "python"
  991. },
  992. "language_info": {
  993. "name": "python",
  994. "version": "3.6.1",
  995. "mimetype": "text/x-python",
  996. "codemirror_mode": {
  997. "name": "ipython",
  998. "version": 3
  999. },
  1000. "pygments_lexer": "ipython3",
  1001. "nbconvert_exporter": "python",
  1002. "file_extension": ".py"
  1003. },
  1004. "gist_id": "af7c4214944f3631d95ab85317dee272"
  1005. },
  1006. "nbformat": 4,
  1007. "nbformat_minor": 2
  1008. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!