Optimisation de regexp et autres...

Répondre


Cette question est un moyen d’empêcher des soumissions automatisées de formulaires par des robots.
Smileys
:D :) :( :o :shock: :? 8-) :lol: :x :P :oops: :cry: :evil: :twisted: :roll: :wink: :!: :?: :idea: :arrow: :| :mrgreen: =D> #-o =P~ :^o :non: :priere: 8-|
Voir plus de smileys
  Revue du sujet
 

  Étendre la vue Revue du sujet : Optimisation de regexp et autres...

par SpintroniK » 11 mai 2009, 17:02

Hum... en effet ça à l'air intéressant :
S
Lorsqu'un masque est utilisé plusieurs fois, cela vaut la peine de passer quelques instants de plus pour l'analyser et optimiser le code pour accélérer les traitements ultérieurs. Cette option force cette analyse plus poussée. Actuellement, cette analyse n'est utile que pour les masques non ancrés, qui ne commencent pas par un caractère fixe.
(source : http://fr2.php.net/manual/fr/reference. ... ifiers.php)

Sinon, il y a quelques conseils d'optimisation ici :
(tout en bas)
http://fr2.php.net/manual/fr/reference. ... ifiers.php

par Hywan » 11 mai 2009, 16:26

Hmm possible en effet. On peut le comprendre de cette façon :-). Bien vu !
Il faudrait regarder le moteur PCRE pour voir si ça fonctionne bien comme ça, mais je suis pris d'une grosse flemme …

par Calimero » 11 mai 2009, 16:20

J'ai pas été voir dans le code source pour en être sûr, mais l'extrait du manuel que j'ai copié (cf parties en gras) laisse deviner l'utilisation d'un système de cache derrière (en tout cas c'est comme cela que je l'avais compris).

par Hywan » 11 mai 2009, 16:14

Il utilise une autre façon d'analyser les expressions mais pas de système de cache.

par Calimero » 11 mai 2009, 15:51

Ta remarque sur les compilations uniques rejoint mon intervention sur le cache d'expression régulière. Perl les compile et les stocke en mémoire. J'aimerais bien que PHP en fasse autant …
Y'a pas un modifieur à cet effet justement ? le S si j'ai bonne mémoire...
When a pattern is going to be used several times, it is worth spending more time analyzing it in order to speed up the time taken for matching. If this modifier is set, then this extra analysis is performed. At present, studying a pattern is useful only for non-anchored patterns that do not have a single fixed starting character.

par Hywan » 11 mai 2009, 13:49

Ta remarque sur les compilations uniques rejoint mon intervention sur le cache d'expression régulière. Perl les compile et les stocke en mémoire. J'aimerais bien que PHP en fasse autant …

par mojorisin » 11 mai 2009, 13:34

Une des choses qui ne sont pas porté depuis perl et qui serait pourtant intéressant à avoir sous le coude c'est le principe de compilation unique des regexp avec le modificateur o: /motif/o.
Avec ce modificateur le moteur de regexp compile la regexp une fois et une seule fois pour le script courant ce qui permet un gain de temps lors de certains traitements.
Biensur il ne faut pas a voir de variable interpolé dans l'expression régulière :)

Après sur la rapidité, je pense que si une expression est façonnée correctement ceal reste rapide. Le plus couteux dans les regexp sont les retours arrières du moteur ainsi que les captures de motifs.

Il ne faut donc pas insérer de parenthèses capturantes si on a pas besoin d'exploiter les données, les regroupement s sans capture peuvent être fait avec la construction (?:).
Il faut de même avoir en tête que les quantificateurs son par défaut avides (il essaieront de reconnaître le plus de caractères possible)

