Dans le cadre de mon stage actuel, j’ai eu à faire des différences entre des listes, c’est à dire à sortir la liste « intersection » des deux listes, et la liste « union-intersection » des deux listes (ou la liste « différence »). L’avantage avec Python, c’est qu’il existe des fonctions fournies directement, et qui font ça très bien (il y a sûrement la même chose dans plein d’autres langages). Ce qui est intéressant là-dedans, c’est que pour Python, j’ai identifié trois solutions pour faire les différences et intersections, et dans ma lutte pour l’optimisation, je me suis fait plaisir en chronométrant les différents temps d’exécution. Ces fonctions sont : SET, FROZENSET et LAMBDA.

J’ai testé ça sur des listes différentes, d’environ 9000 éléments chacune, ce qui me permet d’avoir un temps à peu près regardable, mais pas tant que ça (le temps total reste quand même infiniment petit à mes yeux), comme on va pouvoir le voir.

J’ai mis le code de test des trois fonctions en dessous, pour ceux que ça intéresse.

Pour le reste, voici le log d’exécution de ces fonctions (j’ai viré les mentions inutiles). Notez que Group1 est extrait d’un outil, et que Group2 est extrait de Google Groups. Les vérification à l’issue des trois tests servent à faire une diff entre les résultats, afin de montrer (si diff = 0) que les fonctions renvoient exactement les même listes.

• 2010-03-15 12:41:51,358 – Start.
• 2010-03-15 12:41:51,375 – Nombre total de groupes dans Group1 : 9173
• 2010-03-15 12:41:51,375 – Nombre total de groupes dans Google Groups (Group2) : 9118
• 2010-03-15 12:41:51,391 – Making difference between Group2 & Group1 :
  references found in Group1 but that don’t exist in Google Groups
• 2010-03-15 12:41:51,391 – Starting Difference with SET : 2010-03-15 12:41:51.391000
• 2010-03-15 12:41:51,405 – Finishing Difference with SET : 2010-03-15 12:41:51.406000
• 2010-03-15 12:41:51,405 – SET time : 0:00:00.015000
• 2010-03-15 12:41:51,405 – Starting Difference with FROZENSET : 2010-03-15
  12:41:51.406000
• 2010-03-15 12:41:51,405 – Finishing Difference with FROZENSET : 2010-03-15
  12:41:51.406000
• 2010-03-15 12:41:51,405 – FROZENSET time : 0:00:00
• 2010-03-15 12:41:51,405 – Starting Difference with FILTER : 2010-03-15
  12:41:51.406000
• 2010-03-15 12:41:53,530 – Finishing Difference with FILTER : 2010-03-15
  12:41:53.531000
• 2010-03-15 12:41:53,530 – FILTER time : 0:00:02.125000
• 2010-03-15 12:41:53,530 – Verification. Difference entre meth1 et meth2 : 0 | et
  difference entre meth2 et meth3 : 0
• 2010-03-15 12:41:53,530 – Making difference between Group1 & Group2 :
  references found in Google Groups but that don’t exist in Group1
• 2010-03-15 12:41:53,530 – Starting Difference with SET : 2010-03-15 12:41:53.531000
• 2010-03-15 12:41:53,546 – Finishing Difference with SET : 2010-03-15 12:41:53.547000
• 2010-03-15 12:41:53,546 – SET time : 0:00:00.016000
• 2010-03-15 12:41:53,546 – Starting Difference with FROZENSET : 2010-03-15
  12:41:53.547000
• 2010-03-15 12:41:53,546 – Finishing Difference with FROZENSET : 2010-03-15
  12:41:53.547000
• 2010-03-15 12:41:53,546 – FROZENSET time : 0:00:00
• 2010-03-15 12:41:53,546 – Starting Difference with FILTER : 2010-03-15
  12:41:53.547000
• 2010-03-15 12:41:55,687 – Finishing Difference with FILTER : 2010-03-15
  12:41:55.688000
• 2010-03-15 12:41:55,687 – FILTER time : 0:00:02.141000
• 2010-03-15 12:41:55,687 – Verification. Difference entre meth1 et meth2 : 0 | et
  difference entre meth2 et meth3 : 0
• 2010-03-15 12:41:55,703 – Making intersection between Group2 & Group1
• 2010-03-15 12:41:55,703 – Starting Intersection with SET : 2010-03-15
  12:41:55.703000
• 2010-03-15 12:41:55,703 – Finishing Intersection with SET : 2010-03-15
  12:41:55.703000
• 2010-03-15 12:41:55,703 – SET time : 0:00:00
• 2010-03-15 12:41:55,719 – Starting Intersection with FROZENSET : 2010-03-15
  12:41:55.703000
• 2010-03-15 12:41:55,719 – Finishing Intersection with FROZENSET : 2010-03-15
  12:41:55.719000
• 2010-03-15 12:41:55,719 – FROZENSET time : 0:00:00.016000
• 2010-03-15 12:41:55,719 – Starting Intersection with FILTER : 2010-03-15
  12:41:55.719000
• 2010-03-15 12:41:57,875 – Finishing Intersection with FILTER : 2010-03-15
  12:41:57.875000
• 2010-03-15 12:41:57,875 – FILTER time : 0:00:02.156000
• 2010-03-15 12:41:57,875 – Verification. Difference entre meth1 et meth2 : 0 | et
  difference entre meth2 et meth3 : 0
• 2010-03-15 12:41:57,905 – Making the intersection between Group1 & Group2
• 2010-03-15 12:41:57,905 – Starting Intersection with SET : 2010-03-15
  12:41:57.906000
• 2010-03-15 12:41:57,921 – Finishing Intersection with SET : 2010-03-15
  12:41:57.922000
