Informatique - Détection de doublons dans les inscriptions d'un établissement
Le service scolarité d'un établissement importe chaque matin un fichier CSV de 8000 inscriptions. Une fonction Python vérifie les doublons d'adresse e-mail en comparant chaque enregistrement à tous les autres : elle effectue environ 32 millions de comparaisons et prend 40 secondes, ce qui bloque l'interface. De plus, elle considère « [email protected] » et « [email protected] » comme différents, et elle échoue sur les adresses saisies avec un espace final. Le responsable informatique doit faire évoluer l'outil : le fichier pourrait atteindre 100000 lignes l'an prochain, et le traitement doit rester sous 5 secondes sur le poste actuel. Les développeurs proposent soit d'optimiser la boucle imbriquée, soit d'utiliser un ensemble (set) Python après normalisation des adresses. Le poste dispose de 8 Go de RAM. On estime qu'une comparaison de chaînes coûte 1,25 μs et qu'une insertion ou recherche dans un set coûte environ 0,2 μs.
1. Expliquer pourquoi l'approche actuelle est en O(n²) et estimer son temps d'exécution pour 100000 lignes. Cette approche peut-elle respecter l'objectif de 5 s ?
Read the worked answer
La fonction compare chaque enregistrement à tous les autres : pour n enregistrements, elle effectue n(n−1)/2 comparaisons, soit un coût proportionnel à n². C'est la source du O(n²).
Pour 8000 lignes : 8000×7999/2 ≈ 32 millions de comparaisons, ce qui correspond bien aux 40 s observées. Pour 100000 lignes : 100000×99999/2 ≈ 5×10⁹ comparaisons. À 1,25 μs par comparaison, cela donne environ 6250 s, soit près de 1 h 45.
Même une optimisation constante de la boucle ne dividedrait pas ce temps par 1000. L'approche O(n²) ne peut pas respecter l'objectif de 5 s pour 100000 lignes.
2. Proposer un algorithme avec un set et donner sa complexité. Estimer le temps pour 100000 lignes et l'ordre de grandeur de la mémoire supplémentaire, sachant qu'une adresse normalisée occupe environ 60 octets et que le set a un surcoût d'environ 2 fois.
Read the worked answer
Algorithme :
- Pour chaque enregistrement, normaliser l'adresse : supprimer les espaces de début et de fin, mettre en minuscules, et traiter les accents selon une règle fixée.
- Si l'adresse normalisée est déjà dans un set « vues », c'est un doublon.
- Sinon, l'ajouter au set.
Complexité attendue : O(n) opérations de recherche/insertion, donc O(n) en moyenne, au lieu de O(n²).
Pour 100000 lignes : environ 100000 recherches + 100000 insertions, soit 200000 opérations à 0,2 μs ≈ 0,04 s, auxquelles s'ajoute la normalisation. On reste très largement sous 5 s.
Mémoire : 100000 × 60 octets = 6 Mo, avec un surcoût d'environ 2 fois, soit environ 12 Mo. C'est négligeable sur 8 Go de RAM. Le set est donc le bon choix.
3. Rédiger une stratégie de normalisation qui traite la casse, les espaces et les variantes avec accent dans la partie locale, et expliquer pourquoi il ne faut pas supprimer les points du type « ahmed.benali » sans règle métier.
Read the worked answer
Stratégie proposée :
- supprimer les espaces en début et en fin de chaîne ;
- mettre toute l'adresse en minuscules ;
- séparer la partie locale et le domaine au niveau du dernier « @ » ;
- dans la partie locale, décomposer les caractères accentués (par exemple avec unicodedata.normalize en NFKD) puis retirer les diacritiques, afin que « é » et « e » soient traités de la même façon ;
- conserver le domaine en minuscules, sans accents ;
- appliquer éventuellement une règle interne pour les suffixes « + » si l'établissement les autorise.
Il ne faut pas supprimer les points de la partie locale sans règle métier : « [email protected] » et « [email protected] » peuvent désigner la même personne dans certains systèmes, mais pas dans tous. De même, supprimer tous les points peut créer de faux doublons entre deux personnes différentes. La normalisation doit être décidée avec le service scolarité, documentée et testée sur des cas réels.