BENCHMARK CPU in C++: Parere

[cionci]

Originariamente inviato da ^TiGeRShArK^

con un solo ciclo di clock???? MITIIIIIICOOOO!

For...

[3nigma666]

kla storia del sottovettore massimo la conoscevo gia,ho scelto solo il quicksort a posto dell'algoritmo da te descritto,in quanto lo ritenevo piu efficace x studiarne l effettiva capacita di calcolo di un processore,in quanto è semplice dare in pasto al processore un algoritmo di costo computazionale lineare...In questa maniera non si testa a mio avviso l effettiva efficienza del processore,bisogna dare in "pasto" alla cpu algoritmi un attimino piu sostanzioni come costo computazionale,la piu o meno efficienza serve "solo" per ottenere piu velocemente il risultato.Per questo motivo ho scelto il QuickSort ke ha complessita a mio avviso molto piu interessante T(n) = O(nlogn) piuttosto ke il tuo ke per dare risultati simili puo avere slo costo di T(n) = O(n) quindi lineare. Potevio prendere altri algoritmi tipo le otimizzazioni del quickSort con Insertion SOrt o con Heap Sort,ma incominciavano ad avere un costo com,putazionale troppo basso e quindi non piu interessante.Decisamente piu efficace sarebbe lo stdio dei frattali ,ma ahime ancora non ho la teoria sufficiente alle spalle per poter affrontare tale argomento..so ke purtroppo è limitato il mio benchmark in quanto non si puo efficaciemente studiare la velocita con la uqale si interfaccia con la cache e ke quantita di dati puo trasportare,devo ovviamente migliorerare questo aspetto. Cionci corregimi se sbaglio,potrei osservare la velocita di "dialogo" con la cache dichiarando le variabili con il tipo: register int. Pero sapevo ke spesso il compilatore automaticamente se non riesce ad allocare in cache alloca in ram,senza comunicare niente all'utente!
Per quanto riguarda l'algoritmo del tuo professore,correggimi se sbaglio ma penso ke abbia fatto un cosa del genere:

una funzione piu generale ke chaimeremo
PESO MAX: non fa altro ke richiamare dentro ad un unico ciclo for la funzione CALCOLA_PESO
CALCOLA_PESO: somma il valore i-esimo del vettore a somma temporanea dei valori contigui presenti,e se la somma è maggiore di quella massima precedentemente trovata (il caso base ovviamente è somma = 0)
la sostituisce e ricorsivamente richiama se stesso fino fine vettore.
Inoltre calcola peso ritonora il valore dell'indice i uguale all'inizio del vettore contiguo sucecsisvo a quello appena analizzato.

cosi basta 1 solo ciclo for,certo mancano alcune chirificazioni e controlli degli indici ma credo ke l idea di base sia corretta no?? se puoi postaci lo pseudo codice del tuo prof

[cionci]

E quello dentro a CALCOLA_PESO che ciclo è ?!?!!? E' un ciclo anche quello...

Riguardo al register...register può tranquillamente non essere rispettato dal compilatore... In ogni caso register significa che il compilatore tenta di memroizzare la variabile all'interno dei registri del processore, quindi in teoria con la cache non ha niente a che vedere...

[71104]

Originariamente inviato da cionci

Ho appena finito...con un solo ciclo di clock e trova anche l'inizio e la fine del sottovettore...

ehm...
ma scusa quanti elementi ci hai messo nel vettore? quanto ci mette la tua soluzione con 10 milioni di elementi? mi posti il codice che hai scritto?
NON E' CHE NON CI CREDO, EH!!! (nnnnuuuuuuuuuuuuuuuuuu... ), è solo che sai, come dire, dal momento che un solo ciclo di clock non basta manco a fare una comparazione...

PS: non ti do un bel niente se riesci a realizzarmelo tu l'algoritmo; casomai al mio professore, non a te!

[71104]

Originariamente inviato da cionci

For...

ma LOL l'ho letto ora
e che ragionamento hai fatto?
(non mi venire a dire che hai copiato un algoritmo trovato su Google...)

[71104]

Originariamente inviato da 3nigma666

Per quanto riguarda l'algoritmo del tuo professore,correggimi se sbaglio ma penso ke abbia fatto un cosa del genere:

una funzione piu generale ke chaimeremo
PESO MAX: non fa altro ke richiamare dentro ad un unico ciclo for la funzione CALCOLA_PESO
CALCOLA_PESO: somma il valore i-esimo del vettore a somma temporanea dei valori contigui presenti,e se la somma è maggiore di quella massima precedentemente trovata (il caso base ovviamente è somma = 0)
la sostituisce e ricorsivamente richiama se stesso fino fine vettore.
Inoltre calcola peso ritonora il valore dell'indice i uguale all'inizio del vettore contiguo sucecsisvo a quello appena analizzato.

cosi basta 1 solo ciclo for,certo mancano alcune chirificazioni e controlli degli indici ma credo ke l idea di base sia corretta no?? se puoi postaci lo pseudo codice del tuo prof

