{"cells":[{"metadata":{"id":"ClKgmfAOzM04"},"cell_type":"markdown","source":"<font color=\"orange\" size=\"5\"><b>📗 Recherche textuelle : mesure du temps avec la méthode naïve </b></font>"},{"metadata":{"id":"ztFaNs4GdJ2J"},"cell_type":"markdown","source":"On rappelle :"},{"metadata":{"id":"bbKtUf66zLlB","trusted":true},"cell_type":"code","source":"def recherche_naive_bool(texte, motif):\n    '''\n    renvoie un booléen indiquant la présence ou non de\n    la chaîne motif dans la chaîne texte.\n    '''\n    trouve = False\n    i = 0\n    while i <= len(texte) - len(motif) and not trouve:\n        k = 0\n        while k < len(motif) and texte[i + k] == motif[k]:\n            k = k + 1\n        if k == len(motif):\n            trouve = True\n        i = i + 1\n\n    return trouve","execution_count":null,"outputs":[]},{"metadata":{"id":"s1ePglg5zLlC","trusted":true},"cell_type":"code","source":"texte = 'CAATGTCTGCACCAAGAC'\nmotif = 'CAAG'\nassert(recherche_naive_bool(texte, motif) == True)\nassert(recherche_naive_bool(texte, 'BB') == False)","execution_count":null,"outputs":[]},{"metadata":{"id":"KRk5gaXRzLlD"},"cell_type":"markdown","source":"#### Mesure du temps de calcul\n\nOn va reprendre ici le texte du roman *Le rouge et le noir* utilisé dans le cours, et comparer les temps de recherche entre la fonction intégrée <code>find</code> de Python et notre fonction <code>recherche_naive_bool</code>. "},{"metadata":{"id":"6KxptG2F3kPe","trusted":true},"cell_type":"code","source":"fichier = open('pg798.txt', 'r', encoding = 'utf-8')\nstendhal = fichier.read()\nfichier.close()","execution_count":null,"outputs":[]},{"metadata":{"id":"eNsIl8Z7zM1H"},"cell_type":"markdown","source":"Pour mesurer le temps d'exécution d'un programme, on peut utiliser la fonction <code>timeit()</code> du module *timeit*. \n\nNous allons chercher :  \"Mme de Rênal fut fidèle à sa promesse\" dans la variable `stendhal`. "},{"metadata":{"id":"rrQhAss4psTT","colab":{"base_uri":"https://localhost:8080/"},"outputId":"c5cad5df-b77d-473a-cbdc-4dbef015b528","trusted":true},"cell_type":"code","source":"from timeit import timeit\n\ndef recherche_find(livre, texte):\n    return livre.find(texte)\n\ndef recherche_naive(livre, texte):\n    return recherche_naive_bool(livre, texte )\n\nlivre = stendhal\ntexte = 'Mme de Rênal fut fidèle à sa promesse'\n\ntemps_find = timeit(\"recherche_find(livre, texte)\", number=5, globals=globals())\ntemps_naif = timeit(\"recherche_naive(livre, texte)\", number=5, globals=globals())\nprint(\"Temps en utilisant find : \",temps_find)\nprint(\"Temps en utilisant l'algorithme naif : \",temps_naif)\n","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"#### Comparaison du temps d'exécution en fonction de la longueur du motif cherché avec la recherche naïve"},{"metadata":{"trusted":true},"cell_type":"code","source":"livre = stendhal\ntexte_1 = \"Mme de Rênal ne connaissait pas encore l'intelligence artificielle\"\ntexte_2 = \"dico\"\ntemps_1 = timeit(\"recherche_naive(livre, texte_1)\", number=5, globals=globals())\ntemps_2 = timeit(\"recherche_naive(livre, texte_2)\", number=5, globals=globals())\nprint(\"Temps pour un texte long : \", temps_1)\nprint(\"Temps pour un texte court : \", temps_2)","execution_count":null,"outputs":[]},{"metadata":{},"cell_type":"markdown","source":"#### Comparaison du temps d'exécution en fonction de la longueur du motif cherché avec la méthode find"},{"metadata":{"trusted":true},"cell_type":"code","source":"livre = stendhal\ntexte_1 = \"Mme de Rênal ne connaissait pas encore l'intelligence artificielle\"\ntexte_2 = \"dico\"\ntemps_1 = timeit(\"recherche_find(livre, texte_1)\", number=5, globals=globals())\ntemps_2 = timeit(\"recherche_find(livre, texte_2)\", number=5, globals=globals())\nprint(\"Temps pour un texte long : \", temps_1)\nprint(\"Temps pour un texte court : \", temps_2)","execution_count":null,"outputs":[]},{"metadata":{"id":"VZnU9A29zM1I"},"cell_type":"markdown","source":"#### 😭 Et dans le pire des cas ?\n\nConstruisons un texte (très long ! un million de caractères - tous identiques- par exemple) et un motif (assez long lui aussi ! Mettons mille caractères - les mêmes plus un caractère différent à la fin-) correspondant au pire des cas, et comparons les deux temps de calcul.  \nVous verrez c'est assez long... "},{"metadata":{"colab":{"base_uri":"https://localhost:8080/"},"id":"Prh35gLa6HAQ","outputId":"4e362fc5-37e2-4e75-c1bd-92b5bd7234c8","trusted":true},"cell_type":"code","source":"texte_pire = 'A'*10**6\nmotif_pire = 'A'*10*3+'B'\ntemps_find = timeit(\"recherche_find(texte_pire, motif_pire)\", number=2, globals=globals())\ntemps_naif = timeit(\"recherche_naive(texte_pire, motif_pire)\", number=2, globals=globals())\nprint(\"Temps en utilisant find : \",temps_find)\nprint(\"Temps en utilisant l'algorithme naif : \",temps_naif)\n","execution_count":null,"outputs":[]}],"metadata":{"kernelspec":{"display_name":"Python 3","language":"python","name":"python3"},"language_info":{"codemirror_mode":{"name":"ipython","version":3},"file_extension":".py","mimetype":"text/x-python","name":"python","nbconvert_exporter":"python","pygments_lexer":"ipython3","version":"3.7.6"},"colab":{"name":"BoyerMoore2_corrigé.ipynb","provenance":[],"collapsed_sections":[]}},"nbformat":4,"nbformat_minor":2}