Optimisation d'un parcours de tableau de chaine

Bonjour,

Je débute un peu en Python et en particulier sur le module 're'. J'ai
l'impression que ma programmation est un peu maladroite et je sens que
je pourrais faire autrement mais je ne vois pas trop comment.

Je voulais coder en Python la fonction matlab suivante :
x = strmatch('str', STRS) parcourt le tableau STRS pour trouver les
chaines qui commencent par la chaine str et retourne les indices
correspondants.

et j'ai donc codé ça :
[j for j in range(len(STRS)) if re.match(str, STRS[j])]

Est-ce qu'il n'est pas possible de faire cela de manière plus propre et
plus performante ? J'ai tenté d'utiliser les fonctions map, filter
where, etc... mais je n'ai rien pondu de valable.

Qu'en pensez-vous ?

<convention>
Par convention, les identifiants en majuscules sont des (pseudo)
constantes...
</convention>

Il faudrait verifier avec le profiler, mais a priori, les expressions
regulières plombent pas mal les perfs. D'une manière générale, préférer
les methodes de l'objet string. Si je reprends ta spec pour strmatch():
-> "> les chaines qui commencent par la chaine str", "".startswith()
devrait suffire.

Sinon, enumerate(seq) permet d'itérer "en parallèle" sur les éléments de
la séquence *et* leur indice:
for indice, item in enumerate(sequence)

bref, une première version serait:

def strmatch(target, strings):
return [i for i, s in enumerate(strings) if s.startswith(target)]

Si tu tiens vraiment à utiliser map, filter et autres, tu peux aussi
faire ça:

def lisp_strmatch(target, strings):
return map(lambda t: t[0],
filter(lambda t: t[1].startswith(target),
enumerate(strings)))


NB : tu peux rendre ces fonctions plus génériques en passant la fonction
discriminante en paramètre:

def xmatch(test, seq):
return [i for i, s in enumerate(seq) if test(s)]

def lisp_xmatch(test, seq):
return map(lambda t: t[0],
filter(lambda t: test(t[1]),
enumerate(seq)))

ce qui permet une troisième version de strmatch():

def xstrmatch(target, strings):
return xmatch(lambda s: s.startswith(target), strings)


Je te laisse le soin de comparer les perfs respectives (le module timeit
est ton ami)

HTH
Bruno

Bruno Desthuilliers wrote:

[j for j in range(len(STRS)) if re.match(str, STRS[j])]

Il faudrait verifier avec le profiler, mais a priori, les expressions

regulières plombent pas mal les perfs. D'une manière générale, préférer
les methodes de l'objet string. Si je reprends ta spec pour strmatch():
-> "> les chaines qui commencent par la chaine str", "".startswith()
devrait suffire.

Sinon, s'il faut vraiment une expression régulière, il est peut-être
intéressant de la compiler une fois pour toute (non testé) :

def strmatch(target, strings):
maregexp = re.compile(target)
return [i for i, s in enumerate(STRS) if maregexp.match(s)]


Ensuite, si les performances sont vraiment un problème, il faut en effet
vérifier dans le profiler et toutes ces sortes de choses. Sinon, ça me
semble acceptable.

Accessoirement, les map, filter, ... sont une autre manière de faire la
même chose avec une approche plus fonctionnelle (d'où le préfixe lisp).
Mais les 'list comprehensions' ne sont pas moins propres et sont
peut-être même plus pythonesque, puisqu'il semble que GvR veuille
supprimer map et consorts de python 3000.

(snip)

Accessoirement, les map, filter, ... sont une autre manière de faire la
même chose avec une approche plus fonctionnelle
(d'où le préfixe lisp).

<mode="j'etale ma science">
les listes en intention viennent aussi de la programmation fonctionelle
(de Haskell, qui est bien plus purement fonctionnel que Common Lisp).
</mode>

Etonnant, non ?-)

Bruno

On Thu, 14 Jul 2005 18:19:53 +0200, Bruno Desthuilliers

Je voulais coder en Python la fonction matlab suivante :
x = strmatch('str', STRS) parcourt le tableau STRS pour trouver les
chaines qui commencent par la chaine str et retourne les indices
correspondants.

et j'ai donc codé ça :
[j for j in range(len(STRS)) if re.match(str, STRS[j])]

Il faudrait verifier avec le profiler, mais a priori, les expressions
regulières plombent pas mal les perfs. D'une manière générale,
préférer les methodes de l'objet string. Si je reprends ta spec pour
strmatch(): -> "> les chaines qui commencent par la chaine str",
"".startswith() devrait suffire.

Bon sang j'avais pourtant bien lu le manuel de long en large et toute la
section sur 'string' et 're' et cela ne m'était même pas venu à l'esprit
de regarder les méthodes de string...
Comme quoi je n'ai pas fini d'apprendre...

Sinon, enumerate(seq) permet d'itérer "en parallèle" sur les éléments
de la séquence *et* leur indice:
for indice, item in enumerate(sequence)

Je ne connaissais pas, merci !
Il n'y a pas de pages regroupant ce genre d'astuces par hasard ?

bref, une première version serait:

def strmatch(target, strings):
return [i for i, s in enumerate(strings) if s.startswith(target)]

Impeccable, je la garde !

Si tu tiens vraiment à utiliser map, filter et autres, tu peux aussi
faire ça:

def lisp_strmatch(target, strings):
return map(lambda t: t[0],
filter(lambda t: t[1].startswith(target),
enumerate(strings)))

Très instructif aussi, je garde cela dans un coin !

NB : tu peux rendre ces fonctions plus génériques en passant la
fonction discriminante en paramètre:

def xmatch(test, seq):
return [i for i, s in enumerate(seq) if test(s)]

def lisp_xmatch(test, seq):
return map(lambda t: t[0],
filter(lambda t: test(t[1]),
enumerate(seq)))

Oui pas bête du tout...

Je te laisse le soin de comparer les perfs respectives (le module
timeit est ton ami)

Je ne cherche pas la performance à tout prix, mais la version que tu
m'as donné en premier a l'énorme avantage de ne pas importer de module
supplémentaire, en plus d'être lisible (car avec map et filter...).
Je la garde donc !

Merci pour toutes ces recommandations !

[j for j in range(len(STRS)) if re.match(str, STRS[j])]

Il faudrait verifier avec le profiler, mais a priori, les

expressions regulières plombent pas mal les perfs. D'une manière
générale, préférer les methodes de l'objet string. Si je reprends
ta spec pour strmatch(): -> "> les chaines qui commencent par la
chaine str", "".startswith() devrait suffire.

Sinon, s'il faut vraiment une expression régulière, il est peut-être
intéressant de la compiler une fois pour toute (non testé) :

def strmatch(target, strings):
maregexp = re.compile(target)
return [i for i, s in enumerate(STRS) if maregexp.match(s)]

Oui c'est même ce qui est recommandé dans le manuel sur 're'

Ensuite, si les performances sont vraiment un problème, il faut en
effet vérifier dans le profiler et toutes ces sortes de choses.
Sinon, ça me semble acceptable.

Moi aussi !

Accessoirement, les map, filter, ... sont une autre manière de faire
la même chose avec une approche plus fonctionnelle (d'où le préfixe
lisp). Mais les 'list comprehensions' ne sont pas moins propres et
sont peut-être même plus pythonesque, puisqu'il semble que GvR
veuille supprimer map et consorts de python 3000.

J'avais lu une page sur l'optimisation des boucles en Python et les
'list comprehensions' étaient moins rapides que les map et filter...
Impossible de retrouver la page cependant...