2

個人的な学習課題として、単項文字列を長さが 2 のべき乗で増加する部分に分割するために、次の正規表現を作成しました ( ideone.com も参照)。

    for (String s :
       new String(new char[500])
       .split("(?=(.*))(?<=(?<=(^.*))\\G.*)(?<=(?=\\2\\2.\\1)^.*)")
    ) {
       System.out.printf("%s ", s.length());
    }
    // prints "1 2 4 8 16 32 64 128 245 "

これは、ルックアラウンド中のキャプチャ、ネストされたルックアラウンド、後方参照でのマッチング、および無限長の後読み (Java では公式にサポートされていませんが、とにかく動作します) の組み合わせを使用します。2 のべき乗の合計のプロパティと、文字列に単項アルファベットがあるという事実も利用されます。

このソリューションは判読不能であり、パフォーマンスも最悪です。

私の質問は、この正規表現をどのように「最適化」しますか?

  • 正規表現を読みやすくできますか (パフォーマンスが悪くても問題ありません)
  • 正規表現のパフォーマンスを向上させることはできますか (読みにくくても構いません)
4

3 に答える 3

2

私は Java の専門家ではないため、回答は .NET 正規表現の実装に基づいています。使った

"(?<=(^.*)\\G.*)(?<=\\G\\1.)"

という事実に基づいてい\sum_{i=0}^{n} 2^n = 2^{n+1} - 1ます。基本的には「最後の試合の後の部分が最後の試合の前の部分よりも1つ長いすべての位置に一致する」と書かれています。

オリジナルの約 2 倍の速さ (.NET の場合) で、10,000 文字を分割するのに 2 秒もかかりません。もう少し読みやすいと思います。うーん... 読めないことが少なくなりました。=)

乾杯!いい質問です!=)

編集:正規表現をもう一度見ると、同じアプローチを使用しているように見えますが、より複雑な方法です。私は挑戦が好きで、あなたの正規表現がまったく読めないため、自分のソリューションを作成する前にあなたのものを読もうとしなかったことを認めます. =) Java 正規表現エンジンのために、これらのネストされたルックアラウンドが必要ですか?

于 2010-07-07T10:25:18.503 に答える
1

私は本当にしません。すべてを捨てて、読み取り可能な手続き型コードとしてやり直します。

正規表現では実際にすべきでないことがいくつかあります。これはそのうちの1つです。私はすべて自分自身を教育するためですが、それがいつか役立つと本当に思いますか?

おそらく、実際に使用可能で保守可能なもの学ぶほうがよいでしょう:-)

于 2010-07-07T09:31:18.647 に答える
0

これらは、Java でうまくいったパターンです。最終的には、完全な説明を含む 1 つの包括的な回答にすべてを修正します。これらはすべて Java 文字列リテラル表現です。

  • P000:"(?=(.*))(?<=(?<=(^.*))\\G.*)(?<=(?=\\2\\2.\\1)^.*)"
  • P001:"(?=(.*))(?<=(?<=(^.*))\\G.*)(?<=(?=\\2.\\1)\\G.*)"
    • 基本的にはP000と同じですが、代わりに^\2\G\2.\1頭を切り落として\G\2.\1
    • 2.21 秒で 500 ( ideone.com )
  • P002:"(?=(.*))(?<=(?<=(^.*))(?=\\2.\\1)\\G.*)"
    • P000よりかなり遅いが短い
    • 基本的に、両方の後読みが固定されている P001 の「リファクタリング」\G
    • 3.05 秒で 400 ( ideone.com )
于 2010-07-07T11:27:25.670 に答える