La notion de tableau (liste python)

  • Un même nom de variable pour un grand nombre de données
In [20]: 
liste = [1, 3.45, "bonjour", [4,5,6], ("a", "b")]

On évitera les tableaux avec des données de types différents, le traitement des données d'un tableau doit pouvoir se faire sans distinction de type.

  • Les cases du tableau sont numérotées à l’aide de valeurs entières consécutives appelées indices (ou index en anglais), pour un tableau de n valeurs on a les indices suivants:
  • Les données sont rangées dans les cases d’un tableau à 1 ou 2 dimensions
0, 1, 2 . . . n − 1

Créer une liste vide :

In [2]: 
L = []

Manipuler une liste

L'ensemble des fonctionnalités liées à un objet liste

In [3]: 
print dir(L)

['__add__', '__class__', '__contains__', '__delattr__', '__delitem__', '__delslice__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__getitem__', '__getslice__', '__gt__', '__hash__', '__iadd__', '__imul__', '__init__', '__iter__', '__le__', '__len__', '__lt__', '__mul__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__reversed__', '__rmul__', '__setattr__', '__setitem__', '__setslice__', '__sizeof__', '__str__', '__subclasshook__', 'append', 'count', 'extend', 'index', 'insert', 'pop', 'remove', 'reverse', 'sort']

Seules les fonctions : append, count, extend, index, insert, pop, remove, reverse, sort ont un intérêt pour nous. Comme d'habitude pour obtenir de l'aide sur une de ces fonctions on tape par exemple :

In [4]: 
print(help(L.append))

Help on built-in function append:

append(...)
    L.append(object) -- append object to end

None

Accéder aux éléments d'une liste, les éléments (encore mieux les objets) de la liste sont rangés par index croissant à partir de zéro.

\[ \begin{array}{|c|c|c|c|c|}\hline \text{index}& 0 & 1 & 2 & 3\\\hline \text{L} & 10.2 & 13 & 8 & 7.5\\\hline \end{array} \]

In [5]: 
L = [10.2, 13, 8, 7.5]
L[2], L[3] # accès par rang
Out[5]:
(8, 7.5)

La taille d'une liste est obtenue à l'aide de la primitive python len qui appartient au module builtins

In [6]: 
len(L)
Out[6]:
4

Accéder au dernier élément de la liste

In [7]: 
L[-1]
Out[7]:
7.5

Ajouter un élément à la liste par extension

In [9]: 
L.append(15)
print(L)

[10.2, 13, 8, 7.5, 15, 15]

Liste de liste ou tableau à 2 dimensions

Accès aux éléments d'une liste de liste, dans l'exemple suivant nous avons deux sous listes dans une liste principale

In []: 
tab = [[11,12,13],[7,9,11]]

\(\begin{array}{c|ccc} & 0 & 1 & 2 \\\hline 0 & 11 & 12 & 13 \\ 1 & 7 & 9 & 11\\ \end{array}\)

In []: 
print "Premier élément de tab: tab[0] = ", tab[0], "\nÉlément de la ligne 0 et de la colonne 1 : tab[0][1] = ",  tab[0][1]
print "Nombre de lignes : ", len(tab)
print "Nombre de colonnes:", len(tab[0])

Une autre façon de faire, les sous listes sont référencées par les variables K et L, ont peut donc modifier une sous liste directement à partir de K et L

In [10]: 
K = ["H","He"]
L = ["Li", "Be", "B", "C", "N", "O", "F", "Ne"]
classif = [K, L]
print classif #On crée des sous listes (tableau à deux dimensions)

[['H', 'He'], ['Li', 'Be', 'B', 'C', 'N', 'O', 'F', 'Ne']]

Concaténation de deux séquences

In [6]: 
print K+L #On crée une seule liste

['H', 'He', 'Li', 'Be', 'B', 'C', 'N', 'O', 'F', 'Ne']

Liste compréhension

Définition mathématique d’un ensemble en compréhension

