_doc/notebooks/code/code_liste_tuple.ipynb

{
 "metadata": {
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "heading",
     "level": 1,
     "metadata": {},
     "source": [
      "Liste, t-uple, ensemble, dictionnaire, liste cha\u00een\u00e9e, co\u00fbt des op\u00e9rations"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Plan\n",
      "\n",
      "- [Insertion avec ``list`` et ``deque``](#listdeque)\n",
      "- [Un \u00e9l\u00e9ment dans un ensemble](#set)\n",
      "\n",
      "\n",
      "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\n",
      "\n",
      "<h3 id=\"listdeque\">Insertion avec ``list`` et ``deque``</h3>\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",
     "collapsed": false,
     "input": [
      "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.clock()\n",
      "    for i in range(0,N) :\n",
      "        li.append(i)\n",
      "    b = time.clock()\n",
      "    print(\"    list\", N, \"\u00e9l\u00e9ments, temps par \u00e9l\u00e9ments :\", (b-a)/N)    \n",
      "        \n",
      "    li = collections.deque()\n",
      "    a = time.clock()\n",
      "    for i in range(0,N) :\n",
      "        li.append(i)\n",
      "    b = time.clock()\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.clock()\n",
      "    for i in range(0,N) :\n",
      "        li.appendleft(i)\n",
      "    b = time.clock()\n",
      "    print(\"    deque\", N, \"\u00e9l\u00e9ments, temps par \u00e9l\u00e9ments :\", (b-a)/N)    \n",
      "    \n",
      "    N2 = N // 100\n",
      "    li = list()\n",
      "    a = time.clock()\n",
      "    for i in range(0,N2) :\n",
      "        li.insert(0,i)\n",
      "    b = time.clock()\n",
      "    print(\"    list\", N, \"\u00e9l\u00e9ments, temps par \u00e9l\u00e9ments :\", (b-a)/N)   "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "passage  0\n",
        "  insertion en fin\n",
        "    list"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 1000000 \u00e9l\u00e9ments, temps par \u00e9l\u00e9ments : 2.5046494771072505e-07\n",
        "    deque"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 1000000 \u00e9l\u00e9ments, temps par \u00e9l\u00e9ments : 2.0089547068874937e-07\n",
        "  insertion au d\u00e9but\n",
        "    deque"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 1000000 \u00e9l\u00e9ments, temps par \u00e9l\u00e9ments : 1.9280886575847944e-07\n",
        "    list"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 1000000 \u00e9l\u00e9ments, temps par \u00e9l\u00e9ments : 4.187672524574282e-08\n",
        "passage  1\n",
        "  insertion en fin\n",
        "    list"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 1000000 \u00e9l\u00e9ments, temps par \u00e9l\u00e9ments : 2.054758845125093e-07\n",
        "    deque"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 1000000 \u00e9l\u00e9ments, temps par \u00e9l\u00e9ments : 1.8848161270256015e-07\n",
        "  insertion au d\u00e9but\n",
        "    deque"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 1000000 \u00e9l\u00e9ments, temps par \u00e9l\u00e9ments : 1.9194247434717227e-07\n",
        "    list"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 1000000 \u00e9l\u00e9ments, temps par \u00e9l\u00e9ments : 4.5812690966442916e-08\n",
        "passage  2\n",
        "  insertion en fin\n",
        "    list"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 1000000 \u00e9l\u00e9ments, temps par \u00e9l\u00e9ments : 2.0198166722616407e-07\n",
        "    deque"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 1000000 \u00e9l\u00e9ments, temps par \u00e9l\u00e9ments : 1.8757844455802796e-07\n",
        "  insertion au d\u00e9but\n",
        "    deque"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 1000000 \u00e9l\u00e9ments, temps par \u00e9l\u00e9ments : 1.8689465390315263e-07\n",
        "    list"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 1000000 \u00e9l\u00e9ments, temps par \u00e9l\u00e9ments : 4.0188416612011224e-08\n"
       ]
      }
     ],
     "prompt_number": 8
    },
    {
     "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``.\n",
      "\n",
      "<h3 id=\"set\">Un \u00e9l\u00e9ment dans un ensemble</h3>\n",
      "\n",
      "Faut-il \u00e9crire ``i in [0,1]`` ou ``i in (0,1)`` ou ... Essayons."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "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.clock()\n",
      "    s = 0\n",
      "    for i in range(0,N) :\n",
      "        if i in lens : s += 1\n",
      "    b = time.clock()\n",
      "    print(\"  list\", N, \"fois, temps par \u00e9l\u00e9ments :\", (b-a)/N)    \n",
      "    \n",
      "    a = time.clock()\n",
      "    s = 0\n",
      "    for i in range(0,N) :\n",
      "        if i in tens : s += 1\n",
      "    b = time.clock()\n",
      "    print(\"  tuple\", N, \"fois, temps par \u00e9l\u00e9ments :\", (b-a)/N)    \n",
      "    \n",
      "    a = time.clock()\n",
      "    s = 0\n",
      "    for i in range(0,N) :\n",
      "        if i in sens : s += 1\n",
      "    b = time.clock()\n",
      "    print(\"  set\", N, \"fois, temps par \u00e9l\u00e9ments :\", (b-a)/N)    \n",
      "    \n",
      "    a = time.clock()\n",
      "    s = 0\n",
      "    for i in range(0,N) :\n",
      "        if i in fens : s += 1\n",
      "    b = time.clock()\n",
      "    print(\"  frozenset\", N, \"fois, temps par \u00e9l\u00e9ments :\", (b-a)/N)    "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "passage 0\n",
        "  list"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 100000 fois, temps par \u00e9l\u00e9ments : 2.3807495183744436e-05\n",
        "  tuple"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 100000 fois, temps par \u00e9l\u00e9ments : 2.3632861293984887e-05\n",
        "  set 100000 fois, temps par \u00e9l\u00e9ments : 1.5523630120128474e-07\n",
        "  frozenset 100000 fois, temps par \u00e9l\u00e9ments : 1.4532368870618483e-07\n",
        "passage 1\n",
        "  list"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 100000 fois, temps par \u00e9l\u00e9ments : 2.327263746907704e-05\n",
        "  tuple"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 100000 fois, temps par \u00e9l\u00e9ments : 2.3603341551079778e-05\n",
        "  set 100000 fois, temps par \u00e9l\u00e9ments : 1.386097967230171e-07\n",
        "  frozenset 100000 fois, temps par \u00e9l\u00e9ments : 1.3637325818365298e-07\n",
        "passage 2\n",
        "  list"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 100000 fois, temps par \u00e9l\u00e9ments : 2.3171993234791443e-05\n",
        "  tuple"
       ]
      },
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        " 100000 fois, temps par \u00e9l\u00e9ments : 2.330123351728844e-05\n",
        "  set 100000 fois, temps par \u00e9l\u00e9ments : 1.3354230500340236e-07\n",
        "  frozenset 100000 fois, temps par \u00e9l\u00e9ments : 1.3071990455159722e-07\n"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "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",
     "collapsed": false,
     "input": [],
     "language": "python",
     "metadata": {},
     "outputs": []
    }
   ],
   "metadata": {}
  }
 ]
}