• 2010-03-15 12:41:57,921 – SET time : 0:00:00.016000
• 2010-03-15 12:41:57,921 – Starting Intersection with FROZENSET : 2010-03-15
  12:41:57.922000
• 2010-03-15 12:41:57,921 – Finishing Intersection with FROZENSET : 2010-03-15
  12:41:57.922000
• 2010-03-15 12:41:57,921 – FROZENSET time : 0:00:00
• 2010-03-15 12:41:57,921 – Starting Intersection with FILTER : 2010-03-15
  12:41:57.922000
• 2010-03-15 12:42:00,421 – Finishing Intersection with FILTER : 2010-03-15
  12:42:00.422000
• 2010-03-15 12:42:00,421 – FILTER time : 0:00:02.500000
• 2010-03-15 12:42:00,421 – Verification. Difference entre meth1 et meth2 : 0 | et
  difference entre meth2 et meth3 : 0

Conclusions que l’on peut tirer de ce test :

Pour la différence : lambda toujours plus long, puis SET, puis frozenset.
Pour l’intersection :

• lambda est toujours plus long.
• Ensuite, le plus long entre set et frozenset dépend de la grandeur des deux objets à comparer.

  Si on a deux objets distincts, disons un grosObjet et un petitObjet :

  • grosObjet.intersection(petitObjet) => time(frozenset) > time(set)
  • petitObjet.intersection(grosObjet) => time(frozenset) < time(set)

Le code du test, comme promis :

def make_intersec(arg1,arg2):
# Make intersection between arg1 and arg2
    
    #Premiere methode : en utilisant SET
    startSET = datetime.now()
    logger.info("Starting Intersection with SET : "+str(startSET))
    setArg1 = set(arg1)
    setArg2 = set(arg2)
    intersecArg1Arg2meth1 = setArg2.intersection(setArg1)
    endSET = datetime.now()
    logger.info("Finishing Intersection with SET : "+str(endSET))
    logger.info("SET time : "+str(endSET-startSET))
    #Deuxieme methode, en utilisant FROZENSET
    startFROZENSET = datetime.now()
    logger.info("Starting Intersection with FROZENSET : "+str(startFROZENSET))
    frozensetArg1 = frozenset(arg1)
    frozensetArg2 = frozenset(arg2)
    intersecArg1Arg2meth2 = frozensetArg2.intersection(frozensetArg1)
    endFROZENSET = datetime.now()
    logger.info("Finishing Intersection with FROZENSET : "+str(endFROZENSET))
    logger.info("FROZENSET time : "+str(endFROZENSET-startFROZENSET))
    
    #Troisieme methode, en utilisant LAMBDA
    startFILTER = datetime.now()
    logger.info("Starting Intersection with FILTER : "+str(startFILTER))
    intersecArg1Arg2meth3 = filter(lambda x:x in arg1,arg2)
    endFILTER = datetime.now()
    logger.info("Finishing Intersection with FILTER : "+str(endFILTER))
    logger.info("FILTER time : "+str(endFILTER-startFILTER))

    result_methode_1 = frozenset(intersecArg1Arg2meth1)
    result_methode_2 = frozenset(intersecArg1Arg2meth2)
    result_methode_3 = frozenset(intersecArg1Arg2meth3)
    diffmeth1meth2 = result_methode_1.difference(result_methode_2)
    diffmeth2meth3 = result_methode_2.difference(result_methode_3)
    logger.info("Verification. Difference entre meth1 et meth2 : "+str(len(diffmeth1meth2))+" | et difference entre meth2 et meth3 : "+str(len(diffmeth2meth3)))
    
    result = list(intersecArg1Arg2meth2)
    result.sort()
    return result
  
  
def make_diff(arg1,arg2):
# Make difference between arg1 and arg2
    
    #Premiere methode : en utilisant SET
    startSET = datetime.now()
    logger.info("Starting Difference with SET : "+str(startSET))
    setArg1 = set(arg1)
    setArg2 = set(arg2)
    diffArg1Arg2meth1 = setArg2.difference(setArg1)
    endSET = datetime.now()
    logger.info("Finishing Difference with SET : "+str(endSET))
    logger.info("SET time : "+str(endSET-startSET))
    #Deuxieme methode, en utilisant FROZENSET
    startFROZENSET = datetime.now()
    logger.info("Starting Difference with FROZENSET : "+str(startFROZENSET))
    frozensetArg1 = frozenset(arg1)
    frozensetArg2 = frozenset(arg2)
    diffArg1Arg2meth2 = frozensetArg2.difference(frozensetArg1)
    endFROZENSET = datetime.now()
    logger.info("Finishing Difference with FROZENSET : "+str(endFROZENSET))
    logger.info("FROZENSET time : "+str(endFROZENSET-startFROZENSET))
    
    #Troisieme methode, en utilisant LAMBDA
    startFILTER = datetime.now()
    logger.info("Starting Difference with FILTER : "+str(startFILTER))
    diffArg1Arg2meth3 = filter(lambda x:x not in arg1,arg2)
    endFILTER = datetime.now()
    logger.info("Finishing Difference with FILTER : "+str(endFILTER))
    logger.info("FILTER time : "+str(endFILTER-startFILTER))

    result_methode_1 = frozenset(diffArg1Arg2meth1)
    result_methode_2 = frozenset(diffArg1Arg2meth2)
    result_methode_3 = frozenset(diffArg1Arg2meth3)
    diffmeth1meth2 = result_methode_1.difference(result_methode_2)
    diffmeth2meth3 = result_methode_2.difference(result_methode_3)
    logger.info("Verification. Difference entre meth1 et meth2 : "+str(len(diffmeth1meth2))+" | et difference entre meth2 et meth3 : "+str(len(diffmeth2meth3)))
    
    result = list(diffArg1Arg2meth2)
    result.sort()
    return result