Conteneurs

Cours/Coder et développer/Bases du langage python/Structurer son code/Conteneurs

En plus des 6 types de bases, python met à notre disposition plusieurs objets qui peuvent contenir d'autres objets.

Un conteneur est un objet itérable et possède l'opérateur in (comme on l'a déjà vu avec les chaînes de caractères). On pourra ainsi toujours utiliser x in C pour savoir si l'objet x est dans le conteneur C.

Parmi ces conteneurs, la liste est certainement la plus utilisée.

Listes

Ensembles et dictionnaires

Les deux autres conteneurs à connaître sont les ensembles et les dictionnaires. Ces deux structures sont très utiles lorsque l'on manipule des données mais sont plus complexes à manipuler que des listes. Prenez le temps d'apprendre à utiliser leurs nombreux avantages :

Ensembles et dictionnaires

L'exercice ci-après, en plus d'avoir une importance algorithmique certaine, vous permet de trouver la réponse à un problème de trois façons différentes

Exercice final

On possède une liste $P$ d'entiers correspondant à des prix ($P[i]$ correspond au prix de la marchandise $i$, allant de 0 à len(p) - 1) et un crédit $C$.

On peut pouvoir donner deux indices $i$ et $j$ tels que $p[i] + p[j] = C$.

Vous allez répondre à cette question de trois façons différentes :

utilisez deux boucles imbriquées allant de $0$ à $n-1$ permettent de balayer tous les couples $(i, j)$ avec $0 \leq i, j < n$
Commencez par trier la liste $P$ (vous pourrez utiliser la méthode sort des listes) puis utilisez une unique boucle while pour résoudre le problème. Cette boucle doit commencer avec i=0 et j=len(P)-1 et, à chaque étape, soit augmente i soit diminue j.
Créez un dictionnaire $d$ dont les clés $c$ sont les prix $P[i]$ ($0 \leq i < \text{len}(P)$) et les valeurs des indices $i$ ($0 \leq i < \text{len}(P)$) tels que P[d[c]] = c. Utilisez $d$ pour résoudre le problème

solution

On fait une recherche exhaustive de tous les couples $(i, j)$ :

for i in range(len(P)):
    for j in range(len(P)):
        if P[i] + P[j] == C:
            print(i, j)

Pour la deuxième solution, une fois le tableau trié il suffit de remarquer que :

si $P[i] + P[j] > C$ alors $P[i'] + P[j'] > C$ pour tous $i' \leq i$ et $j' \geq j$
si $P[i] + P[j] < C$ alors $P[i'] + P[j'] < C$ pour tous $i' \geq i$ et $j' \leq j$

P.sort()

i = 0
j = len(P)-1
while (i != j) and (P[i] + P[j] != C):
    if P[i] + p[j] < C:
        i += 1
    else:
        j -= 1

if i != j:
  print(i, j)

La troisième solution est très élégante et est très rapide en moyenne :

d = dict()

for i in range(len(P)):
  d[P[i]] = i

for k in d:
    if C - k in d:
        print(d[C-k], d[k])

Cet exercice est étudié de façon théorique dans la partie algorithmie. Les trois complexités sont de valeurs différentes. Si l'on veut une solution efficace en pratique on utilisera la troisième méthode (qui est linéaire en moyenne) et si on cherche une solution de complexité la plus faible on utilisera la seconde méthode (de complexité égale à celle du tri).

Cas particulier des chaines de caractères

Une chaine de caractère peut être vue comme un conteneur non mutable. On peut donc accéder à un caractère particulier comme une liste :


>>> "abcdefghijklmnopqrstuvwxyz"[2]
'c'

Ou même utiliser des slices de liste :

>>> "abcdefghijklmnopqrstuvwxyz"[2:15:4]
'cgko'

En reprenant le 27ème nombre de Mersenne sous sa forme chaine de caractère, m27 = str(2 ** 44497 - 1), résolvez les exercices suivants :

Quels sont les 10 premiers chiffres de m27 ?

solution

str(m27)[:10]

Quels sont les 10 derniers chiffres de m27 ?

solution

str(m27)[-10:]

Est-ce que m27 est un palindrome ?

solution

str(m27) == str(m27)[::-1] (s[::-1] renverse la chaîne)

En revanche, il est interdit de modifier une chaine de caractère :

>>> x = "chaine"
>>> x[0] = "C"
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'str' object does not support item assignment

Enfin on ne le répètera jamais assez, python vient avec tout un tas de méthodes utilitaires permettant de résoudre nombre d'opérations courantes. Utilisez la documentation sur les méthodes de chaînes en python pour résoudre les exercices suivants :

Index de la première occurrence de 1234 dans m27. Et de la deuxième ?

solution

str(m27).find('1234')
str(m27).find('1234', 19260 + 1) : la première occurrence est à l'indice 19260, on cherche donc après.
on peut faire en une ligne : str(m27).find('1234', str(m27).find('1234') + 1)