Elimination des doublons dans une liste triée

I) Présentation

1) Objectif

  On veut éliminer les doublons dans une liste triée par ordre croissant.  Dans une liste s, un doublon e = s[i] est un élément qui se trouve au moins une fois avant la position i.
En d'autres termes, pour une liste s de longueur n:  
     ∀ i ∈ {1,..., n - 1},  e = s[i] est un doublon ⇔ ∃ j ∈ {0,..., i - 1} / s[j] = s[i].

Dans le cas particulier d'une liste triée (par ordre croissant): ∀ i ∈ {1,..., n - 1},  e = s[i] est un doublon ⇔ s[i] = s[i - 1].

  On veut écrire une fonction eliminer_doublons(s) (avec s liste triée  par ordre croissant) qui calcule la liste s  sans ses éventuels doublons.

Par exemple eliminer_doublons([1, 2, 2, 2, 3, 5, 5, 6, 6, 6]) = [1, 2, 3, 5, 6]

2) Méthodes

D'après la définition d'un doublon, on doit conserver la première occurrence de chaque élément de la liste.

Nous allons étudier les deux idées suivantes, avec une variante pour la première idée.

(1) Parcours de la liste et suppression au fur et à mesure des doublons trouvés:
    • (1a) On parcourt la liste dans l'ordre direct et, chaque fois qu'un doublon est trouvé, on le supprime de la liste.
    • (1b) On parcourt la liste dans l'ordre inverse et, chaque fois qu'un doublon est trouvé, on le supprime de la liste.     

(2) Création de la liste des représentants uniques:
    • On parcourt la liste s en ajoutant à une liste vide au départ chaque élément de s qui n'est pas un doublon.

II) Algorithmes

Q1) Ecrire une fonction eliminer_doublons_parcours_direct(s) éliminant les doublons de la liste s en exploitant l'idée (1a).

Q2) Ecrire une fonction eliminer_doublons_parcours_inverse(s) éliminant les doublons de la liste s en exploitant l'idée (1b).

Q3) Ecrire une fonction eliminer_doublons_creation(s) éliminant les doublons de la liste s en exploitant l'idée (2).

III) Calcul théorique des complexités des fonctions

1) Paramètres et hypothèses

On suppose que la liste s contient n éléments dont d doublons (il y a donc n - d éléments dans le résultat, la liste dédoublonnée).

Il y a deux paramètres à prendre en compte pour comparer les complexités des méthodes étudiées:
    • La longueur n de la liste s à dédoublonner
    •• La proportion x = d n de doublons dans la liste s initiale.

Les seules opérations élémentaires sont les comparaisons, ajout ou suppression d'un élément (on néglige les affectations).

  Une comparaison ou la suppression du dernier élément d'une liste ou l'ajout d'un élément à la fin d'une liste ont des coûts identiques, valant 1.

  Mais la suppression d'un élément e "au milieu" d'une liste s revient à décaler tous les éléments suivants pour les réindexer correctement: le coût de cette réindexation est proportionnel au nombre d'éléments qui suivent e dans s.

  Pour simplifier, si e = s[i] et s est de longueur n, le coût de la suppression de e dans la liste s sera de n - i . Ainsi le coût de la suppression du dernier élément de s est bien de n-(n-1)=1.

2) Calculs

Q4) Prouver que le coût C 3 ( n , x ) de la fonction  eliminer_doublons_creation(s) est C 3 ( n , x ) n ( 2 - x )

  Le calcul des coûts C 1 ( n , x ) et C 2 ( n , x ) des fonctions eliminer_doublons_parcours_direct(s) et eliminer_doublons_parcours_inverse(s) est un peu plus complexe.

Notons k 1 < k 2 < ... < k d les positions initiales des d doublons de la liste s de longueur n .

Q5) Pouver que C 1 ( n , x ) = n + Σ i = 1 d ( n - k i ) = ( n + 1 ) d - S avec S = Σ i = 1 d k i et que C 2 ( n , x ) = ( n + 1 ) d - S - ( d - 1 ) d 2 .

On fait l'hypothèse raisonnable que la position “moyenne” des doublons est k n 2 .

Q6) Prouver que C 1 ( n , x ) 1 2 x n ( n + 2 ) et que   C 2 ( n , x ) 1 2 x n ( n ( 1 - x ) + 3 )

Q7) En déduire les équivalents simples lorsque n tend vers l'infini et que x ∈ ]0, 1[ :

