Вопрос оптимизации Regex

Question

В качестве личного упражнения я написал это регулярное выражение, чтобы разбить унарную строку на части, длина которых увеличивается в два раза ( см. Также на 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 "

При этом используется комбинация захвата при поиске, вложенных поисков, сопоставления по обратным ссылкам и просмотра с бесконечной длиной (который официально не поддерживается в Java, но работает в любом случае). Свойства сумм степеней двойки и тот факт, что строка имеет одинарный алфавит, также используются в качестве преимущества.

Это решение нечитаемо и имеет ужасную производительность.

Мой вопрос: как бы вы "оптимизировали" это регулярное выражение?

• Можете ли вы сделать регулярное выражение более читабельным (нормально, если оно работает хуже)
• Можете ли вы сделать так, чтобы регулярное выражение работало лучше (нормально, если оно менее читабельно)

Answer 1

Я не парень по Java, поэтому мои ответы основаны на реализации .NET Regex. Я использовал

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

исходя из того, что \sum_{i=0}^{n} 2^n = 2^{n+1} - 1. Он в основном гласит: «Сопоставить каждую позицию, для которой деталь после последнего совпадения на единицу длиннее, чем деталь перед последним совпадением».

Это примерно в два раза быстрее, чем ваш оригинал (опять же в .NET), на разделение 10.000 символов уходит менее 2 секунд, и я бы сказал, что он немного более читабелен. Ну ... менее нечитабельно. =)

Ура! Хороший вопрос! =)

Редактировать: Снова глядя на свое регулярное выражение, мне кажется, что вы используете тот же подход, но более сложным образом. Я признаю, что я не пытался прочитать ваше, прежде чем пытаться найти свое собственное решение, и потому, что мне нравится вызов, и потому что ваше регулярное выражение совершенно нечитаемо. знак равно Являются ли эти вложенные обходные пути необходимыми из-за механизма регулярных выражений Java?

Answer 2

Я бы не стал.Я бы выбросил все это и переделал бы его как читаемый процедурный код.

Есть некоторые вещи, которые вы действительно не должны делать с регулярными выражениями.Это одна из них.Я все для самообразования, но вы действительно думаете, что это пригодится в какой-то момент?

Возможно, вам лучше узнать что-то, что будет действительно пригодным для использования и обслуживания: -)

Answer 3

Это шаблоны, которые работали для меня в Java. В конце концов я все пересмотрю в один исчерпывающий ответ с ПОЛНЫМИ объяснениями. Это все строковые литеральные представления Java.

• P000: "(?=(.*))(?<=(?<=(^.*))\\G.*)(?<=(?=\\2\\2.\\1)^.*)"
  • Оригинальный узор
  • 500 за 2,23 с ( ideone.com ), 666 за 4,1 с ( ideone.com )
• P001: "(?=(.*))(?<=(?<=(^.*))\\G.*)(?<=(?=\\2.\\1)\\G.*)"
  • По сути то же самое, что и P000, но вместо ^\2\G\2.\1 мы отрезаем голову до \G\2.\1
  • 500 за 2,21 с ( ideone.com )
• P002: "(?=(.*))(?<=(?<=(^.*))(?=\\2.\\1)\\G.*)"
  • намного медленнее, чем P000, но короче
  • По сути, это «рефакторинг» P001 теперь, когда оба видовых элемента закреплены на \G
  • 400 за 3,05 с ( ideone.com )