パフォーマンスの高い正規表現の作成

J パフォーマンスの高い正規表現の作成

ここでは、パフォーマンスの高い正規表現を作成するときに考慮する必要がある重要な側面について説明します。

文字クラス

文字クラスは、一致を試行している、または一致しない文字を指定します。 .*sの.をより具体的な文字に置き換えてください。 .*では、入力の終わりまで常に移動してから、以前に保存した状態に戻り、一致の検索を続行します。特定の文字クラスを使用する場合、*が正規表現エンジンを使用する文字数を制御できるため、激しいバックトラックを停止するパワーが得られます。

次の正規表現の例を考えてみます:

(\d{4})(\d{2})(\d{2}),(\S+),([\S\s]*),([\S\s]*),([\S\s]*),([\S\s]*),([\S\s]*),([\S\s]*),([\S\s]*),([\S\s]*),([\S\s]*),([\S\s]*),([0-9.]+),([0-9.]+),([0-9.]+),([0-9.]+),([0-9.]+),([0-9.]+)

次の入力の場合:

20150220,201502,16798186260,tvN,Entertainment/Music,Female,67,2,Individual,ollehtv Economic,Commercial Housing,5587,0,2,0,1,1

指定した正規表現の結果、一致は後方に実行されます。この状況はOracle Log Analyticsによって検出され、一致操作は中断されます。

次の例の正規表現を変更することによって、一致がより高速であることを確認できます。不要なバック・トラッキングが回避されるように、[\S\s]*が[^,]に変更されていることに注意してください。

(\d{4})(\d{2})(\d{2}),(\S+),([^,]*),([^,]*),([^,]*),([^,]*),([^,]*),([^,]*),([^,]*),([^,]*),([^,]*),([^,]*),([0-9.]+),([0-9.]+),([0-9.]+),([0-9.]+),([0-9.]+),([0-9.]+)

怠惰量指定子

多くの正規表現で、欲張り量指定子(.*s)は、怠惰量指定子(.*?s)で安全に置き換えることができるため、結果を変更せずにパフォーマンスをブーストできます。

次の入力について考えてみます:

Trace file /u01/app/oracle/diag/rdbms/navisdb/NAVISDB/trace/NAVISDB_arc0_3941.trc
Oracle Database 11g Enterprise Edition Release 11.2.0.1.0 - 64bit Production
With the Partitioning, OLAP, Data Mining and Real Application Testing options
ORACLE_HOME = /u01/app/oracle/product/11.2.0/db_1
System name: Linux
Node name: NAVISDB
Release: 2.6.18-308.el5
Version: #1 SMP Fri Jan 27 17:17:51 EST 2012
Machine: x86_64
Instance name: NAVISDB
Redo thread mounted by this instance: 1
Oracle process number: 21
Unix process pid: 3941, image: oracle@NAVISDB (ARC0)

指定された入力に対して次の欲張り正規表現を考えてみます:

Trace\sfile\s(\S*).*ORACLE_HOME\s*[:=]\s*(\S*).*System\sname:\s*(\S*).*Node\sname:\s*(\S*).*Release:\s*(\S*).*Machine:\s*(\S*).*Instance\sname:\s*(\S*).*Redo\sthread\smounted\sby\sthis\sinstance:\s(\d*).*Oracle\sprocess\snumber:\s*(\d*).*Unix\sprocess\spid:\s(\d*).*image:\s+([^\n\r]*)

この正規表現は、.*.に出会うたびに、入力の最後まで一致します。 .*が表示される最初の時点は、すべての入力を消費し、ORACLE_HOMEに到達するまでバック・トラックします。これは、非効率的な照合方法です。怠惰正規表現は次のとおりです:

Trace\sfileRelease:\s*(\S*).*?Machine:\s*(\S*).*?Instance\sname:\s*(\S*).*?Redo\sthread\smounted\sby\sthis\sinstance:\s(\d*).*?Oracle\sprocess\snumber:\s*(\d*).*?Unix\sprocess\spid:\s(\d*).*?image:\s+([^\n\r]*)

上の怠惰正規表現は、文字列の先頭から開始してORACLE_HOMEに達するまで使用し、その後に文字列の残りの部分と一致するように処理できます。

ノート: ORACLE_HOMEフィールドが入力の最初の方に表示される場合は、怠惰量指定子を使用する必要があります。末尾に向けてORACLE_HOMEフィールドが表示される場合、欲張り量指定子を使用することが適切な場合があります。

アンカー

アンカーは、カーソルが入力の特定の場所にあることを意図している正規表現エンジンを示します。最も一般的なアンカーは、入力の開始と終了を示す ^および$です。

IPv4アドレスを検出するために、次の正規表現を考慮してください:

\d{1,3}\.d{1,3}.\d{1,3}.\d{1,3}

^\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3}

^で始まる2番目の正規表現は、入力の最初に出現するIPアドレスについて固有であることに注意してください。

次の例のような入力で正規表現を検索しています:

107.21.20.1 - - [07/Dec/2012:18:55:53 -0500] "GET
      /extension/bsupport/design/cl/images/btn_letschat.png HTTP/1.1" 200
    2144

一致しない入力は、次の例のようになります:

[07/Dec/2012:23:57:13 +0000] 1354924633 GET "/favicon.ico" "" HTTP/1.1 200 82726 "-"
      "ELB-HealthChecker/1.0"

^で始まる2番目の正規表現は、一致しない入力が即時に破棄されるため、一致しない入力よりも高速に実行されます。

代替の重要度

代替の順序では、より一般的なオプションを前面に配置して、より高速に一致させることができます。よりまれなオプションが最初に配置された場合、正規表現エンジンは、より一般的なオプションが成功したかどうかをチェックする前に、それらのチェックに時間を浪費します。また、一般的なパターンを抽出してみてください。たとえば、(abcd|abef)ではなくab(cd|ef)が使用されます。

次の正規表現をみてください:

{TIMEDATE}\s{0,1}:\s*(?:|\[)(\w+)(?:\:|\])(?:\[|)(\d+)(?:\:|\])(.{1,1000}).*

{TIMEDATE}\s{0,1}:\s*(?:\[|)(\w+)(?:\:|\])(?:\[|)(\d+)(?:\:|\])(.{1,1000}).*

次の入力で:

2014-06-16 12:13:46.743: [UiServer][1166092608] {0:7:2} Done for
ctx=0x2aaab45d8330

2つ目の正規表現は、nullに続く文字[を最初に検索するので、高速一致になります。入力に[があるため、一致がより高速に実行されます。