Séminaire 5 : Analyse & Complexité - Algorithmics & Data Structures

Université de Genève — Algorithmique & Structures de données

Objectifs d’aujourd’hui¶

Pourquoi l’analyse compte dans les systèmes réels
Big-O et les classes de croissance
Coûts des structures de données en Python (list, dict, set)
Arbitrages d’implémentation en pratique
Benchmarking équitable et interprétation

1) Motivation Spotify¶

Contraintes à l’échelle Spotify :

640M+ d’utilisateurs actifs
100M+ de titres
attentes produit de latence sous la seconde

Deux questions centrales de complexité :

Comment vérifier si une chanson est déjà dans la bibliothèque d’un utilisateur ?
Quand les recommandations doivent-elles être calculées (à la lecture vs pré-calculées) ?

La leçon clé : la complexité, c’est choisir où le travail a lieu.

# Two equivalent algorithms, very different scaling

def is_liked_list(song, liked_songs):
    for s in liked_songs:  # O(n)
        if s == song:
            return True
    return False


def is_liked_set(song, liked_song_set):
    return song in liked_song_set  # O(1) average


liked_list = ["Shape of You", "Blinding Lights", "Levitating"]
liked_set = set(liked_list)

print(is_liked_list("Levitating", liked_list))
print(is_liked_set("Levitating", liked_set))

2) Big-O : Idée principale¶

Supprimer les constantes : 5n -> O(n)
Ignorer les termes d’ordre inférieur : n^2 + n -> O(n^2)
Conserver le terme de croissance dominant : 3n^2 + 10n + 7 -> O(n^2)

À grande échelle, la classe de croissance compte davantage que les micro-optimisations.

3) Lire le Big-O à partir du code¶

Une boucle sur n éléments -> O(n)
Boucles imbriquées sur n et n -> O(n^2)
Test d’appartenance via hachage (x in set) -> O(1) en moyenne

# O(n): playlist scan
def contains_scan(playlist, target):
    for song in playlist:
        if song == target:
            return True
    return False

# O(n^2): pairwise work
def all_pairs_work(n):
    c = 0
    for i in range(n):
        for j in range(n):
            c += 1
    return c

# O(1) avg: hash lookup
def contains_hash(song_id, library_set):
    return song_id in library_set

4) Problème d’équivalence de playlists Spotify¶

Étant données deux playlists p1 et p2, déterminer si elles contiennent exactement les mêmes chansons :

mêmes identifiants de chanson
mêmes multiplicités
l’ordre n’a pas d’importance

Nous comparerons quatre designs (A/B/C/D) plus une solution conceptuelle basique par force brute.

from collections import Counter

# Design A: The Nested Scan -> O(n^2)
def playlist_equiv_A(p1, p2):
    if len(p1) != len(p2):
        return False
    for song in p1:
        if song not in p2:
            return False
    return True


# Design B: Sort and compare -> O(n log n)
def playlist_equiv_B(p1, p2):
    return sorted(p1) == sorted(p2)


# Design C: Frequency dict -> O(n)
def playlist_equiv_C(p1, p2):
    if len(p1) != len(p2):
        return False
    freq = {}
    for s in p1:
        freq[s] = freq.get(s, 0) + 1
    for s in p2:
        if freq.get(s, 0) == 0:
            return False
        freq[s] -= 1
    return True


# Design D: Counter map -> O(n)
def playlist_equiv_D(p1, p2):
    return Counter(p1) == Counter(p2)


# Quick checks
print(playlist_equiv_A([1, 2, 2, 3], [2, 1, 3, 2]))
print(playlist_equiv_B([1, 2, 3], [3, 2, 1]))
print(playlist_equiv_C([1, 1, 2], [1, 2, 1]))
print(playlist_equiv_D([1, 2, 2], [2, 1, 2]))
print(playlist_equiv_D([1, 2, 2], [1, 2, 3]))

Design X (conceptuel) : permutations par force brute¶

La force brute essaie chaque permutation d’une playlist et la compare à l’autre.

Une permutation désigne un ordre possible des mêmes éléments. Exemple avec les chansons [A, B, C] :

