正規表現

Iが（私は数十ルータ数千の平均大きいことにより）、大きなISPネットワークに接続するルータから、サポートされていない物理インターフェイス/サブインターフェイスを破棄するために、次のコードを使用してい

を最適化GigabitEthernet2/11.2000 正規表現

GigabitEthernet1/2-MPLS層

FastEthernet6/0/3.2000-802.1Qため

未配線VLAN 2000のようなエントリを破棄されますvLAN subif

このコードは、キャッシュが本当に新しいサブインターフェイスが設定されているので、どちらか/非常に捨てあまり役に立ちません（一部のルータが50K + subintefacesを持っている）インタフェースの巨大なセットの上に（数回毎分）十分な頻度でヒットしましたしばしば。この計画では、手続きがより速く完了するように正規表現を最適化することが計画されています（1ナノ秒ごとにカウントされます）。あなたは私を啓発できますか？

注：mpls layerと802.1Qはインターフェースの他の種類のためにサポートされ、unrouted VLANsではありません。

出典

2011-12-29 Anthony Accioly

なぜ最初に一致しなければならない文字列を分離していることを確認します –

正規表現ではなくString.containsを使ってみましたか？ –

あなたが提供したこれらのエントリは、フルラインか、ラインの途中から取られたいくつかの単語ですか？ – piotrekkr

私は自分の質問に答えるつもりですが、クレジットは@piotrekkrに行きましたが、彼はそれを指摘していました。また、@ JBと@ratchetへの私の誇り。私はmatches()を使用して終了し、indexOfといくつかのcontainsを使用しているロジックは、ほぼ同じ速さでした（これは私にとっては常に1つの正規表現がcontainsへの複数の呼び出しより速いと仮定していました）。（プロファイラによると、約7倍少ない時間がMatcherクラスのメソッドで費やされている）。ここ

は数倍高速であるソリューションです。

^(?:unrouted VLAN.++|GigabitEthernet.+?-mpls layer|FastEthernet.+?-802\\.1Q vLAN subif)$

出典

2011-12-29 21:14:30

あなたは明らかにO（N * k）のコストよりも、一度安価でk個の文字列の長さnの文字列で検索してみてくださいすることができ、いくつかの文字列検索アルゴリズムがあります。

通常、あなたの単語の既存のハッシュのリストとローリングハッシュを比較します。これの代表例はRabin-Karp algorithmです。 wikiページにもこのセクションがあります。原則のより高度なバージョンもありますが、原則を理解するのは簡単です。

私が試してみたいことは、Javaのライブラリが既に存在するかどうかは分かりませんが、それは私が試してみたいことです。5つの文字列はここでは小さく、サイズが異なると複雑になります。だから良いKMP文字列検索が高速でないかどうかを確認する - 私はそれが本当に最高の解決策であると思うだろう（デフォルトのJava APIはナイーブな文字列検索を使用するので、libを使用する）

あなたについてregexes：パフォーマンス重視の検索コードのregex実装をバックトラックするそれは良い考えだとは思わない。

PS：あなたの問題のテストセットとテストハーネスを投稿すると、好きな人にどれくらいの賞賛を寄せることができるだろうか - 人間の本性はとても簡単です:)

出典

2011-12-29 18:54:30 Voo

ありがとう@Voo。私はそれに掘り下げるテストハーネス、私が何ができるかわからない、おそらくそれらの木の文字列に5.000.000回反復し、 'System.nanotime（）'で時間を記録する：D。私はベンチマークをうまく使っていない。私が明日までそれに満足していないと感じたら、コードをテストLOL：Dで更新します。 –

@Anthony Javaでベンチマークを書くのは簡単ではありません。 [caliper]（http://code.google.com/p/caliper/）は簡単にする必要がありますが、私はそれを使用していません。 [This]（http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java）とCliffの[プレゼンテーション]（http：// www。わかりやすいベンチマークが必要な場合は、azulsystems.com/events/javaone_2009/session/2009_J1_Benchmark.pdf）を参考にしてください。 – Voo

一般的なハーネスについては、テスト候補によって実装されたインタフェース 'boolean valid（String s）'を提案し、次にいくつかの典型的な入力文字列をチェックして（結果を確認してください）。最も簡単なのは、あなたが別に提供したファイルから入力を読み込むことです。結局あなたの通常のデータを表現できるはずです。そこで、ランダムな文字列を生成することはできません。一般的には**測定できないものを最適化しないでください**これは本当に最初に行うべきことです。最初のバージョンでいくつか問題を指摘しても心配しないでください;-) – Voo

あなたが探している長い文字列定数がいくつかある場合は、標準のCツール "lex"のJavaアナログを使用することをお勧めします。

すばやいグーグルが私をJFlexに連れて行きました。私はこの特定のツールを使用していないし、利用可能な他のツールがあるかもしれませんが、それは私が探しているツールの一例です。

出典

2011-12-29 19:13:44 theglauber

さて、レックスは彼のためにFSMを作成しています。正規表現はすでにそれを行っています。 – Voo

良い点。私はlexツールを2つの理由で使用したいと考えています。（1）最適化を行うために時間を費やすことができるため、ツールが正規表現よりもFSMを最適化する良い仕事をすることを望みます。（2）lexファイルを使用すると、検索文字列を整理するための読みやすい方法が得られます。 – theglauber

あなたはこのために正規表現を使用する必要がある場合は、このいずれかに変更してみてください：

^(?:unrouted VLAN)|(?:GigabitEthernet.+?-mpls layer)|(?:FastEthernet.+?-802\.1Q vLAN subif)

^メイクエンジンの試合を文字列の初めから、ではないどこかの文字列に

.+?は+ ungreedy

(?:...)を作ります行う。()非捕獲群

出典

2011-12-29 19:22:25 piotrekkr

答えて

関連する問題