主页 / ubuntu / 问题 / 960557
Accepted
pa4080
Asked: 2017-09-30 07:29:33 +0800 CST

Grep -E, Sed -E - 使用 '[x]{1,9999}' 时性能低下，但为什么呢？

  • 772

当greporsed与选项一起使用--extended-regexp并且模式{1,9999}是所使用的正则表达式的一部分时，这些命令的性能会降低。为了更清楚，下面应用了一些测试。[1] [2]

  • 和的相对性能几乎相等grep -E，因此只提供了用 进行的测试。egrepsed -Egrep -E

测试 1

$ time grep -E '[0-9]{1,99}' < /dev/null

real    0m0.002s

测试 2

$ time grep -E '[0-9]{1,9999}' < /dev/null

> real    0m0.494s

测试 3

$ time grep -E '[0123456789]{1,9999}' < /dev/null

> 真正的 21 分 43.947 秒

测试 4

$ time grep -E '[0123456789]+' < /dev/null
$ time grep -E '[0123456789]*' < /dev/null
$ time grep -E '[0123456789]{1,}' < /dev/null
$ time grep -P '[0123456789]{1,9999}' < /dev/null

real    0m0.002s

造成这种性能显着差异的原因是什么？

command-line

1 个回答

  1. Best Answer

    请注意，需要时间的不是匹配，而是 RE 的构建。您会发现它也使用了相当多的 RAM：

    $ 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

    alloc 的数量似乎与迭代次数大致成正比，但分配的内存似乎呈指数增长。

    这取决于 GNU 正则表达式的实现方式。如果您使用 编译 GNUgrep并CPPFLAGS=-DDEBUG ./configure && make运行这些命令，您将看到指数效应在起作用。比这更深入意味着要了解很多关于 DFA 的理论并深入研究 gnulib 正则表达式的实现。

    在这里，您可以使用似乎没有相同问题的 PCRE：（grep -Po '[0-9]{1,65535}'尽管您始终可以执行[0-9](?:[0-9]{0,10000}){100}1 到 1,000,001 次重复之类的最大操作）不会比grep -Po '[0-9]{1,2}'.

    • 10

相关问题