{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# 1A.soft - Calcul num\u00e9rique et Cython - correction"]}, {"cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [{"data": {"text/html": ["
run previous cell, wait for 2 seconds
\n", ""], "text/plain": [""]}, "execution_count": 2, "metadata": {}, "output_type": "execute_result"}], "source": ["from jyquickhelper import add_notebook_menu\n", "add_notebook_menu()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## Exercice : python/C appliqu\u00e9 \u00e0 une distance d'\u00e9dition\n", "\n", "On reprend la fonction donn\u00e9e dans l'\u00e9nonc\u00e9."]}, {"cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["188 \u00b5s \u00b1 28.6 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 10000 loops each)\n"]}], "source": ["def distance_edition(mot1, mot2):\n", " dist = { (-1,-1): 0 }\n", " for i,c in enumerate(mot1) :\n", " dist[i,-1] = dist[i-1,-1] + 1\n", " dist[-1,i] = dist[-1,i-1] + 1\n", " for j,d in enumerate(mot2) :\n", " opt = [ ]\n", " if (i-1,j) in dist : \n", " x = dist[i-1,j] + 1\n", " opt.append(x)\n", " if (i,j-1) in dist : \n", " x = dist[i,j-1] + 1\n", " opt.append(x)\n", " if (i-1,j-1) in dist :\n", " x = dist[i-1,j-1] + (1 if c != d else 0)\n", " opt.append(x)\n", " dist[i,j] = min(opt)\n", " return dist[len(mot1)-1,len(mot2)-1]\n", "\n", "%timeit distance_edition(\"idstzance\",\"distances\")"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## solution avec notebook\n", "\n", "Les pr\u00e9liminaires :"]}, {"cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [], "source": ["%load_ext cython"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Puis :"]}, {"cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [{"data": {"text/html": ["\n", "\n", "\n", "\n", " \n", " Cython: _cython_magic_f072b3f10e4cb6a87b39cd12da494e91.pyx\n", " \n", "\n", "\n", "

Generated by Cython 0.29.21

\n", "

\n", " Yellow lines hint at Python interaction.
\n", " Click on a line that starts with a \"+\" to see the C code that Cython generated for it.\n", "

\n", "
 01: cimport cython
\n", "
 02: 
\n", "
+03: def cidistance_edition(str mot1, str mot2):
\n", "
/* Python wrapper */\n", "static PyObject *__pyx_pw_46_cython_magic_f072b3f10e4cb6a87b39cd12da494e91_1cidistance_edition(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds); /*proto*/\n", "static PyMethodDef __pyx_mdef_46_cython_magic_f072b3f10e4cb6a87b39cd12da494e91_1cidistance_edition = {\"cidistance_edition\", (PyCFunction)(void*)(PyCFunctionWithKeywords)__pyx_pw_46_cython_magic_f072b3f10e4cb6a87b39cd12da494e91_1cidistance_edition, METH_VARARGS|METH_KEYWORDS, 0};\n", "static PyObject *__pyx_pw_46_cython_magic_f072b3f10e4cb6a87b39cd12da494e91_1cidistance_edition(PyObject *__pyx_self, PyObject *__pyx_args, PyObject *__pyx_kwds) {\n", "  PyObject *__pyx_v_mot1 = 0;\n", "  PyObject *__pyx_v_mot2 = 0;\n", "  PyObject *__pyx_r = 0;\n", "  __Pyx_RefNannyDeclarations\n", "  __Pyx_RefNannySetupContext(\"cidistance_edition (wrapper)\", 0);\n", "  {\n", "    static PyObject **__pyx_pyargnames[] = {&__pyx_n_s_mot1,&__pyx_n_s_mot2,0};\n", "    PyObject* values[2] = {0,0};\n", "    if (unlikely(__pyx_kwds)) {\n", "      Py_ssize_t kw_args;\n", "      const Py_ssize_t pos_args = PyTuple_GET_SIZE(__pyx_args);\n", "      switch (pos_args) {\n", "        case  2: values[1] = PyTuple_GET_ITEM(__pyx_args, 1);\n", "        CYTHON_FALLTHROUGH;\n", "        case  1: values[0] = PyTuple_GET_ITEM(__pyx_args, 0);\n", "        CYTHON_FALLTHROUGH;\n", "        case  0: break;\n", "        default: goto __pyx_L5_argtuple_error;\n", "      }\n", "      kw_args = PyDict_Size(__pyx_kwds);\n", "      switch (pos_args) {\n", "        case  0:\n", "        if (likely((values[0] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_mot1)) != 0)) kw_args--;\n", "        else goto __pyx_L5_argtuple_error;\n", "        CYTHON_FALLTHROUGH;\n", "        case  1:\n", "        if (likely((values[1] = __Pyx_PyDict_GetItemStr(__pyx_kwds, __pyx_n_s_mot2)) != 0)) kw_args--;\n", "        else {\n", "          __Pyx_RaiseArgtupleInvalid(\"cidistance_edition\", 1, 2, 2, 1); __PYX_ERR(0, 3, __pyx_L3_error)\n", "        }\n", "      }\n", "      if (unlikely(kw_args > 0)) {\n", "        if (unlikely(__Pyx_ParseOptionalKeywords(__pyx_kwds, __pyx_pyargnames, 0, values, pos_args, \"cidistance_edition\") < 0)) __PYX_ERR(0, 3, __pyx_L3_error)\n", "      }\n", "    } else if (PyTuple_GET_SIZE(__pyx_args) != 2) {\n", "      goto __pyx_L5_argtuple_error;\n", "    } else {\n", "      values[0] = PyTuple_GET_ITEM(__pyx_args, 0);\n", "      values[1] = PyTuple_GET_ITEM(__pyx_args, 1);\n", "    }\n", "    __pyx_v_mot1 = ((PyObject*)values[0]);\n", "    __pyx_v_mot2 = ((PyObject*)values[1]);\n", "  }\n", "  goto __pyx_L4_argument_unpacking_done;\n", "  __pyx_L5_argtuple_error:;\n", "  __Pyx_RaiseArgtupleInvalid(\"cidistance_edition\", 1, 2, 2, PyTuple_GET_SIZE(__pyx_args)); __PYX_ERR(0, 3, __pyx_L3_error)\n", "  __pyx_L3_error:;\n", "  __Pyx_AddTraceback(\"_cython_magic_f072b3f10e4cb6a87b39cd12da494e91.cidistance_edition\", __pyx_clineno, __pyx_lineno, __pyx_filename);\n", "  __Pyx_RefNannyFinishContext();\n", "  return NULL;\n", "  __pyx_L4_argument_unpacking_done:;\n", "  if (unlikely(!__Pyx_ArgTypeTest(((PyObject *)__pyx_v_mot1), (&PyUnicode_Type), 1, \"mot1\", 1))) __PYX_ERR(0, 3, __pyx_L1_error)\n", "  if (unlikely(!__Pyx_ArgTypeTest(((PyObject *)__pyx_v_mot2), (&PyUnicode_Type), 1, \"mot2\", 1))) __PYX_ERR(0, 3, __pyx_L1_error)\n", "  __pyx_r = __pyx_pf_46_cython_magic_f072b3f10e4cb6a87b39cd12da494e91_cidistance_edition(__pyx_self, __pyx_v_mot1, __pyx_v_mot2);\n", "  int __pyx_lineno = 0;\n", "  const char *__pyx_filename = NULL;\n", "  int __pyx_clineno = 0;\n", "\n", "  /* function exit code */\n", "  goto __pyx_L0;\n", "  __pyx_L1_error:;\n", "  __pyx_r = NULL;\n", "  __pyx_L0:;\n", "  __Pyx_RefNannyFinishContext();\n", "  return __pyx_r;\n", "}\n", "\n", "static PyObject *__pyx_pf_46_cython_magic_f072b3f10e4cb6a87b39cd12da494e91_cidistance_edition(CYTHON_UNUSED PyObject *__pyx_self, PyObject *__pyx_v_mot1, PyObject *__pyx_v_mot2) {\n", "  int __pyx_v_dist[0x1F4][0x1F4];\n", "  int __pyx_v_cost;\n", "  int __pyx_v_c;\n", "  int __pyx_v_l1;\n", "  int __pyx_v_l2;\n", "  PyObject *__pyx_v_i = NULL;\n", "  PyObject *__pyx_v_j = NULL;\n", "  PyObject *__pyx_r = NULL;\n", "  __Pyx_RefNannyDeclarations\n", "  __Pyx_RefNannySetupContext(\"cidistance_edition\", 0);\n", "/* \u2026 */\n", "  /* function exit code */\n", "  __pyx_L1_error:;\n", "  __Pyx_XDECREF(__pyx_t_2);\n", "  __Pyx_XDECREF(__pyx_t_3);\n", "  __Pyx_XDECREF(__pyx_t_7);\n", "  __Pyx_XDECREF(__pyx_t_11);\n", "  __Pyx_XDECREF(__pyx_t_12);\n", "  __Pyx_AddTraceback(\"_cython_magic_f072b3f10e4cb6a87b39cd12da494e91.cidistance_edition\", __pyx_clineno, __pyx_lineno, __pyx_filename);\n", "  __pyx_r = NULL;\n", "  __pyx_L0:;\n", "  __Pyx_XDECREF(__pyx_v_i);\n", "  __Pyx_XDECREF(__pyx_v_j);\n", "  __Pyx_XGIVEREF(__pyx_r);\n", "  __Pyx_RefNannyFinishContext();\n", "  return __pyx_r;\n", "}\n", "/* \u2026 */\n", "  __pyx_tuple_ = PyTuple_Pack(9, __pyx_n_s_mot1, __pyx_n_s_mot2, __pyx_n_s_dist, __pyx_n_s_cost, __pyx_n_s_c, __pyx_n_s_l1, __pyx_n_s_l2, __pyx_n_s_i, __pyx_n_s_j); if (unlikely(!__pyx_tuple_)) __PYX_ERR(0, 3, __pyx_L1_error)\n", "  __Pyx_GOTREF(__pyx_tuple_);\n", "  __Pyx_GIVEREF(__pyx_tuple_);\n", "/* \u2026 */\n", "  __pyx_t_1 = PyCFunction_NewEx(&__pyx_mdef_46_cython_magic_f072b3f10e4cb6a87b39cd12da494e91_1cidistance_edition, NULL, __pyx_n_s_cython_magic_f072b3f10e4cb6a87b); if (unlikely(!__pyx_t_1)) __PYX_ERR(0, 3, __pyx_L1_error)\n", "  __Pyx_GOTREF(__pyx_t_1);\n", "  if (PyDict_SetItem(__pyx_d, __pyx_n_s_cidistance_edition, __pyx_t_1) < 0) __PYX_ERR(0, 3, __pyx_L1_error)\n", "  __Pyx_DECREF(__pyx_t_1); __pyx_t_1 = 0;\n", "
 04:     cdef int dist [500][500]
\n", "
 05:     cdef int cost, c
\n", "
+06:     cdef int l1 = len(mot1)
\n", "
  if (unlikely(__pyx_v_mot1 == Py_None)) {\n", "    PyErr_SetString(PyExc_TypeError, \"object of type 'NoneType' has no len()\");\n", "    __PYX_ERR(0, 6, __pyx_L1_error)\n", "  }\n", "  __pyx_t_1 = __Pyx_PyUnicode_GET_LENGTH(__pyx_v_mot1); if (unlikely(__pyx_t_1 == ((Py_ssize_t)-1))) __PYX_ERR(0, 6, __pyx_L1_error)\n", "  __pyx_v_l1 = __pyx_t_1;\n", "
+07:     cdef int l2 = len(mot2)
\n", "
  if (unlikely(__pyx_v_mot2 == Py_None)) {\n", "    PyErr_SetString(PyExc_TypeError, \"object of type 'NoneType' has no len()\");\n", "    __PYX_ERR(0, 7, __pyx_L1_error)\n", "  }\n", "  __pyx_t_1 = __Pyx_PyUnicode_GET_LENGTH(__pyx_v_mot2); if (unlikely(__pyx_t_1 == ((Py_ssize_t)-1))) __PYX_ERR(0, 7, __pyx_L1_error)\n", "  __pyx_v_l2 = __pyx_t_1;\n", "
 08: 
\n", "
+09:     dist[0][0] = 0
\n", "
  ((__pyx_v_dist[0])[0]) = 0;\n", "
+10:     for i in range(l1):
\n", "
  __pyx_t_2 = __Pyx_PyInt_From_int(__pyx_v_l1); if (unlikely(!__pyx_t_2)) __PYX_ERR(0, 10, __pyx_L1_error)\n", "  __Pyx_GOTREF(__pyx_t_2);\n", "  __pyx_t_3 = __Pyx_PyObject_CallOneArg(__pyx_builtin_range, __pyx_t_2); if (unlikely(!__pyx_t_3)) __PYX_ERR(0, 10, __pyx_L1_error)\n", "  __Pyx_GOTREF(__pyx_t_3);\n", "  __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;\n", "  if (likely(PyList_CheckExact(__pyx_t_3)) || PyTuple_CheckExact(__pyx_t_3)) {\n", "    __pyx_t_2 = __pyx_t_3; __Pyx_INCREF(__pyx_t_2); __pyx_t_1 = 0;\n", "    __pyx_t_4 = NULL;\n", "  } else {\n", "    __pyx_t_1 = -1; __pyx_t_2 = PyObject_GetIter(__pyx_t_3); if (unlikely(!__pyx_t_2)) __PYX_ERR(0, 10, __pyx_L1_error)\n", "    __Pyx_GOTREF(__pyx_t_2);\n", "    __pyx_t_4 = Py_TYPE(__pyx_t_2)->tp_iternext; if (unlikely(!__pyx_t_4)) __PYX_ERR(0, 10, __pyx_L1_error)\n", "  }\n", "  __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;\n", "  for (;;) {\n", "    if (likely(!__pyx_t_4)) {\n", "      if (likely(PyList_CheckExact(__pyx_t_2))) {\n", "        if (__pyx_t_1 >= PyList_GET_SIZE(__pyx_t_2)) break;\n", "        #if CYTHON_ASSUME_SAFE_MACROS && !CYTHON_AVOID_BORROWED_REFS\n", "        __pyx_t_3 = PyList_GET_ITEM(__pyx_t_2, __pyx_t_1); __Pyx_INCREF(__pyx_t_3); __pyx_t_1++; if (unlikely(0 < 0)) __PYX_ERR(0, 10, __pyx_L1_error)\n", "        #else\n", "        __pyx_t_3 = PySequence_ITEM(__pyx_t_2, __pyx_t_1); __pyx_t_1++; if (unlikely(!__pyx_t_3)) __PYX_ERR(0, 10, __pyx_L1_error)\n", "        __Pyx_GOTREF(__pyx_t_3);\n", "        #endif\n", "      } else {\n", "        if (__pyx_t_1 >= PyTuple_GET_SIZE(__pyx_t_2)) break;\n", "        #if CYTHON_ASSUME_SAFE_MACROS && !CYTHON_AVOID_BORROWED_REFS\n", "        __pyx_t_3 = PyTuple_GET_ITEM(__pyx_t_2, __pyx_t_1); __Pyx_INCREF(__pyx_t_3); __pyx_t_1++; if (unlikely(0 < 0)) __PYX_ERR(0, 10, __pyx_L1_error)\n", "        #else\n", "        __pyx_t_3 = PySequence_ITEM(__pyx_t_2, __pyx_t_1); __pyx_t_1++; if (unlikely(!__pyx_t_3)) __PYX_ERR(0, 10, __pyx_L1_error)\n", "        __Pyx_GOTREF(__pyx_t_3);\n", "        #endif\n", "      }\n", "    } else {\n", "      __pyx_t_3 = __pyx_t_4(__pyx_t_2);\n", "      if (unlikely(!__pyx_t_3)) {\n", "        PyObject* exc_type = PyErr_Occurred();\n", "        if (exc_type) {\n", "          if (likely(__Pyx_PyErr_GivenExceptionMatches(exc_type, PyExc_StopIteration))) PyErr_Clear();\n", "          else __PYX_ERR(0, 10, __pyx_L1_error)\n", "        }\n", "        break;\n", "      }\n", "      __Pyx_GOTREF(__pyx_t_3);\n", "    }\n", "    __Pyx_XDECREF_SET(__pyx_v_i, __pyx_t_3);\n", "    __pyx_t_3 = 0;\n", "/* \u2026 */\n", "  }\n", "  __Pyx_DECREF(__pyx_t_2); __pyx_t_2 = 0;\n", "
+11:         dist[i+1][0] = dist[i][0] + 1
\n", "
    __pyx_t_5 = __Pyx_PyIndex_AsSsize_t(__pyx_v_i); if (unlikely((__pyx_t_5 == (Py_ssize_t)-1) && PyErr_Occurred())) __PYX_ERR(0, 11, __pyx_L1_error)\n", "    __pyx_t_3 = __Pyx_PyInt_AddObjC(__pyx_v_i, __pyx_int_1, 1, 0, 0); if (unlikely(!__pyx_t_3)) __PYX_ERR(0, 11, __pyx_L1_error)\n", "    __Pyx_GOTREF(__pyx_t_3);\n", "    __pyx_t_6 = __Pyx_PyIndex_AsSsize_t(__pyx_t_3); if (unlikely((__pyx_t_6 == (Py_ssize_t)-1) && PyErr_Occurred())) __PYX_ERR(0, 11, __pyx_L1_error)\n", "    __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;\n", "    ((__pyx_v_dist[__pyx_t_6])[0]) = (((__pyx_v_dist[__pyx_t_5])[0]) + 1);\n", "
+12:         dist[0][i+1] = dist[0][i] + 1
\n", "
    __pyx_t_5 = __Pyx_PyIndex_AsSsize_t(__pyx_v_i); if (unlikely((__pyx_t_5 == (Py_ssize_t)-1) && PyErr_Occurred())) __PYX_ERR(0, 12, __pyx_L1_error)\n", "    __pyx_t_3 = __Pyx_PyInt_AddObjC(__pyx_v_i, __pyx_int_1, 1, 0, 0); if (unlikely(!__pyx_t_3)) __PYX_ERR(0, 12, __pyx_L1_error)\n", "    __Pyx_GOTREF(__pyx_t_3);\n", "    __pyx_t_6 = __Pyx_PyIndex_AsSsize_t(__pyx_t_3); if (unlikely((__pyx_t_6 == (Py_ssize_t)-1) && PyErr_Occurred())) __PYX_ERR(0, 12, __pyx_L1_error)\n", "    __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;\n", "    ((__pyx_v_dist[0])[__pyx_t_6]) = (((__pyx_v_dist[0])[__pyx_t_5]) + 1);\n", "
+13:         for j in range(l2):
\n", "
    __pyx_t_3 = __Pyx_PyInt_From_int(__pyx_v_l2); if (unlikely(!__pyx_t_3)) __PYX_ERR(0, 13, __pyx_L1_error)\n", "    __Pyx_GOTREF(__pyx_t_3);\n", "    __pyx_t_7 = __Pyx_PyObject_CallOneArg(__pyx_builtin_range, __pyx_t_3); if (unlikely(!__pyx_t_7)) __PYX_ERR(0, 13, __pyx_L1_error)\n", "    __Pyx_GOTREF(__pyx_t_7);\n", "    __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;\n", "    if (likely(PyList_CheckExact(__pyx_t_7)) || PyTuple_CheckExact(__pyx_t_7)) {\n", "      __pyx_t_3 = __pyx_t_7; __Pyx_INCREF(__pyx_t_3); __pyx_t_5 = 0;\n", "      __pyx_t_8 = NULL;\n", "    } else {\n", "      __pyx_t_5 = -1; __pyx_t_3 = PyObject_GetIter(__pyx_t_7); if (unlikely(!__pyx_t_3)) __PYX_ERR(0, 13, __pyx_L1_error)\n", "      __Pyx_GOTREF(__pyx_t_3);\n", "      __pyx_t_8 = Py_TYPE(__pyx_t_3)->tp_iternext; if (unlikely(!__pyx_t_8)) __PYX_ERR(0, 13, __pyx_L1_error)\n", "    }\n", "    __Pyx_DECREF(__pyx_t_7); __pyx_t_7 = 0;\n", "    for (;;) {\n", "      if (likely(!__pyx_t_8)) {\n", "        if (likely(PyList_CheckExact(__pyx_t_3))) {\n", "          if (__pyx_t_5 >= PyList_GET_SIZE(__pyx_t_3)) break;\n", "          #if CYTHON_ASSUME_SAFE_MACROS && !CYTHON_AVOID_BORROWED_REFS\n", "          __pyx_t_7 = PyList_GET_ITEM(__pyx_t_3, __pyx_t_5); __Pyx_INCREF(__pyx_t_7); __pyx_t_5++; if (unlikely(0 < 0)) __PYX_ERR(0, 13, __pyx_L1_error)\n", "          #else\n", "          __pyx_t_7 = PySequence_ITEM(__pyx_t_3, __pyx_t_5); __pyx_t_5++; if (unlikely(!__pyx_t_7)) __PYX_ERR(0, 13, __pyx_L1_error)\n", "          __Pyx_GOTREF(__pyx_t_7);\n", "          #endif\n", "        } else {\n", "          if (__pyx_t_5 >= PyTuple_GET_SIZE(__pyx_t_3)) break;\n", "          #if CYTHON_ASSUME_SAFE_MACROS && !CYTHON_AVOID_BORROWED_REFS\n", "          __pyx_t_7 = PyTuple_GET_ITEM(__pyx_t_3, __pyx_t_5); __Pyx_INCREF(__pyx_t_7); __pyx_t_5++; if (unlikely(0 < 0)) __PYX_ERR(0, 13, __pyx_L1_error)\n", "          #else\n", "          __pyx_t_7 = PySequence_ITEM(__pyx_t_3, __pyx_t_5); __pyx_t_5++; if (unlikely(!__pyx_t_7)) __PYX_ERR(0, 13, __pyx_L1_error)\n", "          __Pyx_GOTREF(__pyx_t_7);\n", "          #endif\n", "        }\n", "      } else {\n", "        __pyx_t_7 = __pyx_t_8(__pyx_t_3);\n", "        if (unlikely(!__pyx_t_7)) {\n", "          PyObject* exc_type = PyErr_Occurred();\n", "          if (exc_type) {\n", "            if (likely(__Pyx_PyErr_GivenExceptionMatches(exc_type, PyExc_StopIteration))) PyErr_Clear();\n", "            else __PYX_ERR(0, 13, __pyx_L1_error)\n", "          }\n", "          break;\n", "        }\n", "        __Pyx_GOTREF(__pyx_t_7);\n", "      }\n", "      __Pyx_XDECREF_SET(__pyx_v_j, __pyx_t_7);\n", "      __pyx_t_7 = 0;\n", "/* \u2026 */\n", "    }\n", "    __Pyx_DECREF(__pyx_t_3); __pyx_t_3 = 0;\n", "
+14:             cost = dist[i][j+1] + 1
\n", "
      __pyx_t_6 = __Pyx_PyIndex_AsSsize_t(__pyx_v_i); if (unlikely((__pyx_t_6 == (Py_ssize_t)-1) && PyErr_Occurred())) __PYX_ERR(0, 14, __pyx_L1_error)\n", "      __pyx_t_7 = __Pyx_PyInt_AddObjC(__pyx_v_j, __pyx_int_1, 1, 0, 0); if (unlikely(!__pyx_t_7)) __PYX_ERR(0, 14, __pyx_L1_error)\n", "      __Pyx_GOTREF(__pyx_t_7);\n", "      __pyx_t_9 = __Pyx_PyIndex_AsSsize_t(__pyx_t_7); if (unlikely((__pyx_t_9 == (Py_ssize_t)-1) && PyErr_Occurred())) __PYX_ERR(0, 14, __pyx_L1_error)\n", "      __Pyx_DECREF(__pyx_t_7); __pyx_t_7 = 0;\n", "      __pyx_v_cost = (((__pyx_v_dist[__pyx_t_6])[__pyx_t_9]) + 1);\n", "
+15:             c    = dist[i+1][j] + 1
\n", "
      __pyx_t_7 = __Pyx_PyInt_AddObjC(__pyx_v_i, __pyx_int_1, 1, 0, 0); if (unlikely(!__pyx_t_7)) __PYX_ERR(0, 15, __pyx_L1_error)\n", "      __Pyx_GOTREF(__pyx_t_7);\n", "      __pyx_t_9 = __Pyx_PyIndex_AsSsize_t(__pyx_t_7); if (unlikely((__pyx_t_9 == (Py_ssize_t)-1) && PyErr_Occurred())) __PYX_ERR(0, 15, __pyx_L1_error)\n", "      __Pyx_DECREF(__pyx_t_7); __pyx_t_7 = 0;\n", "      __pyx_t_6 = __Pyx_PyIndex_AsSsize_t(__pyx_v_j); if (unlikely((__pyx_t_6 == (Py_ssize_t)-1) && PyErr_Occurred())) __PYX_ERR(0, 15, __pyx_L1_error)\n", "      __pyx_v_c = (((__pyx_v_dist[__pyx_t_9])[__pyx_t_6]) + 1);\n", "
+16:             if c < cost : cost = c
\n", "
      __pyx_t_10 = ((__pyx_v_c < __pyx_v_cost) != 0);\n", "      if (__pyx_t_10) {\n", "        __pyx_v_cost = __pyx_v_c;\n", "      }\n", "
+17:             c = dist[i][j]
\n", "
      __pyx_t_6 = __Pyx_PyIndex_AsSsize_t(__pyx_v_i); if (unlikely((__pyx_t_6 == (Py_ssize_t)-1) && PyErr_Occurred())) __PYX_ERR(0, 17, __pyx_L1_error)\n", "      __pyx_t_9 = __Pyx_PyIndex_AsSsize_t(__pyx_v_j); if (unlikely((__pyx_t_9 == (Py_ssize_t)-1) && PyErr_Occurred())) __PYX_ERR(0, 17, __pyx_L1_error)\n", "      __pyx_v_c = ((__pyx_v_dist[__pyx_t_6])[__pyx_t_9]);\n", "
+18:             if mot1[i] != mot2[j] : c += 1
\n", "
      __pyx_t_7 = __Pyx_PyObject_GetItem(__pyx_v_mot1, __pyx_v_i); if (unlikely(!__pyx_t_7)) __PYX_ERR(0, 18, __pyx_L1_error)\n", "      __Pyx_GOTREF(__pyx_t_7);\n", "      __pyx_t_11 = __Pyx_PyObject_GetItem(__pyx_v_mot2, __pyx_v_j); if (unlikely(!__pyx_t_11)) __PYX_ERR(0, 18, __pyx_L1_error)\n", "      __Pyx_GOTREF(__pyx_t_11);\n", "      __pyx_t_12 = PyObject_RichCompare(__pyx_t_7, __pyx_t_11, Py_NE); __Pyx_XGOTREF(__pyx_t_12); if (unlikely(!__pyx_t_12)) __PYX_ERR(0, 18, __pyx_L1_error)\n", "      __Pyx_DECREF(__pyx_t_7); __pyx_t_7 = 0;\n", "      __Pyx_DECREF(__pyx_t_11); __pyx_t_11 = 0;\n", "      __pyx_t_10 = __Pyx_PyObject_IsTrue(__pyx_t_12); if (unlikely(__pyx_t_10 < 0)) __PYX_ERR(0, 18, __pyx_L1_error)\n", "      __Pyx_DECREF(__pyx_t_12); __pyx_t_12 = 0;\n", "      if (__pyx_t_10) {\n", "        __pyx_v_c = (__pyx_v_c + 1);\n", "      }\n", "
+19:             if c < cost : cost = c
\n", "
      __pyx_t_10 = ((__pyx_v_c < __pyx_v_cost) != 0);\n", "      if (__pyx_t_10) {\n", "        __pyx_v_cost = __pyx_v_c;\n", "      }\n", "
+20:             dist[i+1][j+1] = cost
\n", "
      __pyx_t_12 = __Pyx_PyInt_AddObjC(__pyx_v_i, __pyx_int_1, 1, 0, 0); if (unlikely(!__pyx_t_12)) __PYX_ERR(0, 20, __pyx_L1_error)\n", "      __Pyx_GOTREF(__pyx_t_12);\n", "      __pyx_t_9 = __Pyx_PyIndex_AsSsize_t(__pyx_t_12); if (unlikely((__pyx_t_9 == (Py_ssize_t)-1) && PyErr_Occurred())) __PYX_ERR(0, 20, __pyx_L1_error)\n", "      __Pyx_DECREF(__pyx_t_12); __pyx_t_12 = 0;\n", "      __pyx_t_12 = __Pyx_PyInt_AddObjC(__pyx_v_j, __pyx_int_1, 1, 0, 0); if (unlikely(!__pyx_t_12)) __PYX_ERR(0, 20, __pyx_L1_error)\n", "      __Pyx_GOTREF(__pyx_t_12);\n", "      __pyx_t_6 = __Pyx_PyIndex_AsSsize_t(__pyx_t_12); if (unlikely((__pyx_t_6 == (Py_ssize_t)-1) && PyErr_Occurred())) __PYX_ERR(0, 20, __pyx_L1_error)\n", "      __Pyx_DECREF(__pyx_t_12); __pyx_t_12 = 0;\n", "      ((__pyx_v_dist[__pyx_t_9])[__pyx_t_6]) = __pyx_v_cost;\n", "
+21:     cost = dist[l1][l2]
\n", "
  __pyx_v_cost = ((__pyx_v_dist[__pyx_v_l1])[__pyx_v_l2]);\n", "
+22:     return cost
\n", "
  __Pyx_XDECREF(__pyx_r);\n", "  __pyx_t_2 = __Pyx_PyInt_From_int(__pyx_v_cost); if (unlikely(!__pyx_t_2)) __PYX_ERR(0, 22, __pyx_L1_error)\n", "  __Pyx_GOTREF(__pyx_t_2);\n", "  __pyx_r = __pyx_t_2;\n", "  __pyx_t_2 = 0;\n", "  goto __pyx_L0;\n", "
"], "text/plain": [""]}, "execution_count": 5, "metadata": {}, "output_type": "execute_result"}], "source": ["%%cython --annotate\n", "cimport cython\n", "\n", "def cidistance_edition(str mot1, str mot2):\n", " cdef int dist [500][500]\n", " cdef int cost, c \n", " cdef int l1 = len(mot1)\n", " cdef int l2 = len(mot2)\n", " \n", " dist[0][0] = 0\n", " for i in range(l1):\n", " dist[i+1][0] = dist[i][0] + 1\n", " dist[0][i+1] = dist[0][i] + 1\n", " for j in range(l2):\n", " cost = dist[i][j+1] + 1\n", " c = dist[i+1][j] + 1\n", " if c < cost : cost = c\n", " c = dist[i][j]\n", " if mot1[i] != mot2[j] : c += 1\n", " if c < cost : cost = c\n", " dist[i+1][j+1] = cost\n", " cost = dist[l1][l2]\n", " return cost"]}, {"cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["16.9 \u00b5s \u00b1 3.47 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 10000 loops each)\n"]}], "source": ["mot1, mot2 = \"idstzance\",\"distances\"\n", "%timeit cidistance_edition(mot1, mot2)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["## solution sans notebook"]}, {"cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["11.4 \u00b5s \u00b1 1.93 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 100000 loops each)\n"]}], "source": ["import sys\n", "from pyquickhelper.loghelper import run_cmd\n", "\n", "code = \"\"\"\n", "def cdistance_edition(str mot1, str mot2):\n", " cdef int dist [500][500]\n", " cdef int cost, c \n", " cdef int l1 = len(mot1)\n", " cdef int l2 = len(mot2)\n", " \n", " dist[0][0] = 0\n", " for i in range(l1):\n", " dist[i+1][0] = dist[i][0] + 1\n", " dist[0][i+1] = dist[0][i] + 1\n", " for j in range(l2):\n", " cost = dist[i][j+1] + 1\n", " c = dist[i+1][j] + 1\n", " if c < cost : cost = c\n", " c = dist[i][j]\n", " if mot1[i] != mot2[j] : c += 1\n", " if c < cost : cost = c\n", " dist[i+1][j+1] = cost\n", " cost = dist[l1][l2]\n", " return cost\n", "\"\"\"\n", "\n", "name = \"cedit_distance\"\n", "with open(name + \".pyx\",\"w\") as f : f.write(code)\n", "\n", "setup_code = \"\"\"\n", "from distutils.core import setup\n", "from Cython.Build import cythonize\n", "setup(\n", " ext_modules = cythonize(\"__NAME__.pyx\",\n", " compiler_directives={'language_level' : \"3\"})\n", ")\n", "\"\"\".replace(\"__NAME__\",name)\n", "\n", "with open(\"setup.py\",\"w\") as f:\n", " f.write(setup_code)\n", "\n", "cmd = \"{0} setup.py build_ext --inplace\".format(sys.executable)\n", "\n", "out,err = run_cmd(cmd)\n", "if err is not None and err != '': \n", " raise Exception(err)\n", " \n", "import pyximport\n", "pyximport.install()\n", "import cedit_distance\n", " \n", "from cedit_distance import cdistance_edition\n", "\n", "mot1, mot2 = \"idstzance\",\"distances\"\n", "%timeit cdistance_edition(mot1, mot2)"]}, {"cell_type": "markdown", "metadata": {}, "source": ["La version Cython est 10 fois plus rapide. Et cela ne semble pas d\u00e9pendre de la dimension du probl\u00e8me."]}, {"cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["11.5 ms \u00b1 561 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 100 loops each)\n", "724 \u00b5s \u00b1 30 \u00b5s per loop (mean \u00b1 std. dev. of 7 runs, 1000 loops each)\n"]}], "source": ["mot1 = mot1 * 10\n", "mot2 = mot2 * 10\n", "%timeit distance_edition(mot1,mot2)\n", "%timeit cdistance_edition(mot1, mot2)"]}, {"cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [], "source": []}], "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.8.7"}}, "nbformat": 4, "nbformat_minor": 2}