[Vari] Contest 19: Full Text Search(e non solo).

[Vincenzo1968]

Si, su Windows XP a 32 bit, l'applicazione 2 di AnonimoVeneziano risulta più veloce di qualche secondo.

Vado a provare su Windows 8 a 64 bit.

[Vincenzo1968]

Originariamente inviato da AnonimoVeneziano

Ah ok, dopo provo a reperirlo.

@Vincenzo mo ti faccio lo screen :P (non è molto diverso da linux eh )

Edit:
Ecco

Originariamente inviato da VICIUS

Comunque. Non so come tu faccia a calcolare i tempi ma canni di brutto. Non ci ha messo neanche lontanamente 15 secondi a creare il file. Sia l'iphone che l'orologio da muro della cucina riportano lo stesso tempo di time.

Grazie mille a entrambi!

Come sarebbe canno?

int main(int argc, char* argv[])
{
	char szFileName[256];
	unsigned char *bufferIn  = NULL;
	unsigned char *bufferOut = NULL;
	long sizeBuffer;
	double Tempo1;
	double Tempo2;
	double Tempo3;
	double TempoTotale;
	uint64_t sizeOutput;
	clock_t c_start, c_end;


	if ( argc < 2 )
	{

#ifdef __linux__ 	
		PrintHelp(argv[0]);
#else
		ExtractFileName(argv[0], szFileName);
		PrintHelp(szFileName);
#endif

		printf("\nPremere INVIO per terminare.");
		getc(stdin);

		return -1;
	}

	//srand((unsigned)time(NULL));

	printf("\nElaborazione del file %s in corso.\nAttendere prego...\n", argv[1]);

	if ( argc >= 3 )
		sizeOutput = GetSizeOutput(argv[2]);
	else
		sizeOutput = 1024 * 1024;

	c_start = clock();
	sizeBuffer = MakeBuffer(&bufferIn);
	c_end = clock();
	Tempo1 = (double)(c_end - c_start) / CLOCKS_PER_SEC;
	printf("\nTempo impiegato per lettura dati -> %5.5f secondi\n", Tempo1);


	c_start = clock();
	sizeBuffer = DFA(bufferIn, &bufferOut, sizeBuffer);
	c_end = clock();
	Tempo2 = (double)(c_end - c_start) / CLOCKS_PER_SEC;
	printf("\nTempo impiegato per eliminare spazi e righe vuote -> %5.5f secondi\n", Tempo2);

	c_start = clock();
	Mescola(bufferOut, argv[1], sizeBuffer, sizeOutput);
	c_end = clock();
	Tempo3 = (double)(c_end - c_start) / CLOCKS_PER_SEC;
	printf("\nTempo impiegato per mescolare-> %5.5f secondi\n", Tempo3);

	TempoTotale = Tempo1 + Tempo2 + Tempo3;
	printf("\nTempo totale -> %5.5f secondi\n", TempoTotale);

	if ( bufferIn )
		free(bufferIn);
	else
		printf("\nbufferIn e' NULL.\n");

	if ( bufferOut )
		free(bufferOut);
	else
		printf("\nbufferOut e' NULL.\n");

	printf("\nPremere INVIO per terminare.");
	getc(stdin);

	return 0;
}

[Vincenzo1968]

7,15 + 8,51 = 15,66

che è approssimativamente uguale a 15,559944

[AnonimoVeneziano]

Credo che usando "clock" (sia io che te) calcoliamo il tempo CPU che le rispettive funzioni impiegano piuttosto che il tempo ver

Il tempo reale di "time" dovrebbe essere quello più giusto (comprendente sia il tempo CPU che il tempo di I/O utilizzato, che non è considerato da "clock"), mentre il nostro tempo (che dovrebbe essere uguale a sys+usr di time) indica il tempo CPU utilizzato dal programma per fare il suo lavoro lavoro.

IMHO

Ciao

[Vincenzo1968]

Originariamente inviato da AnonimoVeneziano

Credo che usando "clock" (sia io che te) calcoliamo il tempo CPU che le rispettive funzioni ci impiegano a terminare piuttosto dal tempo vero, che invece (visto che usiamo funzioni di I/O che non sono computate da clock) in realtà il tempo reale è più alto.

Il tempo reale di "time" dovrebbe essere quello più giusto (comprendente sia il tempo CPU che il tempo di IO), mentre il nostro tempo (che dovrebbe essere uguale a sys+usr di time) indica il tempo CPU utilizzato dal programma per fare il suo lavoro lavoro.

IMHO

Ciao

Minchia ma allora i nostri tempi, se ho ben capito, sono migliori di quelli mostrati a video con printf!
Giusto?

[AnonimoVeneziano]

Originariamente inviato da Vincenzo1968

Minchia ma allora i nostri tempi, se ho ben capito, sono migliori di quelli mostrati a video con printf!
Giusto?

No, sono peggiori. Scusa, ho fatto un casino col copy paste nel messaggio precedente e non si capisce niente

In pratica i nostri tempi considerano solo il tempo CPU utilizzato dal programma. Quando però fai una "fwrite" in realtà il tuo programma si blocca e passa al sistema operativo per fare I/O. Io non credo che quel tempo sia computato da "clock" , almeno su Mac (su win non so , ma credo che anche lì sia lo stesso).

Ciao

[AnonimoVeneziano]

Esempio dei nostri programmi:



