T4.3 dictionnaire versus listes | Cercles informatiques

Dans une bibliothèque, nous avons 10000 livres. Pour chacun un certain nombre de caractéristiques : auteur, date de parution, nombre de pages etc...

Nous allons nous limiter à une seule caractéristique, par exemple le nombre de pages. Chaque livre à donc un nombre de page (remarquons qu'inversement, plusieurs livres peuvent avoir le même nombre de pages).

Nous aimerions trouver le plus rapidement possible le nombre de pages d'un livre. Nous devons décider comment représenter la situation. Nous pouvons utiliser des tuples (livre, nbDePages), on construira alors une liste de tuples, ou nous pouvons utiliser un dictionnaire : {livre1: nbDePages1, livre2: nbDePages2 etc...}

A première vue, laquelle des deux représentations vous semble la plus adaptée (laquelle vous semble plus naturelle) ?

Par ailleurs, ce choix aura-t-il un impact en terme d'efficacité dans la recherche ?

C'est ce que nous allons explorer dans ce TP.

👉 Nous utilisons ici le type : list de python

Implémenter avec une liste ou un dictionnaire

Implémentation avec liste ou dictionnaire

Exercice de code : représenter le problème avec une liste de tuples

Vous disposez de 2 listes : une liste de livres, et une liste de nombre de pages. Les deux listes sont en correspondance : nbPages[i] est le nombre de pages de livre[i].
En utilisant ces deux listes vous devez en construire une nouvelle, avec des tuples (livre, nombre de pages).
Ensuite, en repartant de cette liste, construire un dictionnaire comme décrit plus haut.

livre = []
nbPages = []
livre.append("Un soir au club")
nbPages.append(231)
livre.append("Ada ou l'Ardeur")
nbPages.append(452)
livre.append("Le père Goriot")
nbPages.append(320)
livre.append("Les misérables")
nbPages.append(603)
livre.append("L'étranger")
nbPages.append(257)
# Votre code ici : former une liste de tuples à partir des 2 listes crées ci-dessus

print(liste)

# former de même un dictionnaire en réutilisant la liste créée :

print(dico)

Rechercher l'information souhaitée

Fonctions de recherche de l'information

Bravo ! Vous avez bien implémenté les deux modèles. Maintenant, créez deux fonctions pour trouver le nombre de pages d'un livre.

Exercice de code : Chercher l'information

Le correcteur automatique va maintenant générer pour vous une liste et un dictionnaire, comme vous l'aviez fait dans l'exercice précédent.
Vous devez coder deux fonctions de recherche, l'une dans la liste, l'autre dans le dictionnaire, renvoyant toute deux le nombre de page d'un livre.
Votre code ne doit rien afficher, le correcteur définira des arguments pour tester vos deux fonctions.

def findInList(livre: str, liste: list) -> int:
    """
    cherche le livre dans liste et renvoie le nombre de page
    """
    pass

def findInDico(livre: str, dico: dict) -> int:
    """
    cherche le livre dans le dictionnaire et renvoie le nombre de page
    """
    pass

Mesure d'efficacité

Mesure de l'efficacité

La liste et le dictionnaire générés sont de taille très limitée, aussi la mesure de l'efficacité de l'un et l'autre n'est pas aussi probante que si nous travaillions avec des listes de 10000 livres.

Néanmoins nous pouvons comparer la recherche dans la liste et la recherche dans le dictionnaire.

Exercice de code : Chercher l'information

Le correcteur automatique va maintenant générer pour vous

une liste et un dictionnaire, comme précédemment, nommées liste et dico
les deux fonctions de recherche findInlist et findInDico
une variable livre1.

Tout ce que vous avez à faire est d'inclure des appels répétés (disons 10000 fois) à chacune de vos fonction, pour mesurer les temps des recherches.

Vous rechercherez livre1 dans la liste, ou dans le dico.

Pour une fois, le correcteur ne tiendra pas compte des affichage en console pour évaluer votre code, mais il évaluera quand même le résultat important : quelle méthode est la plus efficace ?

from time import time

nb_appels = 10000

t = time()
# faire nb_appels appels à findInList

dt1 = time() - t
print("temps moyen avec la liste : ", dt1/nb_appels)

t = time()
# idem pour findInDico

dt2 = time()-t
print("temps moyen avec le dico :", dt2/nb_appels)
# cette dernière ligne sert pour le test : on détermine quelle implémentation est plus efficace
winner = "dico" if dt1>dt2 else "liste"

Mesure plus fine de la complexité

Bon, le dictionnaire est plus efficace. Mais ici on travaille sur une bibliothèque de 5 livres.... passons à quelques chose de plus réaliste. Dans l'exemple ci-dessous vous n'avez rien à coder, mais observer et conclure.

On génère pour vous une bibliothèque (c'est à dire, une liste et un dictionnaire) de 10000 livres (bon, les noms des livres ici sont des entiers, mais ça importe peu..). Le code ci-dessous va utiliser les deux fonctions de recherche pour déterminer le nombre de pages d'un livre. On va prendre des livres du début de liste, puis de plus en plus loin dans la liste.... on devrait donc mettre de plus en plus longtemps pour les trouver.

Pour chaque livre la recherche est répétée 100 fois afin d'estimer un temps moyen a peu près stable.

Exemple : Complexités

from time import time
from random import randint
# création de la liste et du dico :
liste = [(i, randint(200, 500)) for i in range(10000)]
dico = {}
for i in range(10000) :
    dico[i] = liste[i][1]
    
print('Dans tous les appels, nous chercherons (dans la liste ou dans le dico) le nieme livre, n étant la longueur de la liste et du dico')

for n in ( 100, 200, 400, 800, 1600) :
    print('résultat avec ',n,' livres')
    t = time()
    for _ in range(n) :
        findInList(n, liste)
    dt1 = time() - t
    print('temps moyen avec la liste :',round(dt1/n*10**6,2),'µs')

    t = time()
    for _ in range(n) :
        findInDico(n, dico)
    dt2 = time() - t
    print('temps moyen avec le dico :',round(dt2/n*10**6,2),'µs')
    winner = 'dico' if dt1>dt2 else 'liste'

Exercice à choix multiple

La complexité de la recherche dans la liste vous semble :

Votre choix :

Correct !

Exercice à choix multiple

La complexité de la recherche dans le dictionnaire vous semble :

Votre choix :

Correct !