Pour aller plus loin

Création d'un annuaire

Par peur de perdre ses contacts, par exemple en cassant son téléphone, Alice a décidé de les sauvegarder sur son ordinateur.

Pour cela, elle pense utiliser un programme Python.

En plus de les sauvegarder, cela lui permettra aussi de les utiliser plus facilement.

Nous allons donc l'aider à écrire son programme.

Question

Tout d'abord, Alice doit choisir quelle structure de donnée elle va utiliser.

Au vu de vos connaissances, proposez une structure de données qui permet de stocker le nom et le numéro de téléphone des contacts.

Justifiez vos choix.

Solution

Liste de couple

Dans notre solution, nous allons décider de représenter les numéros par des strings (sans espace). Contrairement aux entiers, cela permet de garder le premier \(0\)

Pour l'annuaire ce sera donc une liste de couple de string ; la première étant de nom du contact et la deuxième le numéro de téléphone.

1
# L'annuaire suivant est celui composé exclusivement de Bob dont le numéro est le 01.23.45.67.89
2
annuaire = [("Bob", "0123456789")]

Question

Pour stocker ses contacts, Alice a besoin de pouvoir ajouter un·e ami·e dans son annuaire.

Écrivez une fonction ajout qui :

  • prend en paramètre :

    • annuaire : une liste de couple de string

    • nom : une string

    • numero : une string

  • ajoute le couple nom, numero dans l'annuaire.

Indice

On attend une fonction de la forme :

1
def ajout(annuaire: list, nom: str, numero: str):
2
    # Fait quelque chose

Solution

1
def ajout(annuaire: list, nom: str, numero: str):
2
    annuaire.append((nom, numero))

Question

Supposons qu'Alice a déjà 20 contacts dans son annuaire, combien d'opération va effectuer votre fonction ajout ?

Solution

Complexité asymptotique et Domination

On ne fait qu'une seule opération append, on ne fait donc qu'une seule opération.

On parle de \(O(1)\).

Question

Maintenant qu'Alice a son annuaire, elle souhaite pouvoir rechercher le numéro d'un·e ami·e à partir de son nom.

Écrivez une fonction recherche qui :

  • prend en paramètre :

    • annuaire : votre structure

    • nom : une string

  • retourne le numéro de téléphone de l'ami·e s'iel existe et None sinon

Indice

On attend une fonction de la forme :

1
def recherche(annuaire: list, nom: str):
2
    # Faire quelque chose

Solution

1
def recherche(annuaire: list, nom: str):
2
    for (nom1, numero) in annuaire:
3
        if nom1 == nom:
4
            return numero
5
    return None

Question

Supposons que l'annuaire d'Alice contient 20 contacts et que l'on cherche un contact qui n'existe pas.

Combien d'opération va effectuer votre fonction recherche ?

Indice

La boucle for passe par tous les éléments de la liste tant qu'on ne le trouve pas.

Solution

Complexité linéaire

On fait une opération pour chaque élément de la liste.

On fait donc 20 opérations. On parle de complexité linéaire.

On la note \(O(n)\) où \(n\) est la longueur de la liste.

Question

Alice peut désormais vérifier si un·e ami·e est dans son annuaire. Elle souhaite donc que sa fonction ajout n’insère son ami·e que s'iel n'existe pas encore.

Modifiez votre fonction ajout en conséquence. Elle retournera désormais un booléen représentant si oui ou non, l'ami·e a été ajouté·e dans l'annuaire.

Indice

On pourra faire appel à la fonction recherche pour voir si un contact est déjà dans l'annuaire.

Indice

En utilisant l'opérateur is None sur le retour de recherche on saura si une personne est déjà dans l'annuaire.

Solution

1
def ajout(annuaire: list, nom: str, numero: str) -> bool:
2
    if recherche(annuaire, nom) is None:
3
        annuaire.append((nom, numero))

Question

Supposons que l'annuaire d'Alice contient 20 contacts et que l'on ajoute un contact qui n'existe pas.

Combien d'opération va effectuer votre fonction ajout ?

Indice

On remarque que le nombre d'opération est celui de recherche plus celui de la fonction ajout initiale.

Solution

Somme de complexité asymptotique

Le nombre d'opérations effectuées est donc 21.

On parle alors d'une complexité de \(O(n + 1)\), ce qui est égal à \(O(n)\)

Question

Alice est déçue de la complexité (le nombre d'opération) de ses fonctions. Elle se dit qu'elle pourrait faire un système qui fonctionne plus vite.

Proposez un moyen d'obtenir des complexités plus intéressantes.

Solution

Une liste triée

On pourrait stocker les contacts dans l'ordre alphabétique, ainsi la recherche serait plus rapide et donc l'ajout sans doublon.

Un dictionnaire

On pourrait utiliser une structure de données appelée le dictionnaire qui a exactement les propriétés que l'on recherche