Testlib validator taking unusually long when validating multiple token patterns.

Revision en1, by hiddentesla, 2021-10-15 14:21:30

Good day codeforces.

I am currently preparing a problem where a variable must match one of the ten possible values. Once I finished the validator, I noticed that it validates unusually long, about 18 seconds. Meanwhile, my solution only runs in about 2 seconds on my local machine.

After debugging, I found out that the problem is with readToken. I created a simple validator to reproduce the bug:

Validator 1: https://ideone.com/1CZiQW

Validator 2: https://ideone.com/d91Aan

test-case used: https://files.catbox.moe/qb00ce.in (size: 5.2 MB)

What both of them do is read an input file where the first variable (cmd) can be one of ten values (QUERY1 — QUERY10). Their running time differ vastly.


time ./a.out < testcase.in

real    0m16,480s
user    0m16,465s
sys     0m0,009s


time ./a.out < testcase.in

real    0m1,667s
user    0m1,662s
sys     0m0,005s

As we can see, Validator2 is almost ten times faster than validator1. Is there a caveat on readToken() which makes it slow to validate multiple patterns? i tried readToken([A-Z0-9]*) and it gives compatible results to validator2.

Thank you for your time, and have a nice day :)

Tags testlib, validators, validator


  Rev. Lang. By When Δ Comment
en2 English hiddentesla 2021-10-15 15:53:13 128
en1 English hiddentesla 2021-10-15 14:21:30 1324 Initial revision (published)