Je dois implanter des fonctions SQL en Python et je dois faire Distinct sauf que j'ai une complexité assez dégueulasse

En effet, on modélise les tables par des listes d'enregistrement qui sont eux même des listes. Le nombre d'attribut de chaque enregistrement est appelé arité k et la taille de la table (nombre d'enregistrement) est n. On ne peut pas utiliser l'opérateur d'égalité entre listes de Python (seulement attribut par atribut).

J'ai donc fait une fonction qui vérifie si oui ou non deux listes (enregistrements) sont égales et sa complexité est en O(k) (vu qu'il faut comparé les k attributs des deux enregistrements et voir s'ils sont égaux)

Ensuite j'ai fait une fonction qui, à partir d'une liste vide "résultat", va vérifier un à un chaque élément de ma table et s'il ne trouve aucun doublon déjà présent dans "résultat" va l'ajouter dedans...

Sauf que du coup j'ai une complexité en O(k*n^3) si j'ai bien compris. Vu que j'ai une boucle for qui itère n fois sur chaque enregistrement de ma table, puis ensuite j'ai une 2e boucle for DANS LA 1ERE qui itère sur "résultat" dont la taille varie entre chaque tour de boucle et au pire elle augmente de 1 à chaque fois s'il n'y a jamais de doublon et donc il y aura au maximum 1+2+3...+n itération de cette 2e boucle soit O(n^2).Ce qui fait O(n^3) tours de boucles au total et dans chaque tour de boucle on fait des opérations élémentaires donc O(1) et on appelle aussi ma fonction qui vérifie s'il y a un doublon qui a une complexité en O(k) donc j'ai une complexité en O(k*n^3) ...

Vu que c'est sans doute pas clair voilà le code :

def EstDoublon(enregistrement1,enregistrement2) :
    k = 0
    while k < len(enregistrement1) :
        if enregistrement1[k] != enregistrement2[k] :
            return False
        k=k+1
    return True

def SupprimerDoublons(table) :
    res = []
    IlExisteUnDoublon = False 
    for enregistrement in table :
        for enregistrement_res in res :
            IlExisteUnDoublon = IlExisteUnDoublon or EstDoublon(enregistrement,enregistrement_res) 
        if not IlExisteUnDoublon : 
            res.append(enregistrement)
    return res

Du coup j'aimerais améliorer mon code voire totalement le changer s'il existe une autre "facon" plus élégante à laquelle je n'avais pas pensé.., et au moins être convaincu qu'il fonctionne. J'ai fait quelques essais ça à l'air de marcher en tout cas.

Tu réinitialises pas IlExisteUnDoublon, du coup dès que tu trouves un doublon tu vas supprimer tout le reste de ta table.

La complexité est O(k * n²), ton analyse est correcte mais à un moment tu passes de n² à n³ sans raison.

C'est pas forcément une mauvaise solution. L'alternative serait de remplacer la liste "res" par une table de hachage (kn en moyenne et kn² pire cas), ou alors de trier ta table (k n log n).

Ah oui je vais essayer de régler ça Si je met un "IlExisteUnDoublon = False" au début de la 1ere boucle, ça la réinitialise chaque fois qu'on change d'enregistrement non?

Sinon pour le n^3 : la 1ere boucle occure n fois et la deuxième qui est dedans n^2 fois donc au total ça fait n*n^2 tours de boucle cad n^3 non?

Le 24 juillet 2018 à 19:32:52 [iamthedoctor] a écrit :
Ah oui je vais essayer de régler ça Si je met un "IlExisteUnDoublon = False" au début de la 1ere boucle, ça la réinitialise chaque fois qu'on change d'enregistrement non?

Oui

Sinon pour le n^3 : la 1ere boucle occure n fois et la deuxième qui est dedans n^2 fois donc au total ça fait n*n^2 tours de boucle cad n^3 non?

La deuxième boucle s'exécute pas n² fois, elle s'exécute 1 fois, puis 2, puis 3, ... puis n.
Ton calcul "1 + 2 + 3 + ... + n = O(n²)" prend déjà en compte les deux boucles imbriquées

Oui tu as raison en fait je pensais à autre chose c'est bien O(n^2) merci