En brefs les règles des expressions régulières sont :
- La première reconnaissance gagne (la reconnaissance qui commence le plus tôt dans une chaîne est toujours préférée à une autre reconnaissance plus loin dans la chaine)
Cette règle est suivie de la manière suivante : la première tentative de reconnaissance commence avec le premier caractère et ce pour chaque permutation de la regexp. Si le moteur échoue dans la reconnaissance, il recommence en se décalant d'un caractère vers la droite. Ces tentatives sont répètées dans la chaîne jusqu'a ce que une réusisse, ou que le moteur ait atteint la fin de la chaîne.
- Les quantificateurs sont avides (les quantificateurs reconnaissent toujours le plus de texte possible)
La seule situation ou ils ne se comportent pas de cette manière est le cas ou leur avidité ferait échouer la reconnaissance, dans ce cas la, a cause de la troisieme regle, ils "relacheront" des caractères (un par un)
- La reconnaissance globale prédomine
Le moteur de regexp fera tout pour que la globalité de l'expression régulière réussisse.

Exemple avec la phrase : "Jeannette dit bonjour sans ses lunettes de jour"

en recherchant le motif jour la reconnaissance se fait à bonjour
en recherchant le motif sans|jour|dit la reconnaissance se fera à Jeannette dit bonjour sans ses lunettes de jour
en recherchant le motif .*lunettes de jour le moteur reconnatira alors successivement ;
Jeannette dit bonjour sans ses lunettes de jour
Jeannette dit bonjour sans ses lunettes de jour
Jeannette dit bonjour sans ses lunettes de jour
jusqua ce que le moteur trouve une correspondance soit environ une vingtaine de tentative

Sujet vaste et passionnant, je vous recommande le livre "Mastering Regular Expression" de Jeffrey E. F. Friedl aux édition O'reilly qui doit être la bible sur le sujet :)

Petite (moyenne ?) contribution au passage.

par Hywan » 11 mai 2009, 09:50

Très juste, j'avais omis cet aspect ;-).

par Sékiltoyai » 11 mai 2009, 01:58

Les références diffèrent des pointeurs de par le fait qu'il y a une gestion du garbage collector.
Une variable non référencée en PHP a un compteur de référence de 1, et n'a qu'un identifiant pointant vers la valeur.
Du moment ou l'on fait une référence (passage par référence, affectation par référence), on augmente un compteur de référence et on a un nouvel identifiant pointant vers cette variable.
Ce mécanisme permet au garbage collector de désallouer les ressources. Lorsque l'on détruit une variable, on réduit son compteur de référence. Si celui-ci est à zéro, on libère l'espace mémoire.
C'est pour cette raison que l'on ne peut directement assimiler une référence à un pointeur, puisque toute variable en PHP est une référence, et que les références font intervenir la gestion de la mémoire, contrairement aux pointeurs, qui demandent clairement une allocation manuelle de la mémoire.

par Nagol » 11 mai 2009, 01:46

yap.

merci professeur HyWaN.

par Hywan » 10 mai 2009, 23:25

Hmm, techniquement parlant, une référence est un pointeur, ça ne change rien. C'est juste un nom et une notation différente. D'ailleurs, je préfère mille fois les pointeurs aux références, tellement plus simple à gérer.

Donc PHP n'utilise pas des références partout, seulement pour les objets.

Pour les fonctions, écrire
$var = f($var);
n'est pas strictement équiavalent à
f(&$var);
(D'ailleurs, on n'écrit plus f(&$var); mais function f ( &$arg ) { ... } f($var); c'est plus correct). En fait, dans le premier cas, il attend le résultat avant décraser la valeur de la variable, alors que dans le second, le traitement est direct. Pas besoin de passer par une variable intermédiaire (cette valeur est en fait une copie de la première).

C'est pour ça qu'on parle de passage par adresse ou par copie de valeur. Soit on donne l'adresse (l'emplacement en mémoire) de la donnée, soit on donne la donnée elle-même. Dans le premier cas, on travaille toujours sur le même espace mémoire, alors que dans le second, on copie, donc on duplique, puis on travaille sur la copie. Dans le cas d'objet lourd, on comprend que c'est trop lent. Pareil pour d'énorme chaînes de caractères.

Pour ton exemple de file_get_contents(), si le fichier est trop lourd, le résultat le sera d'autant en mémoire, donc une erreur sera levée disant que la mémoire est pleine. On ne sait pas faire le lien entre un fichier et programme sans copier les données du fichier en mémoire (ou sinon, c'est extrêmement lent).

