Première NSI - Corrigé : Structures de données et écoconception

1. Recherche séquentielle dans une liste

La fonction parcourt les éléments un à un. Dans le pire des cas (l'élément recherché est à la fin ou absent), il faut examiner l'intégralité des n éléments. La complexité temporelle est en O(n).

def recherche_liste(catalogue, isbn_cherche):
    for livre in catalogue:
        if livre['isbn'] == isbn_cherche:
            return livre
    return None

2. Avantage du dictionnaire (Table de hachage)

Un dictionnaire en Python repose sur une table de hachage. Une fonction de hachage transforme directement la clé (l'ISBN) en un indice mémoire précis. L'accès à l'élément se fait en temps constant, soit une complexité en O(1) dans le cas moyen, évitant tout parcours séquentiel inutile.

3. Script de test et mesure comparative

import time
import random

# Génération de données factices (n = 50 000)
n = 50000
liste_catalogue = [{'isbn': f'ISBN-{i}', 'titre': f'Livre {i}'} for i in range(n)]
dict_catalogue = {item['isbn']: item['titre'] for item in liste_catalogue}

# Test de 1000 recherches dans la liste
debut = time.time()
for _ in range(1000):
    cible = f'ISBN-{random.randint(0, n-1)}'
    for livre in liste_catalogue:
        if livre['isbn'] == cible:
            break
fin = time.time()
print(f"Temps liste : {fin - debut:.4f} secondes")

# Test de 1000 recherches dans le dictionnaire
debut = time.time()
for _ in range(1000):
    cible = f'ISBN-{random.randint(0, n-1)}'
    _ = dict_catalogue.get(cible)
fin = time.time()
print(f"Temps dictionnaire : {fin - debut:.4f} secondes")

4. Analyse critique et perspective EDD

Pour 10 millions de requêtes quotidiennes :

Avec la liste (15 ms par requête) : 10⁷ × 0,015 = 150 000 secondes de calcul cumulées par jour (soit plus de 41 heures de processeur par jour).
Avec le dictionnaire (0,1 ms par requête) : 10⁷ × 0,0001 = 1 000 secondes de calcul cumulées par jour (soit environ 16 minutes).

Discussion pragmatique : Le choix d'une structure de données adaptée réduit le temps d'occupation du CPU par un facteur supérieur à 100. À l'échelle d'un datacenter, cela se traduit par une baisse immédiate de la sollicitation des unités de calcul, limitant la dissipation thermique et la consommation électrique des serveurs. L'écoconception logicielle démontre ainsi qu'un code optimisé possède une valeur écologique systémique majeure, indépendante du mix énergétique matériel.