{"cells": [{"cell_type": "markdown", "metadata": {}, "source": ["# 1A.1 - Liste, tuple, ensemble, dictionnaire, liste cha\u00een\u00e9e, co\u00fbt des op\u00e9rations\n", "\n", "Exemples de containers, list, tuple, set, dict."]}, {"cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [{"data": {"text/html": ["<div id=\"my_id_menu_nb\">run previous cell, wait for 2 seconds</div>\n", "<script>\n", "function repeat_indent_string(n){\n", "    var a = \"\" ;\n", "    for ( ; n > 0 ; --n)\n", "        a += \"    \";\n", "    return a;\n", "}\n", "var update_menu_string = function(begin, lfirst, llast, sformat, send, keep_item, begin_format, end_format) {\n", "    var anchors = document.getElementsByClassName(\"section\");\n", "    if (anchors.length == 0) {\n", "        anchors = document.getElementsByClassName(\"text_cell_render rendered_html\");\n", "    }\n", "    var i,t;\n", "    var text_menu = begin;\n", "    var text_memo = \"<pre>\\nlength:\" + anchors.length + \"\\n\";\n", "    var ind = \"\";\n", "    var memo_level = 1;\n", "    var href;\n", "    var tags = [];\n", "    var main_item = 0;\n", "    var format_open = 0;\n", "    for (i = 0; i <= llast; i++)\n", "        tags.push(\"h\" + i);\n", "\n", "    for (i = 0; i < anchors.length; i++) {\n", "        text_memo += \"**\" + anchors[i].id + \"--\\n\";\n", "\n", "        var child = null;\n", "        for(t = 0; t < tags.length; t++) {\n", "            var r = anchors[i].getElementsByTagName(tags[t]);\n", "            if (r.length > 0) {\n", "child = r[0];\n", "break;\n", "            }\n", "        }\n", "        if (child == null) {\n", "            text_memo += \"null\\n\";\n", "            continue;\n", "        }\n", "        if (anchors[i].hasAttribute(\"id\")) {\n", "            // when converted in RST\n", "            href = anchors[i].id;\n", "            text_memo += \"#1-\" + href;\n", "            // passer \u00e0 child suivant (le chercher)\n", "        }\n", "        else if (child.hasAttribute(\"id\")) {\n", "            // in a notebook\n", "            href = child.id;\n", "            text_memo += \"#2-\" + href;\n", "        }\n", "        else {\n", "            text_memo += \"#3-\" + \"*\" + \"\\n\";\n", "            continue;\n", "        }\n", "        var title = child.textContent;\n", "        var level = parseInt(child.tagName.substring(1,2));\n", "\n", "        text_memo += \"--\" + level + \"?\" + lfirst + \"--\" + title + \"\\n\";\n", "\n", "        if ((level < lfirst) || (level > llast)) {\n", "            continue ;\n", "        }\n", "        if (title.endsWith('\u00b6')) {\n", "            title = title.substring(0,title.length-1).replace(\"<\", \"&lt;\")\n", "         .replace(\">\", \"&gt;\").replace(\"&\", \"&amp;\");\n", "        }\n", "        if (title.length == 0) {\n", "            continue;\n", "        }\n", "\n", "        while (level < memo_level) {\n", "            text_menu += end_format + \"</ul>\\n\";\n", "            format_open -= 1;\n", "            memo_level -= 1;\n", "        }\n", "        if (level == lfirst) {\n", "            main_item += 1;\n", "        }\n", "        if (keep_item != -1 && main_item != keep_item + 1) {\n", "            // alert(main_item + \" - \" + level + \" - \" + keep_item);\n", "            continue;\n", "        }\n", "        while (level > memo_level) {\n", "            text_menu += \"<ul>\\n\";\n", "            memo_level += 1;\n", "        }\n", "        text_menu += repeat_indent_string(level-2);\n", "        text_menu += begin_format + sformat.replace(\"__HREF__\", href).replace(\"__TITLE__\", title);\n", "        format_open += 1;\n", "    }\n", "    while (1 < memo_level) {\n", "        text_menu += end_format + \"</ul>\\n\";\n", "        memo_level -= 1;\n", "        format_open -= 1;\n", "    }\n", "    text_menu += send;\n", "    //text_menu += \"\\n\" + text_memo;\n", "\n", "    while (format_open > 0) {\n", "        text_menu += end_format;\n", "        format_open -= 1;\n", "    }\n", "    return text_menu;\n", "};\n", "var update_menu = function() {\n", "    var sbegin = \"\";\n", "    var sformat = '<a href=\"#__HREF__\">__TITLE__</a>';\n", "    var send = \"\";\n", "    var begin_format = '<li>';\n", "    var end_format = '</li>';\n", "    var keep_item = -1;\n", "    var text_menu = update_menu_string(sbegin, 2, 4, sformat, send, keep_item,\n", "       begin_format, end_format);\n", "    var menu = document.getElementById(\"my_id_menu_nb\");\n", "    menu.innerHTML=text_menu;\n", "};\n", "window.setTimeout(update_menu,2000);\n", "            </script>"], "text/plain": ["<IPython.core.display.HTML object>"]}, "execution_count": 2, "metadata": {}, "output_type": "execute_result"}], "source": ["from jyquickhelper import add_notebook_menu\n", "add_notebook_menu()"]}, {"cell_type": "markdown", "metadata": {}, "source": ["Python propose diff\u00e9rents [containers](https://docs.python.org/3.4/tutorial/datastructures.html#) pour stocker des \u00e9l\u00e9ments. Voici les plus courants :\n", "\n", "- [list](https://docs.python.org/3.4/tutorial/datastructures.html#more-on-lists) : tableau d'\u00e9l\u00e9ments index\u00e9s de 0 \u00e0 $n$ exclu auquel on peut ajouter ou retirer des \u00e9l\u00e9ments\n", "- [dict](https://docs.python.org/3.4/tutorial/datastructures.html#dictionaries) : tableau d'\u00e9l\u00e9ments index\u00e9s par des types immuables auquel on peut ajouter ou retirer des \u00e9l\u00e9ments\n", "- [tuple](https://docs.python.org/3.4/tutorial/datastructures.html#tuples-and-sequences) : tableau d'\u00e9l\u00e9ments index\u00e9s de 0 \u00e0 $n$ exclu qu'on ne peut pas modifier\n", "- [set](https://docs.python.org/3.4/tutorial/datastructures.html#sets) : tableau d'\u00e9l\u00e9ments uniques non index\u00e9s\n", "- [frozenset](https://docs.python.org/3.4/tutorial/datastructures.html#sets) : ``set`` immuables (non modifiable)\n", "- [deque](https://docs.python.org/3.4/library/collections.html#collections.deque) : presque \u00e9quivalent \u00e0 une listes, la diff\u00e9rent vient de l'impl\u00e9mentation, les m\u00eames op\u00e9rations n'auront pas les m\u00eames co\u00fbts (deque = [liste cha\u00een\u00e9e](http://fr.wikipedia.org/wiki/Liste_cha%C3%AEn%C3%A9e))\n", "\n", "D'autres containers sont disponibles via le module [collections](https://docs.python.org/3.4/library/collections.html). Tous proposent de stocker un nombre variables d'\u00e9l\u00e9ments. Deux aspects diff\u00e9\u00e8rent :\n", "\n", "- la fa\u00e7on de d\u00e9signer un \u00e9l\u00e9ment de l'ensemble\n", "- le co\u00fbt de certaines op\u00e9rations, il faut choisir qui minisera le co\u00fbt des op\u00e9rations pour votre programme"]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Insertion avec ``list`` et ``deque``\n", "\n", "On veut comparer les co\u00fbts d'insertion en d\u00e9but et fin de liste pour un grand nombre d'\u00e9l\u00e9ments."]}, {"cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["passage  0\n", "  insertion en fin\n", "    list 1000000 \u00e9l\u00e9ments, temps par \u00e9l\u00e9ments : 1.6768032881764787e-07\n", "    deque 1000000 \u00e9l\u00e9ments, temps par \u00e9l\u00e9ments : 1.3930898200138983e-07\n", "  insertion au d\u00e9but\n", "    deque 1000000 \u00e9l\u00e9ments, temps par \u00e9l\u00e9ments : 1.2026622409235594e-07\n", "    list 1000000 \u00e9l\u00e9ments, temps par \u00e9l\u00e9ments : 2.2802558892816237e-08\n", "passage  1\n", "  insertion en fin\n", "    list 1000000 \u00e9l\u00e9ments, temps par \u00e9l\u00e9ments : 1.5078710092361442e-07\n", "    deque 1000000 \u00e9l\u00e9ments, temps par \u00e9l\u00e9ments : 1.210950632710861e-07\n", "  insertion au d\u00e9but\n", "    deque 1000000 \u00e9l\u00e9ments, temps par \u00e9l\u00e9ments : 1.2431481508550512e-07\n", "    list 1000000 \u00e9l\u00e9ments, temps par \u00e9l\u00e9ments : 2.6522458657794125e-08\n", "passage  2\n", "  insertion en fin\n", "    list 1000000 \u00e9l\u00e9ments, temps par \u00e9l\u00e9ments : 1.4364004201874892e-07\n", "    deque 1000000 \u00e9l\u00e9ments, temps par \u00e9l\u00e9ments : 1.3574118094175568e-07\n", "  insertion au d\u00e9but\n", "    deque 1000000 \u00e9l\u00e9ments, temps par \u00e9l\u00e9ments : 1.3737357535858763e-07\n", "    list 1000000 \u00e9l\u00e9ments, temps par \u00e9l\u00e9ments : 2.607208846534781e-08\n"]}], "source": ["import time, collections\n", "N = 1000000\n", "\n", "for p in range(0,3):\n", "    print(\"passage \", p)\n", "    print(\"  insertion en fin\")\n", "\n", "    li = list()\n", "    a = time.perf_counter()\n", "    for i in range(0,N) :\n", "        li.append(i)\n", "    b = time.perf_counter()\n", "    print(\"    list\", N, \"\u00e9l\u00e9ments, temps par \u00e9l\u00e9ments :\", (b-a)/N)    \n", "        \n", "    li = collections.deque()\n", "    a = time.perf_counter()\n", "    for i in range(0,N) :\n", "        li.append(i)\n", "    b = time.perf_counter()\n", "    print(\"    deque\", N, \"\u00e9l\u00e9ments, temps par \u00e9l\u00e9ments :\", (b-a)/N)    \n", "    \n", "    print(\"  insertion au d\u00e9but\")\n", "    li = collections.deque()\n", "    a = time.perf_counter()\n", "    for i in range(0,N) :\n", "        li.appendleft(i)\n", "    b = time.perf_counter()\n", "    print(\"    deque\", N, \"\u00e9l\u00e9ments, temps par \u00e9l\u00e9ments :\", (b-a)/N)    \n", "    \n", "    N2 = N // 100\n", "    li = list()\n", "    a = time.perf_counter()\n", "    for i in range(0,N2) :\n", "        li.insert(0,i)\n", "    b = time.perf_counter()\n", "    print(\"    list\", N, \"\u00e9l\u00e9ments, temps par \u00e9l\u00e9ments :\", (b-a)/N)   "]}, {"cell_type": "markdown", "metadata": {}, "source": ["On voit que l'insertion au d\u00e9but du tableau est beaucoup plus co\u00fbteuse pour une liste que pour un ``deque``."]}, {"cell_type": "markdown", "metadata": {}, "source": ["### Un \u00e9l\u00e9ment dans un ensemble\n", "\n", "Faut-il \u00e9crire ``i in [0,1]`` ou ``i in (0,1)`` ou ... Essayons."]}, {"cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [{"name": "stdout", "output_type": "stream", "text": ["passage 0\n", "  list 100000 fois, temps par \u00e9l\u00e9ments : 1.1804175089708608e-05\n", "  tuple 100000 fois, temps par \u00e9l\u00e9ments : 1.2459357053093508e-05\n", "  set 100000 fois, temps par \u00e9l\u00e9ments : 8.682663236478483e-08\n", "  frozenset 100000 fois, temps par \u00e9l\u00e9ments : 9.215601297539955e-08\n", "passage 1\n", "  list 100000 fois, temps par \u00e9l\u00e9ments : 1.1412313516123058e-05\n", "  tuple 100000 fois, temps par \u00e9l\u00e9ments : 1.1940795282648774e-05\n", "  set 100000 fois, temps par \u00e9l\u00e9ments : 8.101922725166411e-08\n", "  frozenset 100000 fois, temps par \u00e9l\u00e9ments : 8.893231054526218e-08\n", "passage 2\n", "  list 100000 fois, temps par \u00e9l\u00e9ments : 1.1539950008908635e-05\n", "  tuple 100000 fois, temps par \u00e9l\u00e9ments : 1.1629893677079037e-05\n", "  set 100000 fois, temps par \u00e9l\u00e9ments : 8.061231383216239e-08\n", "  frozenset 100000 fois, temps par \u00e9l\u00e9ments : 9.595650530114242e-08\n"]}], "source": ["import time, collections\n", "N = 100000\n", "lens = list(range(0,1000))\n", "tens = tuple(lens)\n", "sens = set(lens)\n", "fens = frozenset(lens)\n", "\n", "for p in range(0,3):\n", "    print(\"passage\",p)\n", "    a = time.perf_counter()\n", "    s = 0\n", "    for i in range(0,N) :\n", "        if i in lens : s += 1\n", "    b = time.perf_counter()\n", "    print(\"  list\", N, \"fois, temps par \u00e9l\u00e9ments :\", (b-a)/N)    \n", "    \n", "    a = time.perf_counter()\n", "    s = 0\n", "    for i in range(0,N) :\n", "        if i in tens : s += 1\n", "    b = time.perf_counter()\n", "    print(\"  tuple\", N, \"fois, temps par \u00e9l\u00e9ments :\", (b-a)/N)    \n", "    \n", "    a = time.perf_counter()\n", "    s = 0\n", "    for i in range(0,N) :\n", "        if i in sens : s += 1\n", "    b = time.perf_counter()\n", "    print(\"  set\", N, \"fois, temps par \u00e9l\u00e9ments :\", (b-a)/N)    \n", "    \n", "    a = time.perf_counter()\n", "    s = 0\n", "    for i in range(0,N) :\n", "        if i in fens : s += 1\n", "    b = time.perf_counter()\n", "    print(\"  frozenset\", N, \"fois, temps par \u00e9l\u00e9ments :\", (b-a)/N)    "]}, {"cell_type": "markdown", "metadata": {}, "source": ["Il appara\u00eet que les ensemble ``set`` ou ``frozenset`` sont beaucoup plus rapides. Plus l'ensemble est grand, plus cette diff\u00e9rence est importante."]}, {"cell_type": "code", "execution_count": 4, "metadata": {"collapsed": true}, "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.6.1"}}, "nbformat": 4, "nbformat_minor": 2}