[A, B, C]
[A, C, B]
[B, A, C]
[B, C, A]
[C, A, B]
[C, B, A]

Donc pour 3 chansons, il y a 6 ordres possibles.

Ceci est en O(n!), où n! (“n factorial”) est le nombre de permutations de n éléments distincts :

n! = n * (n-1) * (n-2) * ... * 2 * 1

Exemples:

3! = 3 * 2 * 1 = 6
5! = 5 * 4 * 3 * 2 * 1 = 120
10! = 3,628,800

Le nombre de possibilités explose extrêmement vite, c’est pourquoi cette approche n’est qu’une ligne de base à titre d’avertissement.

Générer des titres de chansons factices¶

Next, you can use the script below to generate synthetic song titles so we can build large playlists.

# =================================================================
# DATA GENERATION (The "Black Box")
# DO NOT WORRY about how this code works!
# Its only job is to create thousands of fake song titles for our tests.
# =================================================================

import random
import time
import matplotlib.pyplot as plt

adjectives = [
    "Silent", "Golden", "Crazy", "Broken", "Shining", "Lost", "Fading", "Electric", "Wild", "Lonely",
    "Burning", "Hidden", "Distant", "Dark", "Bright", "Cold", "Sweet", "Eternal", "Fragile", "Majestic",
    "Secret", "Velvet", "Radiant", "Fallen", "Mystic", "Glowing", "Twilight", "Endless", "Frozen", "Luminous",
    "Melting", "Stormy", "Silent", "Velvet", "Shadowy", "Infinite", "Crystal", "Silver", "Golden", "Blazing",
    "Gentle", "Rapid", "Thunderous", "Soft", "Vivid", "Electric", "Fierce", "Whispering", "Haunting", "Sacred"
]

nouns = [
    "Heart", "Dream", "Sky", "Night", "Light", "Fire", "Rain", "Shadow", "Star", "World",
    "River", "Moon", "Sun", "Ocean", "Flame", "Stone", "Wind", "Garden", "Forest", "Wave",
    "Mist", "Song", "Journey", "Path", "Secret", "Whisper", "Storm", "Vision", "Time", "Soul",
    "Desire", "Memory", "Ember", "Frost", "Echo", "Horizon", "Pulse", "Spark", "Tide", "Realm",
    "Mirror", "Dreamscape", "Candle", "Phoenix", "Labyrinth", "Aura", "Galaxy", "Comet", "Petal", "Skyline"
]

verbs = [
    "Dancing", "Running", "Falling", "Flying", "Waiting", "Hiding", "Chasing", "Burning", "Shining", "Breaking",
    "Crying", "Laughing", "Rising", "Fading", "Screaming", "Gliding", "Spinning", "Whispering", "Shivering", "Drifting",
    "Exploding", "Twisting", "Crawling", "Leaping", "Sliding", "Soaring", "Floating", "Collapsing", "Shattering", "Singing",
    "Hoping", "Longing", "Waiting", "Glowing", "Trembling", "Calling", "Flickering", "Wandering", "Smiling", "Shaking",
    "Flowing", "Burning", "Breaking", "Melting", "Raging", "Cascading", "Dimming", "Hovering", "Rising", "Quivering"
]


def generate_song_title():
    pattern = random.choice([
        "{adj} {noun}",
        "{verb} {noun}",
        "{adj} {verb}",
        "{noun} of {noun}",
        "{adj} {noun} {verb}",
    ])
    return pattern.format(
        adj=random.choice(adjectives),
        noun=random.choice(nouns),
        verb=random.choice(verbs),
    )


def generate_unique_song_titles(total=5000):
    titles = set()
    attempts = 0
    max_attempts = total * 20
    while len(titles) < total and attempts < max_attempts:
        titles.add(generate_song_title())
        attempts += 1
    return list(titles)


def generate_playlist(n, catalog, unique_ratio=0.8):
    """Generates a list of n song titles."""
    num_unique = max(1, int(n * unique_ratio))
    pool = random.sample(catalog, k=min(num_unique, len(catalog)))
    return [random.choice(pool) for _ in range(n)]

5) Mise en place du benchmark réel¶

Nous passons maintenant des nombres statiques à un benchmark réel.

