1

私はGoogleCaliperを使用して、文字列内のmdn番号をチェックする2つの方法をベンチマークします。1つのメソッドはユーザー定義のメソッドを使用しますが、他のメソッドは正規表現を使用します。平均して、正規表現メソッドはユーザー定義メソッドの5倍の時間がかかることに驚いています。

これが私のベンチマークコードです。

package com.code4refernce.caliper;

import java.util.Random;
import java.util.regex.Pattern;

import com.google.caliper.Param;
import com.google.caliper.SimpleBenchmark;

public class SimpleCaliperTest extends SimpleBenchmark {
    String extensiveregex = "^\\d?(?:(?:[\\+]?(?:[\\d]{1,3}(?:[ ]+|[\\-.])))?[(]?(?:[\\d]{3})[\\-/)]?(?:[ ]+)?)?(?:[a-zA-Z2-9][a-zA-Z0-9 \\-.]{6,})(?:(?:[ ]+|[xX]|(i:ext[\\.]?)){1,2}(?:[\\d]{1,5}))?$";
    Pattern EXTENSIVE_REGEX_PATTERN = Pattern.compile(extensiveregex);

    String mdn[][];
    Random random;
    @Param
    int index;

    @Override
    protected void setUp() {
        random = new Random(0);
        mdn = new String[11][1<<16];
        for (int i=0; i<mdn.length; ++i) {
            mdn[0][i] = String.format("%03ddsfasdf00000", random.nextInt(1000));
            mdn[1][i] = String.format("%04d", random.nextInt(10000));
            mdn[2][i] = String.format("%10d", random.nextInt((int) 1e10));
            mdn[3][i] = String.format("-%10d", random.nextInt((int) 1e10));
            mdn[4][i] = String.format("%10d-", random.nextInt((int) 1e10));
            mdn[5][i] = String.format("%03d-%03d-%03d", random.nextInt(1000), random.nextInt(1000), random.nextInt(1000));
            mdn[6][i] = String.format("-%03d-%03d-%03d-", random.nextInt(1000), random.nextInt(1000), random.nextInt(1000));
            mdn[7][i] = String.format("%03d-%03d-%03d-", random.nextInt(1000), random.nextInt(1000), random.nextInt(1000));
            mdn[8][i] = String.format("%03d-%03d-%03d ext %04d", random.nextInt(1000), random.nextInt(1000), random.nextInt(1000), random.nextInt(10000));
            mdn[9][i] = String.format("%03d-%03d-%03d ext %04d-", random.nextInt(1000), random.nextInt(1000), random.nextInt(1000), random.nextInt(10000));
            mdn[10][i] = "123456789012345677890";
        }
    }

    /**
    *This method benchmark the user defined method to check the mdn.
    **/
    public boolean timeExtensiveSimpleMDNCheck(int reps){
        boolean results = false;
        for(int i = 0; i<reps; i ++){
            for(int index2=0; index2<mdn.length; index2++)
                //Use simple method to check the phone number in string.
            results ^= extensiveMDNCheckRegularMethod(mdn[index][index2]);
        }
        return results;
    }

    /**
    *This method benchmark the regex method.
    **/
    public boolean timeExtensiveMDNRegexCheck(int reps){
        boolean results = false;
        for(int i = 0; i<reps; i ++){
            for(int index2=0; index2<mdn.length; index2++)
                //user Regular expression to check the phone number in string.
            results ^=mdnExtensiveCheckRegEx(mdn[index][index2]);
        }
        return results;
    }

