ldyllic's blog

Improve Your Code's Runtime with the Right Order of IF Statements or Using Switch Statements
By ldyllic, history, 21 month(s) ago, In English

For a great while of my CP career I had no idea how such, at a first glance, insignificant things might affect the runtime of the code. And till this day I keep seeing many beginners having lack of knowledge about this so-called effect, that's why I would like to share it here and hope it'll help you out someday.

1 code 164992399 executes in a time of 1918ms.
2 code 164991769 executes in a time of 280ms.

Notice 2 drastically different runtimes (6x difference!). The reason for that is pretty straightforward: in this code one of three IF statements (IF statement with == 2) gets a true response way more often than others. While the first code has an IF statement with 2 at the end, the second code has such IF statement at the beginning.

Knowing this we can make a conclusion: the order of IF statements matters, and sometimes matters a lot (you get AC or TLE). So whenever you hit (or feel you might hit) the bound of the time limit you always want to check whether all IF statements are placed in the right order and if not — a little change might make you happier by seeing this lovely green Accepted word.

upd. As Apachee mentioned in the comments if you wish to avoid thinking where it is better to put one or another IF statement you can use switch-case method which helps to achieve the same runtime as the second code 165019894.

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

Comments Comments (10)
| Write comment?
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Using switch statements in such cases might help you negate the effect of different rearrangements, because I believe switch statements translate to calculating the address to jump to, and then jumping there. For example, if you write switch statement with 3 cases: 1, 2, and 3, then it might result in something like 

address = current + value*block_size;
jump address;

I don't know exactly how switch statements are translated into assembly, but that's what I believe after looking at a few different programs in disassemblers.

Also you might want to look at [[likely]] and [[unlikely]] attributes, which are available in C++20.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

This blog is an absolute gem. Very useful, thanks.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +24 Vote: I do not like it

You use MX = 1e3+1 in one but MX = 1e3+2 in the other. I changed the constant back and got 717 ms. 165025789

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 8   Vote: I like it +9 Vote: I do not like it

    Oh indeed, this code was submitted long time ago so I'm not sure if I remember what happened there.

    upd. I resubmitted both codes and they both still stay in the same bracket (280-330), however some differences occure because of CF system I believe. So seems it's not the thing in this code.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So, the conclusion from the blog is incorrect right? Why don't you update the blog then?

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I explicitly mention that fft's point doesn't change anything, read the "upd." section again.

        → Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

ok thnx

→ Reply