grepの場合 またはsed オプション--extended-regexpとともに使用されます およびパターン{1,9999} が使用される正規表現の一部である場合、これらのコマンドのパフォーマンスは低くなります。より明確にするために、以下にいくつかのテストを適用します。
-
grep -Eの相対的なパフォーマンス 、egrepおよびsed -Eはほぼ等しいので、grep -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
> real 21m43.947s
テスト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
このパフォーマンスの大きな違いの理由は何ですか？
承認された回答：
時間がかかるのはマッチングではなく、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
割り当ての数は反復回数にほぼ比例しているように見えますが、割り当てられたメモリは指数関数的に増加しているようです。
それは、GNU正規表現の実装方法にかかっています。 GNU grepをコンパイルする場合 CPPFLAGS=-DDEBUG ./configure && makeを使用 、これらのコマンドを実行すると、指数効果が実際に動作していることがわかります。それよりも深く掘り下げるということは、DFAに関する多くの理論を経て、gnulibregexpの実装に飛び込むことを意味します。
ここでは、同じ問題がないように見える代わりにPCREを使用できます：grep -Po '[0-9]{1,65535}' （最大値。ただし、[0-9](?:[0-9]{0,10000}){100}のようなことはいつでも実行できます。 1〜1,000,001回の繰り返しの場合）grep -Po '[0-9]{1,2}'よりも時間もメモリもかかりません 。