CSES - Optimointi

Oletko tehnyt brute force -koodin, jossa lasketaan bittien määriä (esim. __builtin_popcount), mutta koodi on liian hidas?

Ei hätää, koska voit nopeuttaa koodia lisäämällä alkuun seuraavan:

#pragma GCC target ("arch=sandybridge")

Tässä arch-arvona on "sandybridge", joka toimii esim. CSES:ssä. Voit tarkastaa tällä komennolla, mikä on oman koneesi arch-arvo:

g++ -march=native -Q --help=target

Entä jos haluat nopeuttaa koodia lisää? Yksi toimiva kikka on muuttaa silmukoita niin, että yhden kierroksen aikana tehdään monta askelta.

Tarkastellaan esimerkkinä seuraavaa koodia, joka laskee kertoman N! modulo M:

ll k = 1;
for (int i = 1; i <= N; i++) {
    k = k*i%M;
}

Kun N=10^9, koodi vie aikaa 6 sekuntia. Voimme kuitenkin muuttaa koodia näin:

ll k1 = 1, k2 = 1;
for (int i = 1; i <= N; i += 2) {
    k1 = k1*i%M;
    k2 = k2*(i+1)%M;
}
ll k = k1*k2%M;

Tämän muutoksen jälkeen aikaa kuluukin vain 3 sekuntia. Entä jos teemme silmukan sisällä vielä enemmän askelia?

Optimointi