Est-ce que j'ai répondu à la question (car je n'en suis pas sûr :-P) ?

Une petite note intéressante (exercice 1, a ;-)), voici plusieurs notations qui sont toutes différentes :
function  f (  $arg ) { ... }
function  g ( &$arg ) { ... }
function &h (  $arg ) { ... }
Elles ont toutes des comportements différents et sont utiles dans des cas différents. La première est normale : entrée et sortie (paramètre et retour) sont copiées. La deuxième : entrée pointée et sortie copiée. La dernière : entrée copiée et sortie pointée.

Je comprends en fait ta philosophie de style de codage. C'est vrai que c'est un aspect. Soit on retourne les valeurs, soit on passe une variable en référence qui va recevoir le résultat. On trouve souvent ça en C. Mais c'est un cas particulier (si j'ose dire) des références. C'est une application possible, mais la philosophie qui est derrière est plus balèze en fait. Est-ce que tu comprends ('suis fatigué là ...) ?

par Nagol » 10 mai 2009, 19:51

À Nagol : une référence est une adresse, soit 32 ou 64 bits de nos jours, soit 1 ou 2 octets. C'est plus léger qu'un passage par copie de valeur, pour sûr. Pour ceux qui se posent la question de qu'est-ce qu'une référence, il ne faut pas chercher bien loin, c'est un pointeur, tout bêtement (même en C). Mais ce n'est pas tellement présent dans la philosophie de PHP que d'utiliser des références (sauf pour les objets qui le sont automatiquement depuis PHP 5). On utilise un langage de haut-niveau, donc on laisse le bas-niveau à l'interpréteur. Tu as raison sur ce point :-).
Justement il me semblait que le passage en référence n'a rien à voir avec un pointeur, j'avais cru comprendre qu'il s'agissait de toute maniere d'une allocation en ram systématique sur les variables, cad que toutes les variables php sont des pointeurs. un exemple concret fais un file_get_contents sur un fichier qui fait 500mo et tu auras un fatal error maximum memory allocation machinchose. par la meme qu'est ce qui differe un $var = func($var); d'un func(&$var); logiquement rien, uniquement du coding style puisque la variable est de toute manière allouée.

par Hywan » 10 mai 2009, 18:17

Je n'aimerais pas te faire de la peine Katagoto, mais tu formules tellement mal tes questions ou réponses que ça ne me donne pas envie de les lire.
Je n'écris pas des pavés, j'explique les choses. Si tu comptes tout apprendre en lisant un SMS en diagonal, tu te trompes.
Tu m'es très désagréable et tes interventions inutiles. Merci de t'abstenir.

À Nagol : une référence est une adresse. C'est plus léger qu'un passage par copie de valeur, pour sûr. Pour ceux qui se posent la question de qu'est-ce qu'une référence, il ne faut pas chercher bien loin, c'est un pointeur, tout bêtement (même en C). Mais ce n'est pas tellement présent dans la philosophie de PHP que d'utiliser des références (sauf pour les objets qui le sont automatiquement depuis PHP 5). On utilise un langage de haut-niveau, donc on laisse le bas-niveau à l'interpréteur. Tu as raison sur ce point :-).

par Nagol » 10 mai 2009, 18:09

À Nagol : qu'est-ce que tu appelles le toolset ?
littéralement boite à outil, ca se comprend non? quand on programme on a plusieurs choix pour faire une même chose, le passage en référence pour moi est strictement équivalent au non-passage en référence, ce n'est qu'une façon de programmer, ais-je raison de penser cela maître HyWaN (plus connu sous le nom de michel chevalet)

par katagoto » 10 mai 2009, 17:19

Escusez moi


Pour apporter ma pierre à l'édifice, j'ai lut sur le livre PHP 5
avancé, à la fin du chapitre que pour les structure contenant
de | (ou pipe), il valait mieux positionner les possibilités par
probabilité d'apparition, du plus au moins.