Ensuite, nous appelons cette fonction utilitaire pour générer un catalogue de titres synthétiques et exécuter les designs A-D sur des playlists échantillonnées.

# Build catalog + measure A/B/C/D on generated song titles

TOTAL_SONGS = 3000
catalog = generate_unique_song_titles(total=TOTAL_SONGS)
print(f"Catalog size: {len(catalog)} unique synthetic song titles")

sizes = [50, 100, 200, 400, 800, 1200]
reps = 3
curves = {
    "A - Nested O(n^2)": [],
    "B - Sort O(n log n)": [],
    "C - Dict O(n)": [],
    "D - Counter O(n)": [],
}

for n in sizes:
    p1 = generate_playlist(n, catalog)
    p2 = p1.copy()
    random.shuffle(p2)

    methods = [
        ("A - Nested O(n^2)", playlist_equiv_A),
        ("B - Sort O(n log n)", playlist_equiv_B),
        ("C - Dict O(n)", playlist_equiv_C),
        ("D - Counter O(n)", playlist_equiv_D),
    ]

    for label, fn in methods:
        best = float("inf")
        for _ in range(reps):
            t0 = time.perf_counter()
            fn(p1, p2)
            best = min(best, time.perf_counter() - t0)
        curves[label].append(best * 1000)

print("Benchmark complete. Curves ready for plotting.")

Now that we have measured runtimes, we can plot them as follows:

plt.figure(figsize=(10, 5))
for label, vals in curves.items():
    plt.plot(sizes, vals, marker="o", linewidth=2, label=label)

plt.title("Playlist Equivalence: Real benchmark on synthetic song titles")
plt.xlabel("Playlist length n")
plt.ylabel("Best runtime over 3 reps (ms)")
plt.grid(alpha=0.3)
plt.legend()
plt.show()

a_slowdown = curves["A - Nested O(n^2)"][-1] / curves["A - Nested O(n^2)"][0]
d_slowdown = curves["D - Counter O(n)"][-1] / curves["D - Counter O(n)"][0]
print(f"Design A slowdown (n={sizes[-1]} vs n={sizes[0]}): {a_slowdown:.1f}x")
print(f"Design D slowdown (n={sizes[-1]} vs n={sizes[0]}): {d_slowdown:.1f}x")

6) Pourquoi nous comptons les opérations (et pas seulement les secondes)¶

Le temps d’exécution brut dépend de :

le matériel,
les processus en arrière-plan,
l’état de Python/de l’environnement d’exécution.

C’est pourquoi l’analyse d’algorithmes se concentre sur la croissance indépendante de la machine.

Pour chaque algorithme, nous modélisons le travail avec une fonction T(n) :

choisir une opération de base (comparaison, affectation, recherche),
compter combien de fois elle s’exécute,
conserver le terme de croissance dominant (Big-O).

7) Rappel sur les boucles cachées + Vérifiez votre compréhension¶

Certains codes Python semblent être en temps constant mais cachent du travail linéaire.

Exemples typiques de boucles cachées :

x in my_list -> parcourt la liste (O(n)),
max(my_list) -> parcourt la liste (O(n)),
my_list.count(v) -> parcourt la liste (O(n)).

Vérifications rapides :

Quelle opération sur une liste n’est pas en O(1) ?
Pourquoi x in set est-il plus rapide que x in list à grande échelle ?
Un algorithme plus lent peut-il tout de même gagner pour de petites entrées ?
Pourquoi Spotify actualise-t-il Discover Weekly chaque semaine plutôt qu’à chaque ouverture de l’application ?

Partie 2 : Exercices du notebook¶

Chaque énoncé d’exercice se trouve directement au-dessus de sa cellule de code.

Exercice 01 : La chasse aux boucles cachées¶

Pour chaque extrait ci‑dessous :

Indiquez la complexité en Big-O.
Indiquez le mot-clé Python spécifique qui est en réalité une « boucle cachée ».

liked_songs = ["Blinding Lights", "Levitating", "As It Was"]
play_counts = [120, 340, 85, 510]
active_users = ["alice", "bob", "carol", "dina"]
premium_members = {"alice", "carol"}


