[Moscow.pm] Регулярные выражения. Помогите понять, почему так.

[Динар Жамалиев]

Пример того, сколько раз с какой позиции ведется поиск, возвраты
генерируются последним квантификатором \s*:
#-----
    $str = "1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1";
    $r = '3\s*?(?:[^a-z]\s*?)+?r';

    for $i ( 1 .. 16 ){
        ( $ii1, $ii2, $ii3, $ii4, $ii5 ) = 0;
        $prefix = ($r x $i).'';

        #|      /$prefix|2\s*?(?:[^a-z]\s*?)+?r/;
        $str =~ /$prefix|2(?{ $ii1++ })\s*?(?{ $ii2++ })(?:[^a-z](?{ $ii3++
})\s*?(?{ $ii4++ }))+?(?{ $ii5++ })r/;

        print "$i| $ii1:$ii2:$ii3:$ii4:$ii5\n"
    }
#-----

результат:

1| 1:2:148:213:163
2| 1:2:188:265:219
3| 1:2:230:321:275
4| 1:2:272:377:331
5| 1:2:315:435:387
6| 1:2:356:489:443
7| 1:2:398:545:499
8| 1:2:440:601:555
9| 1:2:484:661:611
10| 1:2:524:713:667
11| 1:2:566:769:723
12| 1:2:608:825:779
13| 1:2:650:881:835
14| 1:2:692:937:891
15| 1:2:201326589:268435451:268435451
16| 1:2:201326589:268435451:268435451

экспонента именно по числу возвратов/попыток

29 октября 2016 г., 13:28 пользователь Динар Жамалиев <zhdinar на gmail.com>
написал:

> вернее такие шаблоны выдают идентичный результат
>  /bla\s*?bla/ и
>  /bla\s+?bla/
>
> 29 октября 2016 г., 13:13 пользователь Динар Жамалиев <zhdinar на gmail.com>
> написал:
>
> Ясно изъясняться не моя фишка. Под сутью я имел другое. Для примера в
>> контексте строки вида
>>  "bla bla bla"
>> шаблоны вида
>>  /bla\s*?/ и
>>  /bla\s+?/ и
>> идентичны в том смысле, что подстрока "bla " все равно будет найдена, не
>> так ли?
>>
>> 29 октября 2016 г., 2:41 пользователь Loginoff Nick via Moscow-pm <
>> moscow-pm на pm.org> написал:
>>
>> \s* != \s+ - так что это очень сильно меняет суть шаблона. В данном
>>> контексте пробела может и не быть... Так что это не решает проблему
>>>
>>> 28.10.2016, 21:44, "Динар Жамалиев via Moscow-pm" <moscow-pm на pm.org>:
>>>
>>> Если везде заменить \s* на \s+, что не меняет сути шаблона, результат
>>> будет мгновенным, так как квантификатор +? не отступает назад, захват либо
>>> есть максимально возможный, либо нет. В то время как *? сначала захватывает
>>> все, затем отступает Каждый дополнительный * значительно увеличивает число
>>> комбинаций. В твоем случае 16й элемент приводит к экспоненциальному
>>> увеличению возможных комбинаций
>>>
>>> 28 октября 2016 г., 22:30 пользователь Artem Zhuravlev via Moscow-pm <
>>> moscow-pm на pm.org> написал:
>>>
>>> Тут скорее дело в Захвате и построение обратных ссылок для них, на 16+
>>> явно замедляется
>>>
>>>
>>> Вот переменная без захватом отработает быстро
>>> my $regexp16 = qr('
>>> (?:3\s*?(?:[^a-z]\s*?)+?r)
>>> |(?:3\s*?(?:[^a-z]\s*?)+?r)
>>> |(?:3\s*?(?:[^a-z]\s*?)+?r)
>>> |(?:3\s*?(?:[^a-z]\s*?)+?r)
>>> |(?:3\s*?(?:[^a-z]\s*?)+?r)
>>> |(?:3\s*?(?:[^a-z]\s*?)+?r)
>>> |(?:3\s*?(?:[^a-z]\s*?)+?r)
>>> |(?:3\s*?(?:[^a-z]\s*?)+?r)
>>> |(?:3\s*?(?:[^a-z]\s*?)+?r)
>>> |(?:3\s*?(?:[^a-z]\s*?)+?r)
>>> |(?:3\s*?(?:[^a-z]\s*?)+?r)
>>> |(?:3\s*?(?:[^a-z]\s*?)+?r)
>>> |(?:3\s*?(?:[^a-z]\s*?)+?r)
>>> |(?:3\s*?(?:[^a-z]\s*?)+?r)
>>> |(?:3\s*?(?:[^a-z]\s*?)+?r)
>>> |(?:2\s*?(?:[^a-z]\s*?)+?r)
>>> ');
>>>
>>>
>>> Так что думаю стоит уменьшить количество захватов.
>>>
>>> Ну или как в книге пишут если можно то
>>>
>>> вместо /a|b/
>>>
>>> пишите /a/ || /b/
>>>
>>>
>>> --
>>> Moscow.pm mailing list
>>> moscow-pm на pm.org | http://moscow.pm.org
>>>
>>>
>>> ,--
>>> Moscow.pm mailing list
>>> moscow-pm на pm.org | http://moscow.pm.org
>>>
>>>
>>>
>>> --
>>> С Уважением, Login|off Nick или STork.
>>>
>>>
>>> --
>>> Moscow.pm mailing list
>>> moscow-pm на pm.org | http://moscow.pm.org
>>>
>>>
>>
>
----------- следущая часть -----------
Вложение в формате HTML было извлечено…
URL: <http://mail.pm.org/pipermail/moscow-pm/attachments/20161029/2ead0bc6/attachment-0001.html>