Université de Genève · CUI BSc · Algorithmique & Structures de données

Analyse et Complexité

Séminaire 5 · Passer à l'échelle au-delà des petites données
1 / 21

Feuille de route d'aujourd'hui

  • 1 Le mur de l'échelle
  • Pourquoi un code qui marche pour 10 éléments échoue pour 10 millions
  • 2 Notation grand O
  • Apprendre à ignorer le « bruit » et à voir la « forme »
  • 3 Indépendance machine
  • Mesurer les étapes plutôt que les millisecondes
  • 4 Étude de cas
  • Concevoir des algorithmes de recherche à l'échelle Spotify
  • Spotify
  • 640M+ — utilisateurs actifs
  • 100M+ — titres
  • < 1s — chargement de la page
  • Comment une requête peut-elle se terminer en moins d'une seconde quand n = 640 millions ?
  • Sources : Spotify SEC Q3 2024
2 / 21

Pourquoi l'analyse est importante

  • Les systèmes réels cassent quand les algorithmes ne tiennent pas la charge.
  • À l'échelle Spotify (n = 640M), même un parcours "rapide" en O(n) est trop lent.
  • Si nous vérifiions chaque utilisateur pendant 0,0001s, une seule requête prendrait 17 heures.
  • Nous avons besoin d'algorithmes qui restent rapides même lorsque les données mondiales explosent.
3 / 21

Deux algorithmes. Même résultat. Même vitesse ?

  • Scénario : quand vous aimez une chanson, Spotify doit vérifier instantanément : est-elle déjà là ?
  • Algorithme A — Liste
  • liked_songs = ["Shape of You", "Blinding Lights", ...]
  • def is_liked_A(song):
  • for s in liked_songs:
  • if s == song:
  • return True
  • return False
  • Algorithme B — Ensemble
  • liked_songs = {"Shape of You", "Blinding Lights", ...}
  • def is_liked_B(song):
  • return song in liked_songs
  • En Python, les deux renvoient la même réponse. Mais la stratégie est différente.
4 / 21

Résultats : l'écart est énorme

  • Temps de recherche d'une chanson dans une liste vs un ensemble quand n augmente.
  • Le test d'appartenance
  • # Alg A : Liste -> Parcourt les éléments un par un
  • "SongX" in songs_list
  • # Alg B : Ensemble -> Accède directement à l'élément
  • "SongX" in songs_set
  • Résultats du benchmark
  • n (Titres) | Temps (Liste) | Temps (Ensemble)
  • 1,000 | 0.03 ms | 0.0002 ms
  • 10,000 | 0.30 ms | 0.0002 ms
  • 100,000 | 3.00 ms | 0.0002 ms
  • 1,000,000 | 30.00 ms | 0.0002 ms
  • La Liste croît avec n
  • 10x de données = 10x de temps. C'est O(n).
  • L'Ensemble est constant
  • Le temps reste plat indépendamment de la taille. C'est O(1).
  • Échelle relative : si l'Ensemble prend 1 seconde, la Liste prend 4 heures pour n=1M.
5 / 21

Le problème avec le « temps »

Pourquoi les secondes ne sont pas une métrique fiable pour la théorie.
import time

start = time.perf_counter()
result = my_function(data)
elapsed = time.perf_counter() - start

# Problems:
# 1. Hardware: My Mac is faster than your laptop.
# 2. Noise: Is your browser open? Is your battery low?
# 3. Language: Python vs. C++ overhead.
6 / 21

La solution : compter les étapes

  • Au lieu des secondes, nous comptons les opérations de base.
  • 1 étape : Affectation de variable (`x = 10`)
  • 1 étape : Comparer deux valeurs (`a < b`)
  • 1 étape : Accéder à un indice de liste (`my_list[0]`)
  • Cela nous donne une formule T(n) qui fonctionne sur n'importe quel ordinateur.
7 / 21

Les maths : simplifier l'histoire

  • La forme : g(n)
  • Nous cherchons le « plan » de la croissance.
  • Boucles imbriquées = n²
  • Boucles simples = n
  • L'échelle : c
  • Nous utilisons un multiplicateur pour « étirer » le plan.
  • On se fiche que ce soit 3n ou 100n.
  • Ce sont tous deux une croissance « linéaire ».
8 / 21

Notation grand O : le plafond de sécurité

Notation grand O : le plafond de sécurité
La fonction f(n) est « piégée » sous le plafond c * g(n).
9 / 21