def send_email(user):
    print(f"Sent premium message to {user}")


# Snippet 1
if "Levitating" in liked_songs:
    print("Found it!")

# Snippet 2
most_played = max(play_counts)
print("Most played:", most_played)

# Snippet 3
for user in active_users:
    if user in premium_members:
        send_email(user)

Exercice 02 : Le comptable (Design C)¶

Complétez l’ossature ci‑dessous pour implémenter la stratégie de comptage basée sur un dictionnaire.

def equiv_dict(p1, p2):
    """
    Design C: The Accountant (Dictionary)
    Complexity: O(n)
    """
    if len(p1) != len(p2):
        return False

    counts = {}

    # TODO 1: Count songs in p1
    # Hint: Use counts[song] = counts.get(song, 0) + 1
    for song in p1:
        pass  # Your code here

    # TODO 2: Check p2 against the counts
    for song in p2:
        if song not in counts or counts[song] == 0:
            return False
        counts[song] -= 1

    return True

Exercice 03 : Analyse de performance¶

Regardez le graphe que vous avez généré ci‑dessous.

Pour quelle valeur de n (longueur de la playlist) avez-vous commencé à ressentir un délai dans la Nested Scan ?
Si $n = 1,000,000$ , et que l’algorithme en $O(n^2)$ prend 1ms pour $n=100$ , calculez combien d’heures cela prendrait pour le million complet.
Pourquoi la courbe en $O(n)$ est-elle presque invisible en bas du graphique par rapport à $O(n^2)$ ?

# Ex 03 starter — Benchmark sorted() vs nested loop (n from 10 to 5000)

def equiv_nested(p1, p2):
    """
    Design A: The Nested Scan
    Complexity: O(n^2)
    """
    if len(p1) != len(p2):
        return False

    for song in p1:          # Loop 1
        if song not in p2:   # Loop 2 (Hidden inside "in")
            return False

    return True


def equiv_sorted(p1, p2):
    # O(n log n)
    return sorted(p1) == sorted(p2)


sizes = [10, 50, 100, 250, 500, 1000, 2500, 5000]
nested_ms, sorted_ms = [], []

for n in sizes:
    p1 = [random.randint(1, 100000) for _ in range(n)]
    p2 = p1.copy()
    random.shuffle(p2)

    t0 = time.perf_counter()
    equiv_nested(p1, p2)
    nested_ms.append((time.perf_counter() - t0) * 1000)

    t0 = time.perf_counter()
    equiv_sorted(p1, p2)
    sorted_ms.append((time.perf_counter() - t0) * 1000)

plt.figure(figsize=(10, 5))
plt.plot(sizes, nested_ms, marker="o", linewidth=2, label="Nested scan O(n^2)")
plt.plot(sizes, sorted_ms, marker="o", linewidth=2, label="sorted() compare O(n log n)")
plt.title("Ex 03: sorted() vs nested loop")
plt.xlabel("n")
plt.ylabel("Runtime (ms)")
plt.grid(alpha=0.3)
plt.legend()
plt.show()

Ex 04 — détection de doublons en O(n)¶

Concevez et testez un algorithme en O(n) pour détecter des doublons dans une playlist.

# Ex 04 starter — Design an O(n) duplicate checker for playlists

def has_duplicates_playlist(song_ids):
    # TODO: design O(n) solution
    # Hint: track seen song IDs in a set
    return False

#  Tests
print(has_duplicates_playlist([10, 20, 30, 40]) is False)
print(has_duplicates_playlist([10, 20, 30, 20]) is True)
print(has_duplicates_playlist([]) is False)

Consigne de réflexion¶

Pour chaque exercice, écrivez 2–3 lignes :

Quelle était l’opération dominante ?
Quelle classe de croissance avez-vous observée ?
Quel design choisiriez-vous à l’échelle de Spotify, et pourquoi ?

Points clés¶

Commencez par la question système : où le travail doit-il avoir lieu ?
Big-O guide les choix de conception avant les défaillances en production.
Le benchmarking valide la théorie ; la théorie explique les benchmarks.
À grande échelle, le choix de la structure de données est souvent le principal levier de performance.