Блог пользователя ldyllic

Автор ldyllic, история, 21 месяц назад, По-английски

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.

  • Проголосовать: нравится
  • +34
  • Проголосовать: не нравится

»
21 месяц назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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.

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
21 месяц назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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

  • »
    »
    21 месяц назад, # ^ |
    Rev. 8   Проголосовать: нравится +9 Проголосовать: не нравится

    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.

    • »
      »
      »
      21 месяц назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        21 месяц назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
21 месяц назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

ok thnx