c# - c＃正規表現の高いCPU使用率

Question

私の小さなプログラムは、Web サイトが使用するスクリプトの種類をチェックしており、80% 以上の CPU i7 プロセッサを使用しています。普通なのかな？

コード：

public static class EnginesMatcher
{

    public static readonly Regex Drupal1 =
        new Regex(
            @"/misc/drupal\.js|Drupal\.settings|href=""http://drupal\.org""|\?q=node/[0-9]+|/\?q=user/register|/\?q=user/password|/user/register\?destination|<li class=""collapsed""><a href=""/node/add"">|/dpl3/files/|/modules/node/",
            RegexOptions.Compiled);

    public static readonly Regex XE1 =
        new Regex(
        @"XpressEngine|content=""zeroboardXE|content=""xe_board""|var zbxe_session_name|/xe\.css\?2|/xeicon/favicon\.ico""|#xe-editor-container-1|xpress_xeditor",
            RegexOptions.Compiled);

    //and 60 more such regex

別のクラスで

  public async Task<Result> Match(string url)
        {

            if (!await Open(url).ConfigureAwait(false)) return ResultKey;


            if (EnginesMatcher.Drupal1.IsMatch(html))
            {
                return new Result()
                {
                    Key = AResultKey.Success,
                    LogFile = "Drupal.txt",
                    Message = "Drupal",
                    Url = url
                };
            }
            if (EnginesMatcher.XE1.IsMatch(html))
            {
                return new Result()
                {
                    Key = AResultKey.Success,
                    LogFile = "Drupal.txt",
                    Message = "Drupal",
                    Url = url
                };
            }

Match(url) 関数は ForeachAsyncLoop にあり、プログラムは 1 分あたり約 4000 リンクをチェックします。最大 20% の CPU を使用するすべての正規表現を無効にすると、正規表現のパフォーマンスを向上させることはできますか? 強調されたテキスト

score 5 · Accepted Answer

おそらく、正規表現ではあまり高速化できません。ただし、別のアルゴリズムを使用することで、おそらくより多くのことを行うことができます。

Aho-Corasick 文字列マッチングアルゴリズムは、ユーザーが行っていることとまったく同じように設計されています。つまり、大量のテキスト内で固定された文字列セットを探します。

標準アルゴリズムは正規表現をサポートしていませんが、正規表現はそのままの文字列です。つまり、探しているのはthis|that|something else|something more. これは、4 つの異なる文字列を探すのと同じです。

私は数年前に C# での Aho-Corasick アルゴリズムの実装を公開しました。やり方を少し変更すれば、うまくいくはずです。

探している文字列と対応する Web サイトの辞書を作成することから始めます。

Dictionary<string, string> StringsToSites = new Dictionary<string, string>();

次に、文字列を追加します。たとえば、Drupal の場合、以下を追加します。

StringsToSites.Add("/misc/drupal\.js", "Drupal");
StringsToSites.Add("Drupal.settings", "Drupal");
StringsToSites.Add(@"href=""http://drupal\.org"", "Drupal");
// problem with this one ...   |\?q=node/[0-9]+
StringsToSites.Add("?q=user/register", "Drupal");
// etc., etc.

逐語的な文字列ではないものには問題があることに注意してください。実装が「?q=node/[0-9]+/」に一致する方法はありません。できる最善の方法は、文字列「?q=node/」を追加することです。

次に、マッチャーを作成して入力します。

AhoCorasickStringSearcher matcher = new AhoCorasickStringSearcher();
foreach (var key in StringsToSites.Keys)
{
    matcher.AddItem(key);
}
matcher.CreateFailureFunction();

次に、表示されるすべてのリンクに対して、次のように呼び出しますmatcher.Search。

var Matches = matcher.Search(link);

これにより、オブジェクトのコレクションが得られますStringMatch。Textを辞書で調べて、一致するサイトを確認できます。例えば：

foreach (var m in Matches)
{
    string site;
    if (StringsToSites.TryGetValue(m.Text, out site))
    {
        Console.WriteLine("Text '{0}' matches site '{1}'.", m.Text, site);
    }
}

これは、正規表現ソリューションの少なくとも 10 倍、おそらく 100 倍高速であると予想されます。

score 1 · Accepted Answer

あなたがやっていることの継承はこれです：

エンジンは、文字列の先頭から順番に交替を照合しようとします。
正規表現を呼び出す順序で。

1 と 2 を達成しようとすると、すべての正規表現を 1 つの正規表現に組み合わせることができます。これらを組み合わせることでパフォーマンスが低下することはないと思います。さらに効率的かもしれません。

いずれにせよ、これはおそらくコードの遅いポイントになるため、調査する価値があります。

したがって、あなたがしていることと同等のものはこれです：

  Regex rxAll = new Regex(
      @"
           (?:
                ^ [\S\s]*
                (?<Drupal1>
                     /misc/drupal\.js
                  |  Drupal\.settings
                  |  href=""http://drupal\.org""
                  |  \?q=node/ [0-9]+
                  |  /\?q=user/register
                  |  /\?q=user/password
                  |  /user/register\?destination
                  |  <li\ class=""collapsed""><a\ href=""/node/add"">
                  |  /dpl3/files/
                  |  /modules/node/
                )
             |
                ^ [\S\s]*
                (?<XE1>
                     XpressEngine
                  |  content=""zeroboardXE
                  |  content=""xe_board""
                  |  var\ zbxe_session_name
                  |  /xe\.css\?2
                  |  /xeicon/favicon\.ico""
                  |  \#xe-editor-container-1
                  |  xpress_xeditor
                )
           )
      ", RegexOptions.IgnorePatternWhitespace);

  string html =
      @"
         <a class=""x-fn"" href=""javascript:void(0);"">
         <a class='x-fn' href = ""javascript:void(0); "">
         <a href='javascript:void(0);' class=x-fn >
         <a class=""x-fn"" href=javascript:void(0); >
         <a 'hello' href=javascript:void(0); world class=x-fn content=""xe_board"">
      ";

  Match matches = rxAll.Match( html );
  if (matches.Success)
  {
      if (matches.Groups["Drupal1"].Success)
      {
          Console.WriteLine("Matched Drupal1 -> {0}", matches.Groups["Drupal1"].Value);
          return;
      }
      if (matches.Groups["XE1"].Success)
      {
          Console.WriteLine("Matched XE1 -> {0}", matches.Groups["XE1"].Value);
          return;
      }
  }
  return;

編集：ところで、正規表現でRegexFormat（.com）プログラムを使用しました。これらの Verbatim 正規表現は
、ボタンを数回クリックするだけで作成されました。そのため、ツールを使用してすべての作業を行うことができます。

c# - c＃正規表現の高いCPU使用率

2 に答える 2

Related

Reference