Grep -E, Sed -E - низкая производительность при использовании «[x] {1,9999}», но почему?
В зависимости от того, что вы хотите сделать с выходным файлом, можно добавить цвета в обычный текстовый файл, потому что цвета просто исходят от некоторых специальных символов. Греп, похоже, не хочет печатать их при перенаправлении его в файл, поэтому вам нужно заставить его:
grep --color=always "stuff" input.txt > output.txt
Теперь, когда вы печатаете файл на консоли, он будет напечатан с помощью цвета, потому что Bash интерпретирует эти символы как «использовать этот цвет».
cat output.txt
Однако, если вы откроете его в редакторе, например vim, вы получите некоторые странные символы. Например, когда я использую команды
echo "A sentence. A red sentence. Another sentence." \
| grep --color=always "A red sentence" > output.txt
Выход выглядит правильно, когда я печатаю его с помощью cat, но когда я его открываю в vim, я получаю
A sentence. ^[[01;31m^[[KA red sentence^[[m^[[K. Another sentence.
2 ответа
Обратите внимание, что это не соответствие, требующее времени, но построение RE. Вы обнаружите, что он использует довольно много оперативной памяти:
$ valgrind grep -Eo '[0-9]{1,9999}' < /dev/null
==6518== HEAP SUMMARY:
==6518== in use at exit: 1,603,530,656 bytes in 60,013 blocks
==6518== total heap usage: 123,613 allocs, 63,600 frees, 1,612,381,621 bytes allocated
$ valgrind grep -Eo '[0-9]{1,99}' < /dev/null
==6578== in use at exit: 242,028 bytes in 613 blocks
==6578== total heap usage: 1,459 allocs, 846 frees, 362,387 bytes allocated
$ valgrind grep -Eo '[0-9]{1,999}' < /dev/null
==6594== HEAP SUMMARY:
==6594== in use at exit: 16,429,496 bytes in 6,013 blocks
==6594== total heap usage: 12,586 allocs, 6,573 frees, 17,378,572 bytes allocated
Количество выделов кажется примерно пропорциональным числу итераций, но выделенная память, кажется, растет экспоненциально. [!d1 ]
Это не так, как реализуются регулярные выражения GNU. Если вы скомпилируете GNU grep с CPPFLAGS=-DDEBUG ./configure && make и запустите эти команды, вы увидите экспоненциальный эффект в действии. Идя глубже, чем это означало бы пройти много теории по DFA и погрузиться в реализацию gnulib regexp.
Здесь вы можете использовать PCRE вместо этого, похоже, не имеет такой же проблемы: grep -Po '[0-9]{1,65535}' (максимум, хотя вы всегда можете делать такие вещи, как [0-9](?:[0-9]{0,10000}){100} для от 1 до 1000,001 повторений) не занимает больше времени или памяти, чем grep -Po '[0-9]{1,2}'.
-
1Есть ли способ обойти это? – Sergiy Kolodyazhnyy 30 September 2017 в 00:56
-
2@SergiyKolodyazhnyy, вы можете использовать grep -Po '[0-9]{1,9999}, который, похоже, не имеет проблемы. – Stéphane Chazelas 30 September 2017 в 01:10
-
3Это не только в sed -E или grep -E, но в awk также имеет эту низкую производительность (о последней команде awk). возможно, awk также не может использовать PCRE? – αғsнιη 25 October 2017 в 07:25
Обратите внимание, что это не соответствие, требующее времени, но построение RE. Вы обнаружите, что он использует довольно много оперативной памяти:
$ valgrind grep -Eo '[0-9]{1,9999}' < /dev/null
==6518== HEAP SUMMARY:
==6518== in use at exit: 1,603,530,656 bytes in 60,013 blocks
==6518== total heap usage: 123,613 allocs, 63,600 frees, 1,612,381,621 bytes allocated
$ valgrind grep -Eo '[0-9]{1,99}' < /dev/null
==6578== in use at exit: 242,028 bytes in 613 blocks
==6578== total heap usage: 1,459 allocs, 846 frees, 362,387 bytes allocated
$ valgrind grep -Eo '[0-9]{1,999}' < /dev/null
==6594== HEAP SUMMARY:
==6594== in use at exit: 16,429,496 bytes in 6,013 blocks
==6594== total heap usage: 12,586 allocs, 6,573 frees, 17,378,572 bytes allocated
Количество выделов кажется примерно пропорциональным числу итераций, но выделенная память, кажется, растет экспоненциально.
Это не так, как реализуются регулярные выражения GNU. Если вы скомпилируете GNU grep с CPPFLAGS=-DDEBUG ./configure && make и запустите эти команды, вы увидите экспоненциальный эффект в действии. Идя глубже, чем это означало бы пройти много теории по DFA и погрузиться в реализацию gnulib regexp.
Здесь вы можете использовать PCRE вместо этого, похоже, не имеет такой же проблемы: grep -Po '[0-9]{1,65535}' (максимум, хотя вы всегда можете делать такие вещи, как [0-9](?:[0-9]{0,10000}){100} для от 1 до 1000,001 повторений) не занимает больше времени или памяти, чем grep -Po '[0-9]{1,2}'.