question d'optimisation Regex

Question

Comme un exercice d'apprentissage personnel, j'ai écrit ce regex pour diviser une chaîne unaire en plusieurs parties dont la longueur augmente les pouvoirs de deux (see also on ideone.com):

for (String s : 
     new String(new char[500]) 
     .split("(?=(.*))(?<=(?<=(^.*))\\G.*)(?<=(?=\\2\\2.\\1)^.*)") 
    ) { 
     System.out.printf("%s ", s.length()); 
    } 
    // prints "1 2 4 8 16 32 64 128 245 " 

Il utilise une combinaison de capture pendant lookarounds, lookarounds imbriqués, correspondant sur backreferences, et lookbehind longueur infinie (qui n'est pas officiellement pris en charge en Java, mais fonctionne quand même). Les propriétés des sommes de puissances de deux et le fait que la chaîne a un alphabet unaire est également utilisé.

Cette solution est à la fois illisible et a une performance horrible.

Ma question est, comment voulez-vous "optimiser" cette regex?

• Pouvez-vous faire le regex plus lisible (il est normal si elle exécute pire)
• Pouvez-vous faire le regex fonctionne mieux (il est normal si elle est moins lisible)

Answer 1

Je voudrais vraiment pas . Je jetterais le tout et le refaiserais comme un code de procédure lisible.

ne devrait pas faire des choses avec des expressions régulières. C'est l'un d'eux. Je suis tout pour vous éduquer, mais pensez-vous vraiment que ça va être utile à un moment donné?

Peut-être que vous seriez mieux d'apprendre quelque chose qui sera être réellement utilisable et maintenable :-)

Answer 2

Je ne suis pas un gars de Java, donc mes réponses est basée sur la mise en œuvre Regex .NET. J'ai utilisé

"(?<=(^.*)\\G.*)(?<=\\G\\1.)" 

basé sur le fait que \sum_{i=0}^{n} 2^n = 2^{n+1} - 1. Il se lit essentiellement "Correspond à chaque position, pour laquelle la partie après le dernier match est un plus long que la partie avant la dernière correspondance."

Son environ deux fois plus rapide que votre original (sur .NET, encore une fois), en prenant moins de 2 secondes pour diviser 10.000 caractères, et je dirais que c'est un peu plus lisible. Eh bien ... moins illisible. =)

À la votre! Bonne question! =)

Editer: En regardant à nouveau votre Regex, il me semble que vous utilisez la même approche, mais d'une manière plus compliquée. J'avoue que je n'ai pas essayé de lire le vôtre avant d'essayer de faire ma propre solution, à la fois parce que j'aime un défi et parce que votre regex est tout à fait illisible. =) Ces lookarounds imbriqués sont-ils nécessaires à cause du moteur Java regex?

Answer 3

Ce sont des modèles qui ont fonctionné pour moi en Java. Je vais finalement tout réviser en une seule réponse complète avec des explications complètes. Ce sont toutes des représentations littérales de chaîne Java.

• P000: "(?=(.*))(?<=(?<=(^.*))\\G.*)(?<=(?=\\2\\2.\\1)^.*)"
  • motif d'origine
  • 500 en 2.23s (ideone.com), 666 à 4.1s (ideone.com)
• P001: "(?=(.*))(?<=(?<=(^.*))\\G.*)(?<=(?=\\2.\\1)\\G.*)"
  • essentiellement les mêmes que P000, mais au lieu de ^\2\G\2.\1, nous avons coupé la tête juste \G\2.\1
  • 500 dans 2.21s (ideone.com)
• P002: "(?=(.*))(?<=(?<=(^.*))(?=\\2.\\1)\\G.*)"
  • Beaucoup plus lent que P000, mais plus court
  • essentiellement un "refactoring" de P001 maintenant que les deux sont ancrés à assertions arrières \G
  • 400 dans 3.05s (ideone.com)