Nie je hádam nič horšie než striedať input() a print(). Každý input() flushne print() a všetko bufferovanie ide do kanála. Ak máme úlohu s veľa sadami (napríklad milíon), oplatí sa nám výsledky uložiť do poľa a vypísať až na koniec.
Podobne, aj v úlohách kde máme veľa riadkov vstupu (a nie nutne veľa riadkov výstupu) sa nám môže oplatiť nevolať milíon krát input. Radšej si načítame celý vstup naraz a potom už si riadkovanie robíme sami.
import sys
lines = sys.stdin.read().split("\n")
Oheň vie byť sluha i pán. Tak isto vstavané funkcie nám vedia pomôcť i uškodiť. Ak chceme zistiť maximum poľa, nenájdeme lepší prístup než funkciu max(). Ak chceme zistiť maximum dvoch prvkov, nenájdeme horší prístup než funkciu max().
V programovaní sa často snažíme nájsť najlepší výsledok, či už pri hľadaní najkratšej cesty alebo dynamike. Často sa teda v kóde vyskytne výraz best = max(best, aktual). Python je v takomto prípade hlupáčik a tento jeden riadok je v niektorých dynamikách najpomalšia časť celého kódu. Nahradíme ho vlastným if aktual > best: best = aktual a získame niekedy 2x rýchlejší kód.
Snažme sa používať čo najviac vstavaných funkcií, pretože nám uľahčujú život a skrášlujú kód, až na prípady kedy nie.
Ďalej upozornime, že existujú vstavané funkcie a štruktúry bisect.bisect_left, collections.Counter, collections.deque a heapq. Neodporúčame používať modul queue.
Zober svoj kód. Daj ho do def solve():. Zavolaj solve(). Python je znova hlúpučký a global kód vie byť triviálne 3x pomalší než ten istý kód s týmito dvoma riadkami navyše (vysvetlenie).
Väčšina týchto optimalizácii je zbytočná ak jednoducho použijeme PyPy. :/
Avšak PyPy má zase problémy so sys.setrecursionlimit. Malo by ho mať predvolene väčšie ako Python, ale stáva sa, že to stále nie je dosť a keď ho zväčšíme tak (minimálne na Codeforces) dostaneme okamžité Memory Limit Exceeded. Teda 95% času sa oplatí používať PyPy, ale ak ideme robiť s hlbokou rekurziou tak si treba dať pozor a možno použiť niečo iné.
Čo je najväčší trik? Optimalizovať keď treba. Urob si odhad časovej zložitosti. Zakomentuj časti kódu. Zamysli sa nad worst case prípadom. Ak netreba optimalizovať, tak netreba!
Úloha na grafe, program TLEie. Možno pomôže ak sem dám if podmienka: break. Problém je, že táto podmienka sa nikdy nespustí na grafe tvaru cesta a na ňom to tiež dáva TLE. Tento if je potom iba zbytočný kód, v ktorom môže byť chyba, ktorý musím potom už navždy zvažovať či mi kód vlastne nespomaluje, či mi nespôsobí WA, ...
Počul som že max() je pomalé tak všade používam if. Ten max by sa ale počas behu programu zavolal sto krát a iná časť kódu, ktorú si neoptimalizoval/a sa vykoná sto milíonov krát. Gratulujem, máš neprehľadný rozvetvený kód ktorý nie je o nič rýchlejší.
Venujte svoju pozornosť tam kam treba a keď treba. A často aj keď si myslíte, že treba, tak netreba a problém je celkom iný než by sa zdalo.