    public boolean extensiveMDNCheckRegularMethod(String mdn){

        //Strip the character which not numeric or 'x' character.
        String stripedmdn = stripString(mdn);

        if(stripedmdn.length() >= 10 && stripedmdn.length() <= 11 && (!stripedmdn.contains("x") || !stripedmdn.contains("X"))){
            //For following condition
            //1-123-456-7868 or 123-456-7868
            return true;
        }else if ( stripedmdn.length() >= 15 && stripedmdn.length() <= 16  ) {
            //1-123-456-7868 ext 2345 or  123-456-7868 ext 2345
            //
            if ( stripedmdn.contains("x") ) {
                int index = stripedmdn.indexOf("x");
                if(index >= 9 && index <= 10){
                    return true;
                }
            }else if( stripedmdn.contains("X") ) {
                int index = stripedmdn.indexOf("X");
                if(index >= 9 && index <= 10){
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * Strip the other character and leave only x and numeric values.
     * @param extendedMdn
     * @return
     */
    public String stripString(String extendedMdn){
        byte mdn[] = new byte[extendedMdn.length()];
        int index = 0;
        for(byte b : extendedMdn.getBytes()){
            if((b >= '0' && b <='9') || b == 'x'){
                mdn[index++] = b;
            }
        }
        return new String(mdn);
    }

    private boolean mdnExtensiveCheckRegEx(String mdn){
        return EXTENSIVE_REGEX_PATTERN.matcher(mdn).matches();
    }
}

そして、ベンチマークを実行するメインクラス：

package com.code4refernce.caliper;
import com.google.caliper.Runner;

public class CaliperRunner {
    public static void main(String[] args) {
        String myargs[] = new String[1];
        myargs[0] = new String("-Dindex=0,1,2,3,4,5,6,7,8,9,10");
        Runner.main(SimpleCaliperTest.class, myargs);
    }
}

そして、Caliperベンチマークの結果は次のとおりです。

Benchmark index            us  linear runtime
ExtensiveSimpleMDNCheck     0  5.44 =====
ExtensiveSimpleMDNCheck     1  4.34 ====
ExtensiveSimpleMDNCheck     2  5.02 =====
ExtensiveSimpleMDNCheck     3  5.08 =====
ExtensiveSimpleMDNCheck     4  4.92 ====
ExtensiveSimpleMDNCheck     5  4.83 ====
ExtensiveSimpleMDNCheck     6  4.87 ====
ExtensiveSimpleMDNCheck     7  4.72 ====
ExtensiveSimpleMDNCheck     8  5.14 =====
ExtensiveSimpleMDNCheck     9  5.25 =====
ExtensiveSimpleMDNCheck    10  5.57 =====
 ExtensiveMDNRegexCheck     0 17.71 =================
 ExtensiveMDNRegexCheck     1 21.73 =====================
 ExtensiveMDNRegexCheck     2 13.47 =============
 ExtensiveMDNRegexCheck     3  3.37 ===
 ExtensiveMDNRegexCheck     4 12.44 ============
 ExtensiveMDNRegexCheck     5 26.06 ==========================
 ExtensiveMDNRegexCheck     6  3.36 ===
 ExtensiveMDNRegexCheck     7 29.84 ==============================
 ExtensiveMDNRegexCheck     8 23.80 =======================
 ExtensiveMDNRegexCheck     9 24.01 ========================
 ExtensiveMDNRegexCheck    10 20.53 ====================

ここで何かが足りませんか？正規表現の実行に時間がかかるのはなぜですか？

4

1 に答える 1

5

正規表現エンジンは、フィードする正規表現と同じくらい優れているだけであり、正規表現は非常に非効率的です. この入力でRegexBuddyで試しました：

1-123-456-7868 x2345!

...末尾!が一致しないことを確認しますが、その過程で多くの作業を行います。正規表現が失敗するまでに 142 ステップかかりました。次に、非キャプチャ グループのほとんどをアトミック グループに変更し、量指定子の一部を所有格にすることで微調整しましたが、失敗するのに 35 ステップしか必要としませんでした。

参考までに、正規表現でパフォーマンスの問題が発生する場合は、成功した一致ではなく、失敗した一致の試行が表示される可能性が圧倒的に高くなります。上記の文字列からを削除する!と、あなたの正規表現と私の正規表現はわずか 34 ステップで一致します。

余談ですが、あなたのstripString()方法は多くの点で間違っています。StringBuilder を使用して新しい文字列を作成する必要があり、char値をchars ではなく他の s と比較する必要がありますbyte。getBytes()メソッドとString(byte[])コンストラクターが存在することを忘れてください。String から byte[] または byte[] から String への変換を行う必要がある場合は、Charset を指定できるメソッドを常に使用してください。

EDIT以下のコメントに従って、Java 文字列リテラルとして微調整された正規表現を次に示します。

"^\\d?(?>(?>\\+?(?>\\d{1,3}(?:\\s+|[.-])))?\\(?\\d{3}[/)-]?\\s*)?+(?>[a-zA-Z2-9][a-zA-Z0-9\\s.-]{6,})(?>(?>\\s+|[xX]|(i:ext\\s?)){1,2}\\d{1,5})?+$"

..そしてより読みやすい形式で：

^
\d?
(?>
  (?>
    \+?
    (?>
      \d{1,3}
      (?:\s+|[.-])
    )
  )?
  \(?
  \d{3}
  [/)-]?
  \s*
)?+
(?>[a-zA-Z2-9][a-zA-Z0-9\s.-]{6,})
(?>
  (?>
    \s+
   |
    [xX]
   |
    (i:ext\s?)
  ){1,2}
  \d{1,5}
)?+
$

しかし、原子群と所有量指定子の効果を示すために書いただけです。そのために、私は他のいくつかの問題を放っておきました。私の要点は、不適切に記述された正規表現がmdnExtensiveCheckRegEx()メソッドのパフォーマンスに与える影響を示すことでした。

于 2012-08-31T12:56:33.683 に答える