C 1 ( n , x ) 1 2 n 2 x         ;         C 2 ( n , x ) 1 2 n 2 x ( 1 - x )         ;         C 3 ( n , x ) n ( 2 - x )          

  Les fonctions agissant par suppression des éléments sont de complexité quadratique, et celle créant une nouvelle liste est de complexité linéaire.

  Par ailleurs ces calculs montrent qu'il est préférable de supprimer les éléments en commençant par la fin de la liste, d'autant plus que x est proche de 1. C'est normal, il y aura moins de décalages.

IV) Validation expérimentale des calculs de complexité

1) Objectif

  Le coût d'une fonction est ici le temps de calcul.  On veut comparer ces coûts en exécutant les fonctions écrites au II) sur des listes aléatoires triées de n entiers comprenant une proportion x de doublons (avec n ∈ N * et x ∈ ]0,1[).

2) Créer une liste aléatoire avec une proportion donnée de doublons

On admet qu'une liste aléatoire de n entiers de { 1 , 2 , ... , p }   contient une proportion de doublons environ égale à f ( x ) = 1 + e - x - 1 x , avec x = n p .

Q8) Démontrer que la fonction f est strictement croissante sur ]0,+∞[, et que f ( ] 0 , + [ ) = ] 0 , 1 [ .

Q9) Ecrire une fonction resoudre(y) qui calcule, pour y ] 0 , 1 [ , un réel α à ϵ = 10 - 10 près tel que f ( α ) = y .

Conseils:
    • Définir la sous fonction g ( x ) = f ( x ) - y pour se ramener à g ( x ) = 0
    • Déterminer un intervalle [ a , b ] tel que 0 < a < α < b : on pourra partir de a = b = 1 et, tant que g ( a ) > 0
(ou g ( b ) < 0 ), remplacer a par a 2 (ou b par 2 b ).
    • Calculer alors α , solution de g ( α ) = 0 ,  par dichotomie classique

Q10) Ecrire une fonction creer(n, x) avec n ∈ N * et x ∈ ]0,1[ calculant un entier p et une liste aléatoire triée de n entiers de l'ensemble {1, 2,..., p} contenant environ une proportion x de doublons.

  L'instruction s = [random.randint(1, p) for i in range(n)] crée une liste aléatoire s de n entiers  de
l'ensemble {1, 2,..., p}. (Ne pas oublier import random).

3) Comparaison des durées

  La fonction suivante comparer_durees(n, x) avec n ∈ N * et x ∈ ]0,1[ compare les durées d'exécution des trois fonctions pour une liste aléatoire de n entiers comprenant environ une proportion x de doublons

import time
def comparer_durees(n, x):
    """ durée d'exécution de l'élimination des doublons dans une liste triée de
    n entiers comprenant une proportion x de doublons """

    s, p = creer(n, x)
    print("Liste triée de {0} entiers aléatoires de [1, {1}]".format(n, p))
    print("Proportion demandée de doublons = {0:.6}".format(float(x)))

    liste_algos = (eliminer_doublons_parcours_direct,
        eliminer_doublons_parcours_inverse, eliminer_doublons_creation)

    for f in liste_algos:
        s1 = list(s)
        t = time.perf_counter()
        f(s1)
        t = time.perf_counter() - t
        print(" f = {0:35} : t = {1:.3g} s".format(f.__name__, t))

    y = (n - len(f(s1))) /n
    print("Proportion réelle de doublons = {0:.6}".format(y))
    print()

Par exemple: comparer_durees(100000, 0.5) peut renvoyer :

Liste triée de 100000 entiers aléatoires de [1, 62750]
Proportion demandée de doublons = 0.5
f = eliminer_doublons_parcours_direct   : t = 1.23 s
f = eliminer_doublons_parcours_inverse  : t = 0.561 s
f = eliminer_doublons_creation          : t = 0.0286 s
Proportion réelle de doublons = 0.49952

Q11) Pour une même valeur de x (tester avec diverses valeurs de x), proposer des valeurs significatives de n permettant de valider le fait que:

    (1) Les complexités des fonctions d'élimination des doublons par suppression sont quadratiques.

    (2) La complexité de la fonction d'élimination des doublons par création est linéaire.

    (3) C 2 ( n , x ) ( 1 - x ) C 1 ( n , x )

© 2014 - Eric Obermeyer      Powered by      Corrigé