Best method for string pattern matching in Java if performance is a concern

Question

Greetings,

Let's say you wanted to test a string to see if it's an exact match, or, if it's a match with an _ and any number of characters appended following the _

Valid match examples:

MyTestString
MyTestString_
MyTestString_1234

If performance was a huge concern, which methods would you investigate? Currently I am doing the following:

if (String.equals(stringToMatch)) {
            // success
        } else {
            if (stringToMatch.contains(stringToMatch + "_")) {
                // success
            }
            // fail
        }

I tried replacing the pattern the String.contains _ with a Java.util.regex.Pattern match on _*, but that performed much worse. Is my solution here ideal or can you think of something more cleaver to improve performance a bit more?

Thanks for any thoughts

Just to mention: This stringToMatch.contains(stringToMatch + "_") will always evaluate to false, because the string, that should be within the first one, is longer than that. — KingCrunch
– KingCrunch, Commented May 27, 2011 at 14:01
Post the exact pattern that you tried. Btw, I wouldn't use a greedy one. — Kaj
– Kaj, Commented May 27, 2011 at 14:02
What does your data look like? Should "abc MyTestString cde" have a match? Is "MyTestStringFooBar" a valid match? Do you have a large text block? — Kaj
– Kaj, Commented May 27, 2011 at 14:06

Peter Lawrey · Accepted Answer · 2011-05-27 14:34:41Z

8

You can do something like

if(string.startsWith(testString)) {
    int len = testString.length();
    if(string.length() == len || string.charAt(len) == '_')
          // success
}

I assume you want the testString to appear even if you have a "_"?

EDIT: On whether to use one long condition or nested if statements, there is no difference in code or performance.

public static void nestedIf(boolean a, boolean b) {
    if (a) {
        if (b) {
            System.out.println("a && b");
        }
    }
}

public static void logicalConditionIf(boolean a, boolean b) {
    if (a && b) {
        System.out.println("a && b");
    }
}

compiles to the same code. If you do javap -c

public static void nestedIf(boolean, boolean);
  Code:
   0:   iload_0
   1:   ifeq    16
   4:   iload_1
   5:   ifeq    16
   8:   getstatic       #7; //Field java/lang/System.out:Ljava/io/PrintStream;
   11:  ldc     #8; //String a && b
   13:  invokevirtual   #9; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
   16:  return

public static void logicalConditionIf(boolean, boolean);
  Code:
   0:   iload_0
   1:   ifeq    16
   4:   iload_1
   5:   ifeq    16
   8:   getstatic       #7; //Field java/lang/System.out:Ljava/io/PrintStream;
   11:  ldc     #8; //String a && b
   13:  invokevirtual   #9; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
   16:  return

The complied code is identical.

edited May 27, 2011 at 14:34

answered May 27, 2011 at 14:02

Peter Lawrey

535k83 gold badges770 silver badges1.2k bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Sylver Over a year ago

putting all the checks in the same "if" will improve the performance, if this tidbit is called a lot. (as in a long loop)

Peter Lawrey Over a year ago

Using a nested if, or a single if with a logical condition is the same thing. Using a nested if avoids needing to check the length() if there is not a match.

Brett Kail Over a year ago

Further, that sounds like premature optimization. I suspect the JIT will end up doing the same thing in either case if the code really is hot.

RandomUser Over a year ago

Peter, thank you for the excellent response, this was most helpful!

Sylver Over a year ago

@Peter: Thanks. I just had a case with a PHP script where replacing nested conditions by a single "if" improved performance significantly (several seconds faster), and I thought it might be worth checking as the OP seemed concerned about performance. Your test shows clearly that this is not the case in Java. About "length()", would it be called if the first part of the condition fails? @bkail: You are right, but it was worth a try.

|

alexcoco · Accepted Answer · 2011-05-27 14:20:58Z

2

You could use regular expressions to match patterns. You can use stringToMatch.matches(".*?_.*?"). This returns a boolean.

answered May 27, 2011 at 14:20

alexcoco

6,6656 gold badges29 silver badges39 bronze badges

Comments

Dorus · Accepted Answer · 2011-05-27 15:21:50Z

1

I ran some benchmarks. This is the quickest I can get.

    String a = "Test123";
    String b = "Test123_321tseT_Test_rest";
    int len1 = a.length();
    int len2 = b.length();
    if ((len1 == len2 || (len2 > len1 && (b.charAt(len1)) == '_'))
        && b.startsWith(a)) {
        System.out.println("success");
    } else {
        System.out.println("Fail");
    }

This will at least work correctly at reasonable performance.

Edit: I switched the _ check and the startsWith check, since startsWith will have worse perforam the _ check.

Edit2: Fixed StringIndexOutOfBoundsException.

Edit3: Peter Lawrey is correct that making only 1 call to a.length() spares time. 2.2% in my case. Latest benchmark shows I'm 88% faster then OP and 10% faster then Peter Lawrey's code.

Edit4: I replace all str.length() with a local var, and ran dozen more benchmarks. Now the results of the benchmarks are getting so random it's impossible to say what code is faster. My latest version seems to win by a notch.

edited May 27, 2011 at 15:21

answered May 27, 2011 at 14:08

Dorus

7,5761 gold badge32 silver badges38 bronze badges

1 Comment

Dorus Over a year ago

I ran a benchmark vs Peter Lawrey's code, my code is 9% faster then his. It's also 85% faster then the code from the OP.

Collectives™ on Stack Overflow

Best method for string pattern matching in Java if performance is a concern

3 Answers 3

6 Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

6 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related