Discussion :

[pylearner]

Je découvre un peu le cProfiler de python et je découvre une chose qui va à l'encontre des principes que j'avais souvent lu jusqu'à là concernant l'optimisation.

En l'occurrence, l'utilisation d'une boucle dans le calcul d'une somme (pour le calcul d'un coefficient du carré d'une matrice) est plus efficace que la fonction sum.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def somme(l, i, j):
    """Moins efficace qu'on pourrait le croire"""
    return sum([l[i][k]*l[k][j] for k in range(len(l))])
 
   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   199584    2.000    0.000    2.000    0.000 modnoter.py:18(<listcomp>)
   199584    0.282    0.000    2.447    0.000 modnoter.py:16(somme)
   202032    0.149    0.000    0.149    0.000 {built-in method sum}
 
def somme(l, i, j):
    """Sans l'utilisation d'une liste, c'est encore plus long !"""
    return sum(l[i][k]*l[k][j] for k in range(len(l)))
 
   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
  7384608    2.453    0.000    2.453    0.000 modnoter.py:18(<genexpr>)
   202032    0.863    0.000    3.316    0.000 {built-in method sum}
   199584    0.202    0.000    3.534    0.000 modnoter.py:16(somme)
 
#Finalement, la bonne méthode
def somme(l, i, j):
    """somme pour le calcul d'un produit de matrice"""
    s = 0
    for k in range(len(l)):
        s += l[i][k] * l[k][j]
    return s
 
   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
   199584    1.930    0.000    1.945    0.000 modnoter.py:9(somme)

Qu'en pensez-vous ?
(Je suis sur Python 3, sous linux)

[dividee]

Bonsoir,

Je ne suis pas sûr que le profiler soit le meilleur outil pour ce genre de comparaisons; il me semble qu'il est plutôt destiné à voir le temps que prennent les différentes parties du programme les unes par rapport aux autres, pas à faire un benchmark comparatif de différents snippets. Le module timeit ou simplement time.clock() sont plus adaptés et donneront un résultat plus précis, à mon avis. Mais bon, les variations que tu rapportes sont assez significatives, donc devraient être observées également avec l'une de ces méthodes.

J'ai testé tes fonctions avec Python 2.7 (en remplaçant range par xrange pour être dans les mêmes conditions qu'en Python 3). Le résultat est similaire mais les différences sont nettement moins prononcées:

(40000 appels de la fonction somme avec len(l)=200, moyenne de 4 runs)
sum(listcomp) --> 1.941 s
sum(genexpr) --> 2.280 s
boucle for --> 1.885 s

On peut attribuer la lenteur de la seconde version à l'overhead du générateur, mais celui-ci semble plus raisonnable en Python 2.7 qu'en Python 3, ce qui m'étonne un peu. Je serais tout de même curieux de voir les résultats que tu obtiens avec time.clock() au lieu d'un profiling.

[emmanuel_dumas]

Bonjour

Tu viens de comprendre une chose primordiale en matière d'optimisation : il n'y a que le chronomètre qui fait foi. Tout les "on dit" qu'en procédant comme ceci ou comme cela ne sont souvent que des pistes possibles de recherche dans un certain contexte qu'il faut valider dans son contexte avec un chronomètre.
Par contre, dans ce cas il faut être sur du chronomètre, et la je ne sais pas trop quoi dire.

Cordialement,
Emmanuel

[Zavonen]

Bonjour,
Cela ne me surprend pas outre mesure.
La méthode consistant à appeler la fonction sum sur une 'list comprehension' utilise en fait deux itérations. Une pour construire la liste et l'autre pour la sommer.
La méthode 'classique', faisant deux choses à la fois, fait donc l'économie d'une boucle.

[pylearner]

dividee
Le time.clock() donne
boucle for --> 0.0290191173553
sum(listcomp) --> 0.041130065918
sum(genexpr) --> 0.0446801185608


emmanuel_dumas:
Et bien merci, c'est bon à savoir.

Sinon le module numpy est maintenant disponible et fait le travail d'une manière beaucoup, beaucoup plus efficace pour les produits de matrices. Mais il est bon de savoir que seul le chronomètre compte et que python n'est pas forcément le meilleur langage pour itérer ce genre d'opérations.