====== Structures ======

Dans le face à face des structures de données en séquences de python, c'est à dire les dictionnaires, listes et tuples, la logique voudrait que les tuples compenssent leur rigidité par une vitesse folle, et que les dictionnaires soient handicapés par leur malléabilité. Vérifions. 

{{page>info}}

La vitesse d'initialisation met en jeu l'enregistrement des données en mémoire.

<Code>
python -m timeit -n 1000000 -r 10 "dict = {0:10, 1:8, 2:2}"
1000000 loops, best of 10: 0.175 usec per loop

python -m timeit -n 1000000 -r 10 "list = [10, 8, 2]"
1000000 loops, best of 10: 0.112 usec per loop

python -m timeit -n 1000000 -r 10 "tuple = (10, 8, 2)"
1000000 loops, best of 10: 0.0137 usec per loop
</Code>

<gchart 270x130 hbar center "Vitesse d'initialisation">
{dict} = 175
[list] = 112
(tuple) = 013.7
</gchart>

Dans ce processus le tuple est beaucoup, beaucoup plus rapide.

<WRAP center tip>
Le tuple est une structure immuable, invariable, et donc à taille mémoire fixe, qui est précalculée et enregistrée telle quelle en mémoire. Les listes par contre peuvent être constamment modifiées et leur taille changer. Elles ne peuvent être précalculées, et pour éviter d'alouer de la mémoire supplémentaire à chaque fois qu'une valeur est ajoutée le système pré-aloue une zone mémoire plus grande dès le début. Et tout ça demande plus de temps.
</WRAP>


Evaluons maintenant leur vitesse de lecture d'une donnée et de parcours de leur contenu((A propos de l'utilisation de ''min()'' au lieu d'une moyenne, sur la doc de ''timeit'' : "//In a typical case, the lowest value gives a lower bound for how fast your machine can run the given code snippet; higher values in the result vector are typically not caused by variability in Python’s speed, but by other processes interfering with your timing accuracy.//" )).

<Code python>
import timeit
setup = "dict={0:10,1:8,2:2}; list=[10,8,2]; tuple=(10,8,2)"
min(timeit.repeat(stmt="dict[1]", setup=setup, repeat=100))
min(timeit.repeat(stmt="list[1]", setup=setup, repeat=100))
min(timeit.repeat(stmt="tuple[1]", setup=setup, repeat=100))
</Code>

  0.03086
  0.03403
  0.03402

<WRAP group>
<WRAP half column>
<gchart 270x130 hbar center "Accès à une donnée (sur trois)">
{dict} = 3086
[list] = 3403
(tuple) = 3402
</gchart>
</WRAP>
<WRAP half column>
<gchart 270x130 hbar center "Accès à une donnée (sur cent)">
{dict} = 3086
[list] = 3403
(tuple) = 3402
</gchart>
</WRAP>
</WRAP>

Surprise et stupéfaction : le tuple va à la même vitesse qu'une liste et le dictionnaire va un peu plus vite. Le résultat ne dépend pas de la taille de la structure, l'écart est le même avec cent éléments qu'avec trois.

Ré-essayons, en parcourant l'ensemble de la liste.

<Code python>
import timeit
setup = "dict={0:10,1:8,2:2}; list=[10,8,2]; tuple=(10,8,2)"
min(timeit.repeat(stmt="for i in dict: pass", setup=setup, repeat=10))
min(timeit.repeat(stmt="for i in list: pass", setup=setup, repeat=10))
min(timeit.repeat(stmt="for i in tuple: pass", setup=setup, repeat=10))
</Code>

  0.09433
  0.07980
  0.07989

<WRAP group>
<WRAP half column>
<gchart 270x130 hbar center "Parcours de trois éléments">
{dict} = 9433
[list] = 7980
(tuple) = 7989
</gchart>
</WRAP>
<WRAP half column>
<gchart 270x130 hbar center "Parcours de cent éléments">
{dict} = 1731
[list] = 1393
(tuple) = 1390
</gchart>
</WRAP>
</WRAP>

Tuple et liste sont encore identiques mais elles surpassent cette fois franchement le dictionnaire, et l'écart s'accentue légèrement avec le nombre d'éléments.

<WRAP center tip>
Le tuple et la liste sont enregistrées en mémoire sous la même forme. La manière d'accéder à leur contenu étant donc identique, aucune n'est plus rapide que l'autre.
</WRAP>