Regex оптимизация вопрос

В качестве личного обучения упражнения, я написал это регулярное выражение, чтобы разделить унарную строку на части, длина которых увеличивается полномочия двух (see also on ideone.com):Regex оптимизация вопрос

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 "

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

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

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

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

источник

2010-07-07 polygenelubricants

Я считаю, играть с регулярными выражениями, чтобы быть весело, но это полностью мазохистски – Amarghosh

@Amargosh: было сложно печально писать, пока я не заработал. Затем он стал гедонистическим. – polygenelubricants

Насколько ужасно его производительность на Java? В .NET она разбивает 10-килограммовую буквенную строку в течение 4 секунд. – Jens

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

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

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

источник

2010-07-07 09:31:18 paxdiablo

Должен быть комментарий, но программирование - это не только заработок, но и удовольствие. Обучение для меня забавно. – polygenelubricants

И что вы узнали сегодня? Я узнал (вернее, повторил мою веру), что RE - хороший инструмент, но они не подходят для всего. – paxdiablo

Надеюсь, я узнаю ответы, а не комментарии. Я надеюсь, что Алан Мур придет и спасет день. Или, может быть, у меня будет свой прорыв. – polygenelubricants

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

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

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

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

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

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

источник

2010-07-07 10:25:18 Jens

Да, это точно такая же логика совпадения/арифметики, что и у меня, но более кратким, потому что .NET официально поддерживает бесконечный lookbehind. Это не компилируется на Java (http://ideone.com/wcDRQ). +1 за усилие. Java также не поддерживает обратные ссылки в lookbehind (см. Http://stackoverflow.com/questions/2734977/backreferences-in-lookbehind), но вы можете использовать его в виде, вложенном в lookbehind. Видеть? ТЕПЕРЬ мы все учимся !! знак равно – polygenelubricants

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

Р000: "(?=(.*))(?<=(?<=(^.*))\\G.*)(?<=(?=\\2\\2.\\1)^.*)"
- Оригинальный рисунок
- 500 в 2.23s (ideone.com), 666 в 4.1s (ideone.com)
P001: "(?=(.*))(?<=(?<=(^.*))\\G.*)(?<=(?=\\2.\\1)\\G.*)"
- По существу же, как и P000, но вместо ^\2\G\2.\1, мы отрезали голову, чтобы просто \G\2.\1
- 500 в 2.21s (ideone.com)
P002: "(?=(.*))(?<=(?<=(^.*))(?=\\2.\\1)\\G.*)"
- гораздо медленнее, чем P000, но короче
- По существу «рефакторинг» из P001 теперь, когда оба просмотра назад закреплены на \G
- 400 в 3.05s (ideone.com)

источник

2010-07-07 11:27:25 polygenelubricants

Regex оптимизация вопрос

ответ

Смежные вопросы