Il tuo programma ci impiega 6.8+7.4s di tempo CPU a lavorare, ma in totale (a causa dell'IO) in realtà impiega 21.5s.

Il mio invece impiega 5.4+7.4s di tempo CPU (quindi in teoria un pochino più veloce) ma a causa dell'io ce ne impiega 21 di secondi.

Quindi la velocità netta delle due versioni è praticamente la stessa a causa dell'IO (il programma è IO bound), mentre la mia seconda versione non è in grado di saturare la banda dell'IO del mio SSD risultando in tempi totali un po' più lenta (nonostante usi meno tempo CPU).

Questa è la mia teoria a riguardo

Ciao

[Vincenzo1968]

In effetti il tempo "Real" è leggermente superiore:





Non c'è modo di prendere il tempo Real in C?

[AnonimoVeneziano]

Originariamente inviato da Vincenzo1968

In effetti il tempo "Real" è leggermente superiore:

Non c'è modo di prendere il tempo Real in C?

probabilmente utilizzando funzioni del sistema operativo che ti ritornano il tempo in millisecondi dall'inizio del programma ( o dalla epoch). "time()" non è adatta perchè ritorna secondi.

Su UNIX c'è "gettimeofday()" che ritorna secondi e microsecondi dalla epoch e si può usare per fare calcoli del genere. Per windows ci sarà un equivalente.

CLOCK comunque rimane il sistema migliore per calcolare le performance (a meno che non ci sia di mezzo dell'IO pesante come in questo caso)

[Vincenzo1968]

Alt! Fermi tutti!

Se tolgo "Premere INVIO per terminare" ottengo tempi real migliori:



Togliete dunque, nella funzione main, queste due righe di codice:

	printf("\nPremere INVIO per terminare.");
	getc(stdin);

D'ora in poi useremo il comando time per misurare i tempi. Io ve lo dicevo. Voi avete insistito per far stampare il tempo a video...

[Vincenzo1968]

Originariamente inviato da AnonimoVeneziano

probabilmente utilizzando funzioni del sistema operativo che ti ritornano il tempo in millisecondi dall'inizio del programma ( o dalla epoch). "time()" non è adatta perchè ritorna secondi.

Su UNIX c'è "gettimeofday()" che ritorna secondi e microsecondi dalla epoch e si può usare per fare calcoli del genere. Per windows ci sarà un equivalente.

CLOCK comunque rimane il sistema migliore per calcolare le performance (a meno che non ci sia di mezzo dell'IO pesante come in questo caso)

Ok! Allora per questo contest useremo sempre il comando time per calcolare i tempi.
Su Windows dovrebbe essere disponibile installando le GnuWin32 libraries(un porting di molti utili comandi unix su windows):

http://getgnuwin32.sourceforge.net/

[AnonimoVeneziano]

Originariamente inviato da Vincenzo1968

Alt| Fermi tutti!

Se tolgo "Premere INVIO per terminare" ottengo tempi real migliori:



Togliete dunque, nella funzione main, queste due righe di codice:

	printf("\nPremere INVIO per terminare.");
	getc(stdin);

D'ora in poi useremo il comando time per misurare i tempi. Io ve lo dicevo. Voi avete insistito per far stampare il tempo a video...

L'avevo già tolto.

[Vincenzo1968]

Niente da fare:



Il comando time non è disponibile su Windows nemmeno installando le GnuWin32.

Per questo contest utilizzerò Linux.

Windows



EDIT: o, meglio, i tempi li prenderò anche su Windows e mostrerò gli screenshot ma, per le classifiche, i tempi saranno quelli calcolati col comando time su Linux.

[Vincenzo1968]

[AnonimoVeneziano]

Ma in gnuwin32 non c'è time a disposizione?

[Vincenzo1968]

Originariamente inviato da AnonimoVeneziano

Ma in gnuwin32 non c'è time a disposizione?

Evidentemente no. Dando il comando mi dice che ho inserito l'ora sbagliata. (naturalmente ho GnuWin32 installato nel mio sistema da un bel pezzo per via di Flex e Bison. E ho anche messo il percorso in PATH nelle variabili d'ambiente Windows).

[Vincenzo1968]

C'è una cosa che non mi quadra nello screenshot di Vicius:

7,15 secondi user
8,51 secondi system
E real(totoal)? un minuto e trenta secondi?

Non può essere. Sia da me che da AnonimoVeneziano(sul suo Mac) la differenza tra il totale di user e system e real è di pochi secondi(tre, quattro, cinque al massimo; massimo massimo massimo dieci).

Che cacchio è?

[Vincenzo1968]

Originariamente inviato da Vincenzo1968

Niente da fare:



Il comando time non è disponibile su Windows nemmeno installando le GnuWin32.

Per questo contest utilizzerò Linux.

Windows



EDIT: o, meglio, i tempi li prenderò anche su Windows e mostrerò gli screenshot ma, per le classifiche, i tempi saranno quelli calcolati col comando time su Linux.

Però anche così, pensandoci bene, non mi pare giusto. Il tempo real mio e quello di AnonimoVeneziano coincidono ma lui utilizza un algoritmo-metodo un po' più efficiente rispetto al mio.

Che si può fare? come possiamo risolvere la cosa?

[Vincenzo1968]

Secondo me conviene, per la classifica, prendere i tempi user e system e sommarli.

Anche perché ho eliminato un paio di printf dal mio codice e il tempo real scende a 27 secondi circa(27 virgola qualcosa, quasi ventotto). Il che mi vedrebbe vincitore ma non è assolutamente giusto visto che l'algoritmo-metodo di AnonimoVeneziano è più efficiente del mio.

Ditemi che ne pensate.

[VICIUS]

Più veloce delle versioni C. Sia come tempo totale che come somma di user+system.

➜ Contest  time java -server Generate prova -D5GiB
ci ho messo 88 secondi
java -server Generate prova -D5GiB  6.74s user 5.79s system 14% cpu 1:28.81 total

Generate.java