Détection de doublons : complexité, mémoire et un piège de correction
Une plateforme doit détecter les doublons parmi des identifiants clients (chaînes de 12 caractères) issus de fichiers de 200 000 lignes. La fonction actuelle compare chaque élément à tous les suivants au moyen de deux boucles imbriquées ; sur un fichier réel, elle s'exécute en 6 min 10 s, alors que le traitement doit tenir dans une fenêtre de 2 s. Le service demande en sortie la liste des identifiants présents au moins deux fois, chacun une seule fois, dans l'ordre de leur première répétition détectée. Un stagiaire propose de remplacer le tout par « len(liste) != len(set(liste)) », ce qui détecte la présence d'un doublon mais ne renvoie pas la liste attendue. Un collègue suggère de trier la liste puis de la parcourir, afin d'économiser la mémoire d'un ensemble. Le serveur dispose de 512 Mo de RAM et traite les fichiers un par un.
1. Estimer le coût de la version actuelle et vérifier qu'il est cohérent avec les 6 min 10 s observées.
Read the worked answer
Nombre de comparaisons. Deux boucles imbriquées sur n = 2·10⁵ éléments effectuent n(n−1)/2 = 2·10⁵ × 199 999/2 ≈ 2,0·10¹⁰ comparaisons de chaînes.
Temps. À 5·10⁷ comparaisons/s (ordre de grandeur réaliste pour une boucle Python avec comparaison de chaînes), on obtient 400 s, soit 6 min 40 s : cohérent avec les 370 s mesurées. L'ordre de grandeur est donc confirmé, et il n'y a pas de « bug caché » à chercher : la lenteur est structurelle, en O(n²).
Conséquence. Pour tenir en 2 s avec un algorithme en n², il faudrait 10¹⁰ comparaisons/s, soit un facteur d'accélération de 200 : irréaliste. Aucune optimisation micro (boucle locale, Cython, meilleure comparaison) ne peut combler un facteur 200 ; il faut changer la complexité. Critère de décision : on compare l'exposant, pas le facteur constant.
2. Écrire une version en O(n) qui respecte le format de sortie demandé, puis estimer sa consommation mémoire.
Read the worked answer
Code.
def doublons(liste):
vus = set() # déjà rencontrés au moins une fois
sortis = set() # déjà ajoutés au résultat
res = []
for x in liste:
if x in vus:
if x not in sortis:
sortis.add(x)
res.append(x)
else:
vus.add(x)
return res
Pourquoi ce code et pas un one-liner. len(liste) != len(set(liste)) ne renvoie qu'un booléen ; [x for x in liste if liste.count(x) > 1] est en O(n²) et renvoie chaque doublon autant de fois qu'il apparaît. Les deux ensembles sont nécessaires : vus mémorise la première rencontre, sortis évite les répétitions dans le résultat. Coût : O(n) en temps, O(d) en mémoire, d = nombre de valeurs distinctes.
Mémoire. 2·10⁵ chaînes d'environ 12 caractères : chaque objet str Python coûte ≈ 49 + 12 = 61 octets, soit ≈ 12 Mo, plus la table de hachage (≈ 2·10⁵ × 8 octets de pointeurs + surcharge, ≈ 8 à 16 Mo). Total de l'ordre de 25 à 30 Mo, très loin des 512 Mo disponibles. Le temps d'insertion est de quelques dizaines de millisecondes : le budget de 2 s est tenu avec une marge de deux ordres de grandeur.
3. Le collègue défend le tri préalable (O(n log n)) pour économiser la mémoire. Comparer les deux approches et trancher pour ce contexte.
Read the worked answer
Comparaison quantitative.
- Tri : n log₂ n ≈ 2·10⁵ × 17,6 ≈ 3,5·10⁶ opérations de comparaison, soit environ 5 700 fois moins que le n² initial. En Python,
sorted()sur 2·10⁵ chaînes prend de l'ordre de 0,1 à 0,2 s - largement dans le budget. - Mémoire du tri : la version
sorted()crée une copie de la liste (≈ 1,6 Mo de pointeurs), mais les chaînes elles-mêmes existent déjà ; le tri en place (liste.sort()) est en O(1) supplémentaire mais détruit l'ordre d'origine. - Ensemble : ≈ 25 à 30 Mo, également très en dessous des 512 Mo.
Le vrai critère n'est pas la mémoire. Avec 512 Mo et des fichiers traités un par un, l'argument mémoire ne tient pas : les deux solutions sont confortables. En revanche, le tri détruit l'ordre de première occurrence exigé par le cahier des charges, à moins de stocker les indices d'origine, ce qui coûte plus cher que l'ensemble. Le tri devient préférable si les données ne sont pas hachables (listes, dictionnaires) ou si l'on veut un traitement sur disque à mémoire bornée.
Décision. Ensemble pour ce format de sortie ; tri seulement si la contrainte mémoire devenait réelle ou si les éléments n'étaient pas hachables. À signaler : le hachage a un pire cas en O(n²) avec des collisions adversariales, risque à évaluer si les identifiants sont fournis par des tiers.