Un ensemble peut être défini en compréhension, c’est-à-dire qu'on le définit par une propriété caractéristique parmi les éléments d'un ensemble donné. Ainsi l'ensemble des entiers naturels pairs est clairement défini par compréhension, par la propriété « être pairs » parmi les entiers naturels.

\[\text{pair} = \{2\times n\, |\,n \in \mathbb{N}\}\]

De manière analogue en python, une liste peut-être définie par le filtrage du contenu d'une autre liste.

In [42]: 
pair = [2*n for n in range(10)]
print(pair)

[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]

Copie d'une liste

Une erreur classique

Considérons la éléments de la liste référencée par le nom de variable : pair

Nous pourrions maintenant ajouter \(+1\) à tous les éléments de pair avec les instructions suivantes:

In [17]: 
for i in range (len(pair)):
    pair[i] += 1
print(pair)

[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

Dans ce cas nous perdons les valeurs pairs initialement dans la liste au profit des valeurs impairs.

Pour faire une copie de la liste : pair et modifier les valeurs de la copie afin conserver la liste pair intacte, beaucoup seront tentés dans un premier de temps par l'instruction impair = pair. Voyons ce que cela donne:

In [20]: 
impair = pair
for i in range (len(impair)):
    impair[i] += 1
print(impair)

[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

Cela à l'air de fonctionner, mais que se passe-t-il pour la liste pair ?

In [21]: 
print(pair)

[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

La liste pair a elle aussi été modifiée.

Avec l'instruction impair = pair nous obtenons un simple alias vers la même liste, toute modifiaction de la liste référencée par b à pour effet de modifier la liste référencée par a

Alors on fait comment ?

Tout dépend du contenu de la liste...

  • Si la liste ne contient que des objets non mutables on fait une copie superficielle ou shallow copy
In [24]: 
pair = [2*x for x in range(10)]
impair = pair[:]                # copie superficielle [:]
for i in range (len(impair)):
    impair[i] += 1
print(impair)
print(pair)

[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
[0, 2, 4, 6, 8, 10, 12, 14, 16, 18]
  • Si la liste contient des objets mutables on fait une copie profonde ou deep copy

Le problème

In [25]: 
pair = [[2*x] for x in range(10)]
impair = pair[:]
for i in range (len(impair)):
    impair[i][0] += 1 
print(impair)
print(pair)

[[1], [3], [5], [7], [9], [11], [13], [15], [17], [19]]
[[1], [3], [5], [7], [9], [11], [13], [15], [17], [19]]

Problème évident, à nouveau toute modification de impair modifie pair

La solution

Elle passe par l'import du package copy et l'utilisation de la fonction deepcopy

In [26]: 
import copy

pair = [[2*x] for x in range(10)]
impair = copy.deepcopy(pair)
for i in range (len(impair)):
    impair[i][0] += 1 
print(impair)
print(pair)

[[1], [3], [5], [7], [9], [11], [13], [15], [17], [19]]
[[0], [2], [4], [6], [8], [10], [12], [14], [16], [18]]

Quelle différence entre shallow copy et deep copy ?

shallow copy : copie des pointeurs des objets, dans les cas d'objets non mutables la copie superficielle permet de modifier les listes indépendamment l'une de l'autre. Attention les objets mutables seront modifiés dans les deux listes

  • Une liste uniquement avec des objets non mutables

  • Une liste avec des objets mutables

  • Que se passe-t-il si on modifie les objets de a ou de b ?

Conclusion

Avec une copie superficielle

Toutes modifications d'objets non mutables dans une des listes n'entrainent pas de modification dans l'autre liste
Toutes modifications d'objets mutables entrainent des modifications dans les deux listes a et b

Avec une copie profonde

La copie profonde consiste dans une réelle copie des objets, les deux listes sont complètement indépendantes. Technique très couteuse en temps

Initialisation d'une liste et complexité temporelle

Qu'est ce que la complexité temporelle ?

  • pouvoir prévoir le temps d'exécution d'un algorithme
  • pouvoir comparer deux algorithmes réalisant le même traitement
On peut évaluer la complexité par :
  • le calcul
  • une méthode expérimentale

Analyse temporelle expérimentale de l'initialisation d'une liste

In [29]: 
#affichage graphique dans les cellules du notebook
%matplotlib inline
import time #un module pour la gestion du temps
import matplotlib.pyplot as plt #module graphique
  • Avec la fonction append
In [30]: 
tab=[]
start = time.time()
for i in range(10000000):#10 millions ou 7 zéros
    tab.append(0)#ajout d'éléments avec la méthode append
print "%.3e" %(time.time()-start)

2.816e+00
  • Avec une liste compréhension
In [31]: 
start = time.time()
tab = [0 for i in range(10000000)] #10 millions
print "%.3e" %(time.time()-start)

1.383e+00
  • Liste et opérateur étoile \(\boxed{*}\) (splat)
In [32]: 
start = time.time()
tab = [0]*10000000 #10 millions
print "%.3e" %(time.time()-start)

8.502e-02

Attention aux objets mutables, nous avons une liste de 10 millions de références vers le même objet

Considérons la liste réduite suivante :

In [41]: 
L = [[0]]*5
print(L)
L[1][0] = 1
print(L)

[[0], [0], [0], [0], [0]]
[[1], [1], [1], [1], [1]]

Oups encore ce fichu objet mutable qui me cause du tourment !

  • Liste et opérateur \(\boxed{+}\)
In [36]: 
tab = []
start = time.time()
for i in range(100000):# 5 zéros
    tab = tab + [0]
print "%.3e" %(time.time()-start)

3.170e+01

À éviter technique très coûteuse en temps

Conclusion

Avec des objets non mutables, on utilise la technique la plus rapide

Avec des objets mutables au choix entre la fonction append et la liste compréhension

Parcourir une liste

Une simple liste

On commence par initialiser une liste référencée par le nom de variable loto, à l'aide de valeurs entières aléatoires

In [1]: 
from random import randint as rdint
loto = [rdint(0,49) for i in range(6)] # Attention randint[debut:fin] range[debut:fin[

On peut parourir la liste de deux façons :

  • À l'aide d'un index de liste
In [2]: 
for i in range(len(loto)): # renvoie la longueur du tableau
    print loto[i]
               

38
37
39
18
23
11
  • Avec la référence sur les objets de la liste
In [3]: 
for obj in loto:
    print obj

38
37
39
18
23
11
  • Avec les références et les index en même temps
In [6]: 
for index, obj in enumerate(loto):
    print "index",index, "valeur",obj

index 0 valeur 38
index 1 valeur 37
index 2 valeur 39
index 3 valeur 18
index 4 valeur 23
index 5 valeur 11

Tableau à 2 dimensions ou liste de listes

\[[\,[\,], [\,], [\,], \dots,[\,]\,]\]

In [13]: 
nb_grille = 2
ticket=[]
#Remplissage d'un tableau à 2-dimensions
#chaque ligne une grille de loto (6 numéros)
for i in range(nb_grille):
    grille=[]
    for j in range(6):
        grille.append(rdint(0,49))
    ticket.append(grille)
   
#Même chose mais avec les listes compréhensions
#ticket = [[rdint(0,49)for i in range(6)]for j in range(nb_grille)] 

#Le parcours démarre ici
#len(ticket) renvoie le nombre d'objets (grilles) contenus dans l'objet ticket
for i in range(len(ticket)):#parcours des lignes 
    print "Grille"+str(i)+": "
    #len(ticket[i]) renvoie le nombre d'objets contenus dans une grille soit 6 numéros
    for j in range(len(ticket[i])):#parcours des colonnes
        print ticket[i][j]

Grille0: 
48
37
13
28
7
21
Grille1: 
7
11
5
43
17
31

Rechercher une valeur dans une liste

Recherche séquentielle

In [3]: 
liste = [rdint(0,100) for i in range(20)] 
print liste

[10, 43, 34, 39, 13, 88, 91, 1, 89, 0, 43, 56, 61, 51, 73, 19, 79, 58, 71, 98]

On parcours le tableau case par case jusqu'à ce qu'on trouve ou pas la valeur cherchée

Écrire la fonction recherche

In [31]: 
def recherche(liste, k):
    n = len(liste)#longueur de la liste
    i = 0
    #while liste[i] != k and i < n: # cette situation engendre une erreur
    while (i < n) and (liste[i] != k): #l'opérateur AND est dit paresseux,
        i += 1
    if i < n:
        return i, k
    else:
        return i,"pas trouve"

Pour tester notre fonction dans l'intervalle [0, 100] prenons la valeur 61

In [5]: 
recherche(liste, 61)
Out[5]:
(12, 61)

Et avec une valeur qui n'est pas dans la liste ?

In [6]: 
recherche(liste, 2)
Out[6]:
(20, 'pas trouve')

Recherche dichotomique

Cette méthode s’applique à un tableau déjà trié et s’apparente à la technique diviser pour régner, elle impose donc un éventuel pré-traitement de tri

Prenons une autre valeur

In [39]: 
def dicho(t, val):
    g, d = 0, len(t)-1
    compt = 0
    while g <= d:
        i = (g + d)/2
        compt += 1
        if t[i] == val:
            return (i, compt, val)
        if t[i] < val:
            g = i + 1
        else:
            d = i - 1
    return (None, compt)
In [22]: 
tab = [3, 20, 87, 123, 128, 180, 200, 212]
dicho(tab, 127)
Out[22]:
(None, 3)
In [76]: 
from random import randint as rd
tab = [rd(0,1000000) for i in range(10000000)]#10 millions de valeurs
tab.sort()

Comparaison expérimentale de la complexité en temps. Pour cela on utilise une liste x contenant 10 valeurs tirées au hasard dans l'intervalle [0, 1 000 000]

In [77]: 
x = [rd(0, 1000000) for i in range(10)]
print x

[874047, 457776, 494076, 127669, 398164, 733240, 463564, 6524, 710374, 649532]
In [78]: 
start = time.time()
for elt in x:
    print recherche(tab, elt)
print "Temps d'accès  = %.3e s" %(time.time()-start)

(8738109, 874047)
(4576754, 457776)
(4939657, 494076)
(1276696, 127669)
(3980951, 398164)
(7331331, 733240)
(4634464, 463564)
(65362, 6524)
(7102952, 710374)
(6494021, 649532)
Temps d'accès  = 1.399e+01 s
In [79]: 
start = time.time()
for elt in x:
    print dicho(tab, elt)
print "Temps d'accès  = %.3e s" %(time.time()-start)

(8738110, 21, 874047)
(4576756, 18, 457776)
(4939668, 19, 494076)
(1276700, 16, 127669)
(3980958, 19, 398164)
(7331334, 21, 733240)
(4634473, 17, 463564)
(65362, 19, 6524)
(7102954, 20, 710374)
(6494024, 18, 649532)
Temps d'accès  = 1.017e-03 s

Conclusion : La recherche par dichotomie est environ \(10^4\) fois plus rapide, complexité en \(\log(n)\)

Pourquoi les deux méthodes ne donnent-elles pas les mêmes indices de position pour une même valeur ?

Élément de réflexion avec la première valeur cherchée : 874047

In [80]: 
tab[8738105 : 8738115]
Out[80]:
[874046,
 874046,
 874046,
 874046,
 874047,
 874047,
 874047,
 874048,
 874048,
 874048]
In [1]: 
import time
print time.strftime("Version du "+'%d/%m/%y %H:%M',time.localtime())

Version du 11/01/15 12:40

Christophe Casseau mail : isncaju@gmail.com