assolutamente NO!!! l'algoritmo del prof. non era ricorsivo!!! (gli algoritmi ricorsivi ci mettono troppo tempo)
era iterativo purissimo!!!
cmq lo pseudocodice non te lo posto finché cionci non posta il suo

EDIT: aggiungo anche che l'algoritmo del prof., supponendo di avere a disposizione una funzioncina Max che calcola il massimo tra due valori, era lungo esattamente 6 righe!!!!!!
(cmq non pensate chissacchè, l'algoritmo non l'ha inventato lui (figuriamoci ) l'ha letto su un libro; originariamente il problema era un problema di grafica)

[71104]

Originariamente inviato da 71104

aggiungo anche che l'algoritmo del prof., supponendo di avere a disposizione una funzioncina Max che calcola il massimo tra due valori, era lungo esattamente 6 righe!!!!!!

4 se escludiamo l'inizializzazione delle variabili

[cionci]

Originariamente inviato da 71104

ma LOL l'ho letto ora
e che ragionamento hai fatto?
(non mi venire a dire che hai copiato un algoritmo trovato su Google...)

Per ora è molto lento.... Stavo lavorando ad una versione nettamente più veloce (O(N)), ma devo gestire alcuni casi particolari in cui non mi torna...

Eccolo qui:

	for(i=1; ; ++i)
	{
		if(i > end)
		{
			if(somma > max)
			{
				max = somma;
				start_max = start;
				end_max = end;
			}

			somma = 0;
			if(++end == N)
				end = ++start; 

			i = start;
			if(i == N)
				break;
		}
		somma += v[i];
	}

[71104]

non vale, hai barato!!!
che bas****o!!!!
non puoi modificare il contatore i all'interno del ciclo for!!!
cmq funziona, però ti faccio presente che quell'algoritmo è pessimo, cioè bastano 2000 elementi per metterlo in difficoltà (8 secondi...)
la seconda versione del mio algoritmo veniva messa in difficoltà sui 100000 (tra i 10 e i 20 secondi, molto variabile), e l'ultima versione che ho fatto ha un costo di (N^2)/4 (inizia ad avere difficoltà sui 40000, 4 secondi se ricordo bene).
inoltre ho capito come funziona la versione del prof., ma realizzarla è molto difficile

[cionci]

Certo...lo so che è pessimo

[71104]

up!
allora cionci, la tua nuova versione?
ti arrendi e posto la soluzione di 6 righe?

[VICIUS]

Strano che non si sia ancora fatto vivo a2000 con una versione in vb da 3 righe con velocita sconvolgenti

ciao

[cionci]

Originariamente inviato da 71104

up!
allora cionci, la tua nuova versione?
ti arrendi e posto la soluzione di 6 righe?

Non ci ho più lavorato...comunque vai pure...

[71104]

RULLO DI TAMBURI
(ttrrrrrrrrrr...)

int i;
int max = 0, tail = 0;
for (i = 0; i < N; i++) {
    max = Max(max, v[i] + tail);
    tail = Max(0, v[i] + tail);
}

CIASSSSSSS!!! (onomatopea dei piatti alla fine del rullo di tamburi )

ovviamente:
- N è il numero di elementi
- v è il vettore (di N elementi)
- max alla fine contiene il risultato
- Max è una funzioncina che restituisce il massimo di due valori interi

stima dei tempi di calcolo: N!!!
(e ovviamente funziona... )

[DanieleC88]

Originariamente inviato da VICIUS

Strano che non si sia ancora fatto vivo a2000 con una versione in vb da 3 righe con velocita sconvolgenti

Già... Non ricordo in che discussione aveva postato quel codice fantastico di tre righe...

[71104]

ma chi è sto a2000? mica lo conosco... io sapevo di repne scasb, che ottimizzava in modo maniacale fino all'estremo e "aiutava" il compilatore scrivendo codice pressoché illeggibile, ma a2000 non l'ho mai visto

[DanieleC88]

Tempo fa l'avevo trovato in alcune discussioni, ma ora sembra essere scomparso.

[cionci]

Originariamente inviato da 71104

ma chi è sto a2000? mica lo conosco... io sapevo di repne scasb, che ottimizzava in modo maniacale fino all'estremo e "aiutava" il compilatore scrivendo codice pressoché illeggibile, ma a2000 non l'ho mai visto

Ci sono stati alcuni thread davvero mitici con a2000... E' un integralista del Fortran con una preparazione matematica notevole...

[71104]

Originariamente inviato da cionci

Ci sono stati alcuni thread davvero mitici con a2000... E' un integralista del Fortran con una preparazione matematica notevole...

O_o peccato non ci sia più, mi incuriosisce...

[DanieleC88]

Originariamente inviato da cionci

Ci sono stati alcuni thread davvero mitici con a2000... E' un integralista del Fortran con una preparazione matematica notevole...

Qualcuno mi parla un po' di Fortran? Non ho mai visto niente scritto in Fortran e non so che linguaggio è.

Preparazione matematica notevole... hmm, il mio opposto, allora.