11
votes

Regex se comporte paresseux, devrait être gourmand

Je pensais que par défaut mon Regex Strong> présenterait le comportement gourmand que je veux, mais ce n'est pas dans le code suivant: xxx pré>

sortie: P>

Matched in        with in
Matched int       with in
Matched into      with in
Matched internal  with in
Matched interface with in
  • Je veux comprendre pourquoi cela ne fonctionne pas comme prévu et li>
  • le projet réel que je travaille sur a beaucoup plus de mots dans la regex et Il est important de les garder dans ordre alphabétique. LI> ul>

    Donc, ma question est la suivante: pourquoi est-ce paresseux et comment puis-je le réparer? P> P>


4 commentaires

Je ne sais pas si votre utilisation réelle est plus compliquée, mais si l'exemple ci-dessus est en fait ce que vous faites, je pense que vous seriez mille fois mieux à mieux boucler sur votre liste de mots à la recherche de matchs avec la méthode de l'index de la méthode. Si la regex contient simplement un tas de mots dans une alternance, la performance risque probablement.


@JOSH - Non, l'exemple est simplifié. L'application réelle consiste à lire des fichiers de langue pour générer des lexers et des analyseurs de grammaire. Je suis juste un peu rouillé sur ma regex; Mon problème semble si évident maintenant!


@JOSH: Les moteurs Regex peuvent effectuer de nombreuses optimisations pour de tels cas, notamment en écartant de nombreuses vérifications après avoir défaut de faire correspondre un préfixe commun. E.G., si le premier caractère n'est pas "I", aucune des branches commençant par "I" ne serait cochée. Je ne sais pas si le moteur .NET le fait cela, mais je serais surpris si ce n'est pas le cas.


@Max, il construise les transitions de l'état pour accélérer sa correspondance. Si .NET se compare bien à d'autres moteurs de regexs bien établis et bien raffinés, c'est une question de débat sur ce que j'ai rassemblé. Mais cela fonctionne effectivement mieux que l'indexof. (Je suis dirigé à la fois dans des boucles au travail pour prouver pourquoi les collègues devraient utiliser Regex au lieu de l'index de ... Selon ce qui est assorti, vous pouvez obtenir des commandes d'augmentation de la vitesse de magnitude.)


3 Réponses :


12
votes

La paresse et la grofessance s'applique aux quantificateurs uniquement (? , * , + , {min, max} ). Les alternances correspondent toujours à l'ordre et essayez la première correspondance possible.


2 commentaires

Pas d'options autres que la réchrographie? Hrmmm ... Je suppose que je pourrais le ré-commander à la volée afin que je puisse garder la définition dans l'ordre alphabétique ...


@Stomp: Oui, cela peut être fait. Gardez la liste alphabétique dans le programme et juste avant de l'appliquer, vous pouvez le trier par longueur.



3
votes

Selon Regularexpressions.info , les expressions régulières sont désireux . Par conséquent, quand il passe par votre Expression de la canalisation , elle s'arrête sur la première correspondance solide.

Ma recommandation serait de stocker tous vos mots-clés dans une matrice ou une liste, puis générer l'expression triée et canalisée lorsque vous en avez besoin. Vous ne seriez à faire qu'une fois aussi longtemps que votre liste de mots clés ne change pas. Il suffit de stocker l'expression générée dans un singleton de quelque sorte et de retourner sur les exécutions de regex.


1 commentaires

@Jeras - merci pour les liens! Je cherchais sur MSDN et j'ai manqué qu'il cherchait avec impatience le premier match.



6
votes

On dirait que vous essayez de mentionner les choses. Pour ce faire, vous avez besoin que toute l'expression soit correcte, votre actuel n'est pas. Essayez celui-ci à la place ..

new Regex(@"\b(in|int|into|internal|interface)\b");


3 commentaires

Ajout \ b suscitera le comportement souhaité, mais vous vous trompez sur la façon dont cela fonctionne. \ b est une assertion de largeur zéro comme ^ , $ et cherche-champ; Au lieu de faire correspondre un personnage, il correspond à l'écart imaginaire avant ou après un personnage. Le début ou la fin d'une chaîne est automatiquement une limite de mot si le premier ou le dernier caractère (respectivement) est un caractère de mot, votre deuxième regex est donc une version plus verbeuse du premier.


@Alan, j'ai essayé d'exécuter le code et que vous avez clairement raison. Je devrai vérifier le code au travail pour voir ce que nous faisons là-bas ... peut-être que nous utilisons \ w et non \ b. Je sais que nous obtenions des personnages "non-mots" d'une sorte dans une situation similaire où je sais que nous avions une configuration de groupes funky midi-capturant. Pour ce qui est sensible aux paramètres régionaux, cela va être le cas car les frontières de mots seront définies différemment sur la base du rôle de la ponctuation.


@Alan, j'ai modifié ma réponse pour refléter vos commentaires.