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?

Improve this question
\$\endgroup\$
  • 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 '18 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 '18 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 '18 at 9:31
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.

Improve this answer
\$\endgroup\$
  • \$\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\$ – BitBeats Aug 2 '18 at 12:52
  • \$\begingroup\$ also "\d+ \d+" make sense. It makes it somehow faster. regex101.com/r/ykc7s9/2 \$\endgroup\$ – BitBeats Aug 2 '18 at 12:52
  • \$\begingroup\$ @S.G. Adding multiple cases KQkq checks defeats the purpose of K?Q?k?q? pattern. \$\endgroup\$ – hjpotter92 Aug 2 '18 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\$ – BitBeats Aug 2 '18 at 14:35
  • \$\begingroup\$ regex101.com/r/ykc7s9/9 \$\endgroup\$ – BitBeats Aug 2 '18 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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