Ottimizzazione Trova la somma pari V2.0

Aiuto
1

Salve a tutti, volevo sapere se oltre all’utilizzo delle funzioni del C per lettura e scrittura su file che risultano più veloci, cè un modo di ottimizzare ulteriormente l’algoritmo di ricerca della somma massima??

Io semplicemente tengo 2 vettori da 2 elementi.
un vettore per contere i due numeri pari più grandi (dato che pari + pari = pari)
ed un vettore per contenere i due numeri dispari più grandi (dato che dispari + dispari = pari)

Solo che il fatto di dover swappare i vari richiede un po di tempo.

Il codice qui sotto da 100/100 ma nel test case 20 impiega 0.030

Saluti,
Simone

#include <fstream>

using namespace std;

#define FILE_INPUT “input.txt”
#define FILE_OUTPUT "output.txt"

int insert(int n, int var[]) {
	if(n > var[0]) {
		var[1] = var[0];
		var[0] = n;
		return 1;
	}
	else if(n > var[1]) {
		var[1] = n;
		return 1;
	}
	return 0;
}

int main()
{
	ifstream in(FILE_INPUT);
	ofstream out(FILE_OUTPUT);
	
	if(!in || !out) return 1;
	
	int N,temp,s1,s2;
	int odd[2] = {-1,-1}, even[2] = {-1,-1};
	in>>N;
	
	for(int i = 0; i < N; i++) {
		in>>temp;
		if(temp % 2 == 0) { //pari
			insert(temp,even);
		}
		else {
			insert(temp,odd);
		}
	}
	if(odd[1] != -1 || even[1] != -1) {
		s1 = odd[0]+odd[1];
		s2 = even[0]+even[1];
		out<< (s1 > s2 ? s1 : s2);
	}
	else {
		out<<-1;
	}
	in.close();
	out.close();
	return 0;
}
2

Nota: le funzioni di lettura del C++ non sono sempre più lente. Il fatto è che cin/cout mantengono una “sincronizzazione” con scanf/print che ti permette di leggere/scrivere in un modo o nell’altro, interscambiabilmente. Se esegui questa riga, prima di leggere/scrivere, disattivi la suddetta sincronizzazione:


ios_base::sync_with_stdio(false);

A volte in questo modo cin/cout risultano addirittura più veloci di scanf/printf (ma a quel punto devi stare attento a NON mischiare mai scanf/printf)

3

Grazie della risposta,
Cosa succede nel caso io disattivi la sincronizzazione e faccia una cosa del genere:

sync_with_stdio(false);
cin>>a;
scanf("%d",b);
cout<<a;
printf("%d",b);

Disattivando la sincronizzazione ho miglioramenti solo quando utilizzo cin e cout giusto??
Nel mio caso che uso solo l’ fstream non avrei alcun cambiamento?

Poi oltre alla questione della velocità di input/output che è interessante, riguardo l’algoritmo stesso, c’è un modo migliore per risolvere il problema?

Cordiali Saluti,
Simone
4

Al posto di usare l’operazione del resto per vedere se è pari o dispari, puoi usare l’AND bit a bit, in questo modo:

if(temp&1)

//dispari

else

//pari
5
Al posto di usare l'operazione del resto per vedere se è pari o dispari, puoi usare l'AND bit a bit, in questo modo:
if(temp&1)
    //dispari
else
    //pari

Lawliet

Nah, io non starei a fare queste "ottimizzazioni"... Il compilatore spesso e volentieri sa già farle (e le fa) di suo :)

Grazie della risposta,
Cosa succede nel caso io disattivi la sincronizzazione e faccia una cosa del genere:

sync_with_stdio(false);
cin>>a;
scanf("%d",b);
cout<<a;
printf("%d",b);

simone.pri

Non succedono cose belle, suppongo... Nella peggiore delle ipotesi ti ritroveresti ad avere risultati corretti sul tuo PC ma errati sul server (o viceversa).

Disattivando la sincronizzazione ho miglioramenti solo quando utilizzo cin e cout giusto??
Nel mio caso che uso solo l' fstream non avrei alcun cambiamento?

simone.pri

Credo di sì... Ma comunque tieni conto che la lettura da file sta diventando sempre più una cosa superflua. Ormai alle IOI e anche alle OII viene richiesto solo di implementare una certa funzione, ad esempio int solve(int N, int input[]), che restituisca il risultato corretto, quindi l'input ti viene già dato, non devi leggerlo.

Poi oltre alla questione della velocità di input/output che è interessante, riguardo l'algoritmo stesso, c'è un modo migliore per risolvere il problema?

simone.pri

Beh, in termini di complessità direi che non puoi fare meglio di un algoritmo lineare (il tuo è lineare vero?), e in genere (alle olimpiadi) se hai la complessità giusta non è necessario stare ad ottimizzare (infatti i time limit sono molto superiori del necessario, e la "soluzione campione" generalmente passa con parecchio margine di tempo).
6
Al posto di usare l'operazione del resto per vedere se è pari o dispari, puoi usare l'AND bit a bit, in questo modo:
if(temp&1)
    //dispari
else
    //pari

Lawliet

Nah, io non starei a fare queste "ottimizzazioni"... Il compilatore spesso e volentieri sa già farle (e le fa) di suo :)

wil93

Vero e facilmente verificabile sul campo.

Questo è il (minimo?) codice C++ che lo dimostra:
#include <iostream>

using namespace std;

int main()

{

for (int i = 0; i < 10; i++)

{

if (i % 2) cout << “Even”;

if (i & 1) cout << “Even, fastly?”;

}

}
 
Il compilatore g++ traduce entrambe le condizioni con l’istruzione assembly
andl	$1, %eax
che corrisponde all’AND bit a bit tra due long.

7

Vi ringrazio per i chiarimenti.

8

Allora sarà stata solo una coincidenza che il tempo è migliorato. Non sapevo di quest’aspetto del compilatore, grazie :wink: