Вопрос о жадных и отрицательных классах символов в Regex

Question

У меня очень большой файл, который выглядит так (см. Ниже). У меня есть два основных варианта регулярного выражения для использования на нем (я знаю, что могут быть другие, но я действительно пытаюсь сравнить методы Greedy и Negated Char Class).

ftp: [^\D]{1,} 
ftp: (\d)+ 
ftp: \d+ 

Примечание: если я снял parense вокруг \ д?

Теперь + является жадным, который заставляет возвращаться назад, но Negated Char Class требует сравнения char-by-char. Что более эффективно? Предположим, что файл очень-очень большой, поэтому небольшие различия в использовании процессора будут преувеличены из-за длины файла.

Теперь, когда вы ответили на это, что, если мой отрицательный класс Char был очень большим, скажем, 18 разных персонажей? Это изменит ваш ответ?

Спасибо.

FTP: 1117 байтов
FTP: 5696 байтов
FTP: 3207 байтов
FTP: 5696 байтов
FTP: 7200 байт

Answer 1

Оба ваши выражения имеют одинаковую жадность. Как говорили другие, кроме группы захвата, они будут выполнять точно так же.

Также в этом случае жадность не имеет большого значения при скорости выполнения, так как у вас нет ничего следующего за \ d *. В этом случае выражение просто обрабатывает все цифры, которые он может найти, и останавливается, когда пространство встречается. Эти выражения не должны возникать.

Чтобы сделать его более явным, возвраты должны произойти, если у вас есть выражение, как это:

\d*123 

В этом случае анализатор поглотит все цифры, а затем вернуться назад, чтобы соответствовать три следующим цифрам.

Answer 2

не прямой ответ на вопрос, но почему не совсем другой подход, поскольку вы уже знаете формат строк? Например, вы можете использовать регулярное выражение в пробеле между полями или вообще не использовать регулярное выражение и split() в пробеле, что обычно будет быстрее, чем любое регулярное выражение, в зависимости от языка, который вы используете.

Answer 3

[^ \ D] {1,} и \ d + - это точно то же самое. Парсер регулярного выражения будет компилировать [^ \ D] и \ d в классы символов с равным содержимым, а + - только для {1}.

Если вы хотите ленивого повторения, вы можете добавить? в конце.

\d+? 

Классы символов обычно скомпилированы в растровые изображения для символов ASCII. Для Unicode (> = 256) это зависит от реализации. Один из способов - создать список диапазонов и использовать на нем двоичный поиск.

Для ASCII время поиска постоянное по размеру. Для Unicode он логарифмический или линейный.

Answer 4

Мои первоначальные тесты показали, что [^ \ D {1} немного медленнее, чем \ D +, в файле с 184m бывший занимает 9,6 секунд, в то время как последний занимает 8,2

Без захвата (()» s), то они примерно на 1 секунду быстрее, но разница между ними примерно одинакова.

Я также сделал более обширное испытание, когда захваченное значение выводится в/DEV/нуль, с третьей версии расщепления на пространстве, результаты:

([^\D]{1,}): ~18s 
(\d+): ~17s 
(split//)[1]: ~17s 

Edit: сплит версии улучшилось и время сократилось до быть тем же или ниже, чем (\ d +)

Самая быстрая версия до сих пор (может ли кто-нибудь улучшить?):

while (<>) 
{ 
    if ($foo = (split//)[1]) 
    { 
     print $foo . "\n"; 
    } 
} 

Answer 5

Это своего рода трюк вопрос, как написано, потому что (\ d) + занимает немного больше времени из-за накладных расходов, захватывающих скобок. Если вы измените его на \ d +, они возьмут столько же времени в моем perl/system.

Answer 6

Да, я согласен с MizardX ... эти два выражения семантически эквивалентны. Хотя для группировки могут потребоваться дополнительные ресурсы. Это не то, о чем вы просили.