Notation grand O : analogies physiques

  • O(1) : Une opération directe unique, par ex. une recherche dans un ensemble (instantané).
  • O(log n) : Le jeu du "Plus haut / Plus bas" ; on réduit la zone de recherche de moitié à chaque étape.
  • O(n) : Lire chaque nom dans l'annuaire jusqu'à trouver le bon.
  • O(n²) : Pour chaque personne dans le livre, il faut relire tout le livre.
10 / 21

Les classes de croissance

NotationNomVitesseExemple
O(1)ConstantInstantanéRecherche dans un Set (déjà vu)
O(log n)LogarithmiqueExcellentRecherche binaire (semaine 7)
O(n)LinéaireBonRecherche dans une liste (déjà vue)
O(n log n)LinéarithmiqueCorrectTri / Diviser pour régner (semaine 9)
O(n²)QuadratiqueDangereuxBoucles imbriquées (déjà vues)
11 / 21

Le piège de la « boucle cachée »

Python fait paraître certaines opérations O(n) comme O(1).
my_list = [10, 20, 30, 40]

if 50 in my_list:   # This is a hidden Loop! O(n)
    print("Found")

max(my_list)        # This is a hidden Loop! O(n)
my_list.count(10)   # This is a hidden Loop! O(n)
12 / 21

Étude de cas : équivalence de playlists

  • Problème : Étant données deux playlists, sont-elles identiques ?
  • Elles doivent contenir les mêmes chansons avec les mêmes occurrences (multiplicité).
  • L'ordre n'a pas d'importance.
  • Objectif : Trouver la manière la plus efficace de vérifier cela à grande échelle.
13 / 21

Conception A : balayage imbriqué -> O(n²)

  • Motif : boucle externe * boucle interne.
  • La logique de la "double boucle"
  • def equiv_A(p1, p2):
  • for song in p1: # Loop 1
  • if song not in p2: # Boucle cachée 2 !
  • return False
  • return True
  • Cela fonctionne pour 10 chansons, mais échoue pour 10 000.
14 / 21

Conception B : trier et comparer -> O(n log n)

  • Si nous organisons d'abord les données, la comparaison devient facile.
  • La logique de "l'organisateur"
  • def equiv_B(p1, p2):
  • # Tri : O(n log n)
  • # Comparaison : O(n)
  • return sorted(p1) == sorted(p2)
  • Approche standard pour de nombreux problèmes réels.
15 / 21

Conception C : comptage par dictionnaire -> O(n)

  • Utiliser une table de hachage pour compter les occurrences en un seul passage.
  • La logique de "l'expert-comptable"
  • def equiv_C(p1, p2):
  • counts = {}
  • for s in p1:
  • counts[s] = counts.get(s, 0) + 1
  • # ... vérifier p2 par rapport à counts ...
  • return True
  • Vitesse linéaire : c'est ainsi que Spotify gère des millions de titres.
16 / 21

Conception D : la voie Pythonique -> O(n)

  • Python fournit des objets optimisés pour ces tâches courantes.
  • Utiliser les outils intégrés
  • from collections import Counter
  • def equiv_D(p1, p2):
  • return Counter(p1) == Counter(p2)
  • Sous le capot, cela utilise la logique de dictionnaire de la Conception C.
17 / 21

Les résultats : quand N croît...

Les résultats : quand N croît...
  • À n=10 : toutes les stratégies se valent.
  • À n=1 000 : la quadratique O(n²) commence à décrocher.
  • À n=1 000 000 : O(n²) est impossible ; O(n) termine instantanément.
  • Leçon : seule la forme de la courbe compte à l'échelle.
18 / 21

Exercices notebook

  • 1. Identifier les boucles cachées dans 5 extraits de code et justifier leur Big O.
  • 2. Implémenter manuellement l'"expert-comptable" (Conception C) dans votre notebook.
  • 3. Mesurer `sorted()` vs une boucle imbriquée pour n allant de 10 à 5 000.
  • 4. Concevoir une solution O(n) pour détecter les doublons dans une playlist.
19 / 21

Points clés

  • L'échelle change tout : ce qui marche pour 10 éléments échoue pour 10M.
  • La notation grand O est un outil de décision, pas seulement des maths.
  • Les dictionnaires et les ensembles sont des super-pouvoirs de performance (ils fournissent des recherches en O(1)).
  • Identifier "l'opération la plus coûteuse" : optimisez toujours le terme de plus forte croissance (n² avant n).
20 / 21
Université de Genève · CUI BSc · Algorithmique & Structures de données

Merci !

Suite : Maîtriser les algorithmes de tri
21 / 21