Python, any, lists et générateurs; choses étranges au profilage

a marqué ce sujet comme résolu.
Auteur du sujet

Salut à tous,

je suis sur un algo de recherche de sous-graphes en python. C’est donc (NP) complexe, et est censé prendre du temps. D’un autre côté, cela en prends trop, de manière anormal à mon avis; j’utilise donc kernprof pour profilé ligne par ligne pour une fonction, le temps pris.

Or, j’ai un résultat étonnant : j’ai une ligne ainsi :

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
...
    53    120244     740797.0      6.2     17.0             if any( [m[passed].get(i, False) for passed in isom] ): # si ce noeud est lié à un noeud passé, le tester

qui prends donc pas mal de ressource. Je me suis dit que je pourrais économiser en passant par un générateur, afin de ne pas avoir à générer la liste entière : j’ai eu donc :

Line #      Hits         Time  Per Hit   % Time  Line Contents
==============================================================
...
    53     35283     509901.0     14.5     12.8             if any( (m[passed].get(i, False) for passed in isom) ): # si ce noeud est lié à un noeud passé, le tester

C’est donc en effet plus rapide. J’aurais cependant 2 questions :

  • pourquoi le temps par hit est supérieur dans le cas 2 ?
  • pourquoi y a t-il moins de hit dans le cas 2 que dans le 1, sachant que les autres lignes sont identiques ?

La seul explication à laquelle je pense, est qu’any() s’execute par recursion… Avez vous une idée ?

Merci d’avance ! :)

+0 -0

Cette réponse a aidé l’auteur du sujet

Salut,

Je pense que ce qui te manque pour comprendre ce qui se passe, c’est que any est codé intelligemment. Dès qu’il rencontre un élément vrai, il arrête d’itérer la structure que tu lui as passée.

Une implémentation en Python de any pourrait être

def any(elements):
    for element in elements:
        if element:
            return True
    return False

Le code suivant s’arrête très vite car il ne génère que 4 éléments

from itertools import count
any(i == 3 for i in count())

alors que celui-ci remplit la mémoire de ta machine parce qu’il essaye de construire une liste infiniment longue.

from itertools import count
any([i == 3 for i in count()])

C’est pourquoi c’est une très mauvaise idée de générer la liste de ce qu’il y a à l’intérieur d’un any ou d’un all (ou toute fonction qui n’a pas besoin d’épuiser un générateur pour connaître le résultat demandé). En générant la liste, tu forces l’évaluation de tous les éléments de la liste. C’est coûteux en mémoire bien sûr, mais si en plus les opérations pour construire la liste sont complexes alors qu’il y a un élément vrai dans le début de ta liste, ça va aussi te coûter cher en temps pour fabriquer tous les éléments suivants alors qu’ils ne servent à rien.

Ça explique pourquoi tu as plus de hits en construisant la liste, la différence étant tous les appels inutiles à m[passed] et ceux à get. Par ailleurs, j’imagine que les éléments faux sont plus rapides à générer que les éléments vrais et que tu en as potentiellement beaucoup dans ta liste, ce qui peut expliquer qu’en moyenne, générer toute la liste coûte moins cher par élément que générer seulement les éléments jusqu’au premier qui est vrai.

Édité par adri1

I don’t mind that you think slowly, but I do mind that you are publishing faster. — W. Pauli

+5 -0
Auteur du sujet

Cette réponse a aidé l’auteur du sujet

Salut,

merci beaucoup pour l’explication. Je m’en doutais (de l’optimisation de any()), c’est pour ca que j’ai passé à un générateur.

Mon problème venait que je considérais les hits/lignes comme le nombre de fois où la ligne était exécutée; j’imagine que comme tu le dis ce n’est pas exactement cela.

EDIT :

Dans la FAQ de rkern : " Why do my list comprehensions have so many hits when I use the LineProfiler?

LineProfiler records the line with the list comprehension once for each iteration of the list comprehension."

QED ! :)

Édité par ez613

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte