2
\$\begingroup\$

I have this regex:

(\d?)[A-Za-z](?=(\d?)(.*))(?=(.* ){5})

It would be used by me for Chess FEN strings.

I wonder if regex [A-Za-z] is faster than [RNBQKrnbqk]? I only need to check the given letters (but no other letters will appear).

My thoughts are:

  1. [A-Za-z] - the regex engine can match if a char is 65 <= c <= 90 or 97 <= c <= 122. Worst case is 4 comparisons.

  2. [RNBQKrnbqk] - the engine checks if the inspected char equals every given character in the group. Worst case is 10 comparisons.

Am I understanding regex correctly?

\$\endgroup\$
3
  • 5
    \$\begingroup\$ It's impossible to say, because It would depend on the implementation details of the regex engine. In any case, it's unlikely that this is something you would need to worry about. If you have noticeable performance issues because of this (you'd need to be processing millions of inputs a second), then you probably should implement a simple parser optimized to this specific task instead of using a regex. \$\endgroup\$
    – RoToRa
    Aug 2, 2018 at 9:25
  • \$\begingroup\$ Also for any practical use, you'd have to verify the character anyway somewhere down the line, so why not do it here? \$\endgroup\$
    – RoToRa
    Aug 2, 2018 at 9:29
  • 2
    \$\begingroup\$ I think you are looking to optimise in the wrong place, with the speed of modern computers the difference between [A-Za-z] and [RNBQKrnbqk] wont be noticeable. I'd take a look at your lookaheads (?=(\d?)(.*)) can match 0 or more of any character (\d?) matching 0 or 1 number so if there is no number .* matches. Also the {5} in (?=(.* ){5}) is redundant as .* can match nothing to the end of the input so {5} can match 5 lots of nothing \$\endgroup\$
    – JGNI
    Aug 2, 2018 at 9:31

1 Answer 1

6
\$\begingroup\$

No. The matching for a-zA-Z would be slower than the exact character-set you supply: RNBQKrnbqk.

You can observe this behaviour by checking the backtrace it generates. I compared 3 different patterns, two being your own, and the third I found on chess.stackexchange.com:

(\d?)[a-z](?=(\d?)(.*))(?=(.* ){5})

has 64 matches generated in 14323 steps

(\d?)[rnbqk](?=(\d?)(.*))(?=(.* ){5})

has 32 matches generated in 7512 steps

and the pattern from chess.stackexchange:

([rnbqkp1-8]+\/){7}([rnbqkp1-8]+)\s[bw]\s(-|K?Q?k?q?)\s(-|[a-h][36])

has 2 matches generated in 95 steps


Note that I have enabled the ignorecase flag in all three of them.

\$\endgroup\$
5
  • \$\begingroup\$ slight improvement to your code: ([rnbqkp1-8]+\/){7}([rnbqkp1-8]+) [bw] (-|KQ?k?q?|K?Qk?q?|K?Q?kq?|K?Q?k?q) (-|[a-h][36]) \$\endgroup\$ Aug 2, 2018 at 12:52
  • \$\begingroup\$ also "\d+ \d+" make sense. It makes it somehow faster. regex101.com/r/ykc7s9/2 \$\endgroup\$ Aug 2, 2018 at 12:52
  • \$\begingroup\$ @S.G. Adding multiple cases KQkq checks defeats the purpose of K?Q?k?q? pattern. \$\endgroup\$
    – hjpotter92
    Aug 2, 2018 at 13:39
  • \$\begingroup\$ yes, but K?Q?k?q? matches an empty String which is not a valid. For example " 2P5/6P1/P1R5/RP6/3r4/p5bp/4p3/6P1 b a6 17 63" is accepted but is not valid \$\endgroup\$ Aug 2, 2018 at 14:35
  • \$\begingroup\$ regex101.com/r/ykc7s9/9 \$\endgroup\$ Aug 2, 2018 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.