Velocizzare il codice

Ciao a tutti,
Oltre al fast I/O conoscete qualche altra tecnica per velocizzare il codice?

Da quello che so io le assunzioni dei problemi sono pensati per essere risolti senza fast I/O e quindi sarebbe meglio evitarli per evitare un risultato più “sincero” .
Per velocizzare esistono i vari “trucchetti” che si possono usare ovunque come “\n” invece di endl in output multipli

Giusto, anche il \n velocizza di molto il codice, una volta addirittura non ho preso 100 a causa dell’endl.
In ogni caso, molti per l’I/O utilizzando anche delle funzioni più lente e quindi la classifica è per forza poco veritiera.
Ad esempio in passato ho utilizzato il freopen che, da solo, rallenta di molto l’esecuzione.

In ogni caso il post l’ho fatto per curiosità e forse a qualcuno può essere utile per fare 100/100 :grinning:

Non era una critica la mia ahah
Per l’input solitamente uso ifstream/ofstream della libreria fstrram. Per rimanere nei tempi l’anno scorso bastavano qualche struttura dati base.

1 Mi Piace

Poi a volte potrebbe essere utile utilizzare un determinato algoritmo di ordinamento…
Ad esempio in “Studio Amico” delle ABC2017 il normale sort della stl non va bene e si usa il counting sort

1 Mi Piace

Con freopen non ho mai avuto problemi, l’ho sempre usata e ho varie soluzioni tra le più veloci. Spesso la differenza la fanno fastin/out e le versioni unlocked di getchar e putchar. Altro parametro importante sono le opzioni di ottimizzazione date a g++ durante la compilazione.

2 Mi Piace

A cosa ti riferisci?

Al fantastico

#pragma GCC optimize ("O3")
4 Mi Piace

Di cosa si tratta?Onestamente non l’ho mai sentito .

È una direttiva da mettere prima degli include che ha lo stesso effetto di passare -O3 a g++ da riga di comando, ottimizzando il codice un bel po’. A volte con O2 o Ofast si ottengono effetti migliori, dipende dal problema.

2 Mi Piace

Ma è un istruzione che posso inserire in ogni caso e velocizza l’algoritmo indipendentemete da algoritmi/strutture usate?
Riusciresti a farmi un esempio di esercizio?

Grazie mille comunque😉

Buon pomeriggio, non tornavo qui da un po’.

Dipende. In locale non lo uso mai in quanto addio simboli di debug.
Sul CMS per quanto ne sappia l’ O3 c’è già, insieme al -fomit-frame-pointer e altre flag che al momento non ricordo.

Un’altra possibilità è usare ios_base::sync_with_stdio(false); e poi usare cin e cout tranquillamente. Sospetto però che l’operator<< e >> siano più lenti di quanto dichiarato, ma non ho dati alla mano (ok, dovrebbero essere templatizzati, tuttavia la faccenda delle flag globali per la conversione bool in alpha, o la base decimale etc., il buffering e così via devono influire in qualche modo).

Un altro motivo per cui preferire printf/scanf a cin/cout è il loro supporto alle espressioni regolari (ricordo un problema sull’Halim che chiedeva di printare la parte decimale di N numeri in ingresso, la sfida è proprio di fastI/O).

Parlando in astratto, uso pesante della STL.
Ad esempio, se devi inizializzare un vettore, usa sempre fill, memcpy, copy, iota etc.

Evita gli iteratori il più possibile. Anche se lo standard mette sullo stesso piano, non credo che, ad esempio, input_stream_iterator sia una buona idea.

Evita gli operator<< inutili, per il discorso di prima. Il che significa, ad esempio, evita di printare un carattere alla volta, piuttosto scrivi su una stringa. Un operatore abbastanza comodo ma che sconsiglio un poco è sstream (qualcuno lo conosceva vero?).

Entrando nel dettaglio.
Come ti dicevo in sede privata @rossimelthomas dovresti puntare sul vedere bottomup dovunque.
Se stai facendo problemi a query, la lettura a blocco delle query e la scrittura in blocco dei risultati rende il tutto un filino più veloce (l’ottimizzazione funziona meglio se i programmi sono CPU-bound quindi evita di “stoppare” l’algoritmo sul più bello stampando o leggendo roba).

Se vuoi fai anche una sana lettura sul funzionamento intrinseco di CPU cache e di località spaziale e temporale.

Se poi approfondissimo ci sarebbe anche la faccenda dell’allineamento, o il branch prediction, ma esuliamo dall’aspetto competitive.

Un ultima cosa va detta:

O(logN) non è necessariamente meglio di O(N)! Conosco gente che costruisce delle map per convertire poche chiavi in pochi valori anziché fare switch/case. Fidatevi, ce ne vuole prima che la differenza conti qualcosa.

1 Mi Piace

Eh si lo so che è molto meglio una bottom-up, però mi vengono molto più naturali le top down.
Devo allenarmi ancora molto :slight_smile: