hiddentesla's blog

By hiddentesla, history, 3 years ago, In English

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

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?

  • Vote: I like it
  • +26
  • Vote: I do not like it

3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by hiddentesla (previous revision, new revision, compare).