Testlib validator taking unusually long when validating multiple token patterns.
Разница между en1 и en2, 128 символ(ов) изменены
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.↵

Validator1:↵


~~~~~↵
time ./a.out < testcase.in↵

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



Validator2:↵

~~~~~↵
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 :)↵

Edit: im also wondering. 1.6 s just to read input is a bit slow for C++, no? Is there anything else that can be improved here?↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский hiddentesla 2021-10-15 15:53:13 128
en1 Английский hiddentesla 2021-10-15 14:21:30 1324 Initial revision (published)