View Full Version : Linguaggio di programmazione, quale e' il piu veloce?
Salve, sto cercando di risolvere un problema matematico;
ho realizzato il mio software in alcuni linguaggi, ma ho bisogno di piu velocita' ancora perche per giungere alla risoluzione dovranno essere fatti molti miliardi di miliardi di calcoli matematici.
Attualmente sto provando col QB64 (che se non sbaglio compila in C++) ma pur adottando la via di espandere il programma al massimo senza usare variabili del tipo a(10) che portano via molto tempo di calcolo, ma usando invece a1, a2, a3 etc, ancora la velocita' non e' abbastanza e ci impieghera' molti anni.
Inoltre il QB64 (come il quickbasic) non supporta il "goto 1000+a" ma solo goto fissi.
Questo ostacolo e' difficilmente aggirabile e con il ON a GOTO 1001,1002,1003 etc il sistema rallenda a dismisura quasi piu che scrivere decine di IF-GOTO.
..e con CALL la velocita rallenta ancora di piu'...
Domanda 1:
Quale e' un linguaggio di programmazione che mi puo dare piu velocita' di calcolo? magari con GOTO 1001+a (GOTO dinamici) ?
Domanda2:
Inoltre posso chedervi se qualcuno sa' la formula per sapere da quanti bit e' composto un mumero ?
es: premdiamo il numero 8 che in unsigned binario e' 1000 e quindi composto da 4 bit, esiste una formula veloce(la velocita' e' essenziale!) per sapere quanti bit occupa ??? (cioe' da 8 o 1000 ottenere 4 o 100)
Grazie in anticipo, Soniaa
Inviato dal mio Nexus 7 utilizzando Tapatalk
Non ho capito nulla di quello che hai scritto :D
Forse però ti conviene non usare i goto che sono il male, quasi assoluto :D
Detto questo per calcolare quanti bit necessita un numero si usano i logaritmi. Non ci si scappa.
numero_bit = ceil(ln(numero) / ln(2));
Ciao
ingframin
16-11-2013, 06:32
Salve, sto cercando di risolvere un problema matematico;
ho realizzato il mio software in alcuni linguaggi, ma ho bisogno di piu velocita' ancora perche per giungere alla risoluzione dovranno essere fatti molti miliardi di miliardi di calcoli matematici.
Attualmente sto provando col QB64 (che se non sbaglio compila in C++) ma pur adottando la via di espandere il programma al massimo senza usare variabili del tipo a(10) che portano via molto tempo di calcolo, ma usando invece a1, a2, a3 etc, ancora la velocita' non e' abbastanza e ci impieghera' molti anni.
Inoltre il QB64 (come il quickbasic) non supporta il "goto 1000+a" ma solo goto fissi.
Questo ostacolo e' difficilmente aggirabile e con il ON a GOTO 1001,1002,1003 etc il sistema rallenda a dismisura quasi piu che scrivere decine di IF-GOTO.
..e con CALL la velocita rallenta ancora di piu'...
Domanda 1:
Quale e' un linguaggio di programmazione che mi puo dare piu velocita' di calcolo? magari con GOTO 1001+a (GOTO dinamici) ?
Domanda2:
Inoltre posso chedervi se qualcuno sa' la formula per sapere da quanti bit e' composto un mumero ?
es: premdiamo il numero 8 che in unsigned binario e' 1000 e quindi composto da 4 bit, esiste una formula veloce(la velocita' e' essenziale!) per sapere quanti bit occupa ??? (cioe' da 8 o 1000 ottenere 4 o 100)
Grazie in anticipo, Soniaa
Quick basic era un interprete, non un compilatore.
Mostra il codice e ti possiamo dare una mano.
Che altri linguaggi hai usato? Hai provato Fortran?
http://www.fortrantutorial.com/
È considerato il nonno di matlab, è fatto per la matematica (fortran = formula translator) e non credo esistano linguaggi più rapidi,
a parte il linguaggio macchina.
cdimauro
16-11-2013, 07:06
In effetti Fortran ancora oggi rimane imbattuto per macinare numeri. Si potrebbe pensare di realizzare il core dell'algoritmo in assembly ottimizzato a manina, ma prima... bisognerebbe conoscere l'algoritmo da velocizzare, appunto.
Certamente per tirare fuori il numero di bit utilizzati non ricorrerei alla formuletta classica che è stata posta. A seconda dei casi (cioè del range di valori da elaborare), si potrebbe usare l'algoritmo di bisezione, una LUT, oppure una combinazione dei due.
In generale e per quanto possibile, è sempre meglio evitare l'uso di salti, specialmente se condizionati.
vendettaaaaa
16-11-2013, 12:19
In FORTRAN puoi usare dei GOTO "dinamici":
SUBROUTINE MYSUBWITHGOTO(K)
// dichiarazioni
C
GOTO (10,1,2,3,4,5,6,7,8,9,91,92,93,930,931,3,98,84,18,19,20,21,
# 22) K+1
C
Cioè a seconda del valore di K, salti alle label 10, 4, 91, 92...eccetera. Questo vale in FORTRAN77, non so se è una feature deprecata nelle versioni più recenti ma tieni conto che tutti i compilatori principali (Intel Fortran Compiler 13 e gfortran, parte di GCC) riconoscono tutte le sintassi FORTRAN dal 77 in poi.
||ElChE||88
16-11-2013, 13:04
"formula veloce"?
http://x86.renejeschke.de/html/file_module_x86_id_20.html
Spero non pensiate che il mio silenzio sia ingratitudine,...
..anzi vi RINGRAZIO tantissimo e avete risposto esattamente alle mie domande.
Ora elaboro i vostri consigli...dunque Fortran... uhmm, da una prima occhiata non sembra difficile...ce la potrei fare..credo...
stasera faro' un primo approccio al Fortran e qualche test di velocita' di puro calcolo matematico(a me serve solo puro calcolo,pero' man mano che il mio programma arrivera' a punti precisi, dovra' esportare in un normalissimo file txt circa 40 numeri...che alla fine diventeranno qualche miliardo,spero si possa col fortran salvare dati su file...non necessariamente grandi ma diverse migliaia di file (aprendoneo 1 alla volta e quando vi ho inserito esempio 1000000 di numeri, chiuderlo e aprirne un nuovo altro vuoto), poi vi dico...
Graziee
In FORTRAN puoi usare dei GOTO "dinamici":
SUBROUTINE MYSUBWITHGOTO(K)
// dichiarazioni
C
GOTO (10,1,2,3,4,5,6,7,8,9,91,92,93,930,931,3,98,84,18,19,20,21,
# 22) K+1
C
Cioè a seconda del valore di K, salti alle label 10, 4, 91, 92...eccetera. Questo vale in FORTRAN77, non so se è una feature deprecata nelle versioni più recenti ma tieni conto che tutti i compilatori principali (Intel Fortran Compiler 13 e gfortran, parte di GCC) riconoscono tutte le sintassi FORTRAN dal 77 in poi.
Certo che un GOTO di questo genere(che e' presente anche nel QB64"ON a GOTO 100,150,labelqqq,102,etc") richiede in esecuzione un tempo di elaborazione non indifferente,
ma non esistono piu i vecchi "GOTO 1000+a" oppure "GOTO a$" oppure "GOTO VAL (A$)"???
,..quelli si' che facevano girare i programmi veloce!!!
Quick basic era un interprete, non un compilatore.
Mostra il codice e ti possiamo dare una mano.
Che altri linguaggi hai usato? Hai provato Fortran?
http://www.fortrantutorial.com/
È considerato il nonno di matlab, è fatto per la matematica (fortran = formula translator) e non credo esistano linguaggi più rapidi,
a parte il linguaggio macchina.
QuickBasic puo' anche compilare (in C credo...)
QB64 compila solo, (in C++ credo) e la velocita' del C++ rispetto al C e' maggiore di circa 40 per cento sul mio programma...
lorenzo001
16-11-2013, 20:02
Potresti usare un vettore di puntatori a funzione in C ... mi sembra assurdo parlare di GOTO o ON GOTO ...
lorenzo001
16-11-2013, 20:19
Forse vuole dire che il compilatore trasforma il sorgente QB in un sorgente C che poi viene compilato da un compilatore C.
lorenzo001
16-11-2013, 20:33
Non mi pare succedesse per tutte le versioni di QB ma mi sembra di ricordare (è passato un po' di tempo) che il "Basmark QuickBASIC" (che ho usato su SCO Xenix) funzionasse così ...
vendettaaaaa
16-11-2013, 21:18
Spero non pensiate che il mio silenzio sia ingratitudine,...
..anzi vi RINGRAZIO tantissimo e avete risposto esattamente alle mie domande.
Ora elaboro i vostri consigli...dunque Fortran... uhmm, da una prima occhiata non sembra difficile...ce la potrei fare..credo...
stasera faro' un primo approccio al Fortran e qualche test di velocita' di puro calcolo matematico(a me serve solo puro calcolo,pero' man mano che il mio programma arrivera' a punti precisi, dovra' esportare in un normalissimo file txt circa 40 numeri...che alla fine diventeranno qualche miliardo,spero si possa col fortran salvare dati su file...non necessariamente grandi ma diverse migliaia di file (aprendoneo 1 alla volta e quando vi ho inserito esempio 1000000 di numeri, chiuderlo e aprirne un nuovo altro vuoto), poi vi dico...
Graziee
Io uso Fortran per lavoro ed eviterei di manipolare file di testo (o qualsiasi altra operazione di input/output) con quel maledetto linguaggio. Potresti scrivere le subroutine di calcolo in Fortran (se trovi che è davvero più veloce) e chiamarle dal C/C++, così una volta effettuato il calcolo ritornano a C il/i valore/i e dal C li salvi. Posto che la grande maggioranza del tempo di esecuzione stia nell subroutine, così questo espediente non ti toglierebbe preziosi cicli di clock.
Sto provando sto Fortran...
Rispetto al QB64;
piu veloce nei loop (il doppio/triplo)
piu veloce IF (+400%)
piu LENTO nel puro calcolo (-il doppio/triplo)
TEST 1 (FOR / LOOP) QB64 4.5sec Fortran 2.0sec ;)
QB64 code:
DIM a AS LONG
FOR a = 1 TO 1000000000
NEXT a
Fortran code:
program first
integer a
do a=1,1000000000
end do
end program first
TEST 2 (IF) QB64 12sec Fortran 5sec ;)
QB64 code:
DIM a AS LONG
FOR a = 1 TO 1000000000
IF b > a THEN b = 33
IF c > a THEN c = 44
IF d > a THEN d = 55
NEXT a
Fortran code:
program first
integer a,b,c,d
b=12
c=13
d=14
do a=1,1000000000
IF (b > a) b = 33
IF (c > a) c = 44
IF (d > a) d = 55
end do
end program first
TEST 3 (puro calcolo) ;) QB64 54sec Fortran 110sec
QB64 code:
DIM a AS LONG
FOR a = 1 TO 1000000000
b = a / 1003 + a / 1005
c = a / 1008 + a / 1002
d = a / 1001 + a / 1006
NEXT a
Fortran code:
program first
integer a,b,c,d
b=12
c=13
d=14
do a=1,1000000000
b = a / 1003 + a / 1005
c = a / 1008 + a / 1002
d = a / 1001 + a / 1006
end do
end program first
Non ho capito nulla di quello che hai scritto :D
Forse però ti conviene non usare i goto che sono il male, quasi assoluto :D
Detto questo per calcolare quanti bit necessita un numero si usano i logaritmi. Non ci si scappa.
numero_bit = ceil(ln(numero) / ln(2));
Ciao
Grazie per la formula...mi sara' MOLTOO utile!
ln immagino che sia log a base10 vero?
ma il ceil cosa significa? forse la parte intera?...ma allora alla tua formula bisogna alla fine aggiungere "+1" vero???
inoltre: se i GOTO sono sconsigliati allora cosa usi dei CALL/Function??? (che pero sono molto piu leenti dei GOTO!!!)
vendettaaaaa
17-11-2013, 08:27
p.s.: ln è il logaritmo naturale
Lascia perdere questa bigiolica sui goto. Sto cazzo di Djkstra ha fatto il lavaggio del cervello a tutti ormai...I goto non vanno quasi mai bene quando si implementa una logica, ed è ovvio, ma se li si vuole usare in casi come questo, dove svolgono la funzione di switch/case, in un pezzo di codice per il calcolo numerico dove non c'è neanche una logica da implementare, allora non rompete l'anima! :D
Io personalmente li uso in Fortran proprio in questo modo e non danno mai problemi. Tutt'altra cosa sarebbe usarli per rompere dei cicli o far cose logicamente meno ovvie.
Inoltre li uso nei programmini di test che faccio ogni tanto in C++ per tornare all'inizio dell'esecuzione se l'utente dice di continuare, molto più pratico che stare a wrappare tutto in un ciclo strutturato, e anche lì non si rischiano errori di alcun tipo...
Questo thread ha del paradossale, ancora non si è capito qual è il problema che l'utente dovrebbe risolvere :rolleyes:
Prima dovresti dirci cosa stai facendo e poi forse e dico forse ci si pone il problema del linguaggio (o meglio del compilatore).
Se ci sono problemi prestazionali la prima cosa da fare è capire se si sta adottando l'algoritmo corretto, dopodiché bisognerebbe assicurarsi che tu stia dicendo al compilatore di ottimizzare il codice per la velocità, per poi passare ad un profiling del codice e capire se l'utilizzo di cache e quant'altro avviene in maniera ottimale, se si possono usare istruzioni SIMD, multithreading e via discorrendo...
Così mi pare solo una perdita di tempo.
PS: la maggior parte dei processori moderni essendo dotata di branch prediction ottimizza le istruzioni di salto quindi se il codice è abbastanza predicibile le istruzioni di salto sono quasi gratuite.
PS2: se il problema che stai affrontando ha una natura vettoriale si potrebbe pensare di usare la GPU per eseguire questi calcoli.
Analizzando l'uso dei GOTO;
trovandomi nella situazione:
IF a=10 then
...bla bla bla per decine di righe...
END IF
...continuo programma...
cosi' perdo velocita', e' piu conveniente fare l'operazione contraria perche' in caso A<>10 comunque il processore legge tutto il codice per trovare "END IF" per trovare la prossima istruzione da esegiure!
IF a <> 10 then GOTO nextlabel
bla bla bla per decine di righe
END IF
nextlabel:
...continuo programma....
E nel caso di ON a GOTO
ON a GOTO 1001,1003,1004,1005,500,860,etc...
anche cosi' perdo velocita' (senza contare che e' difficilmente utilizzare una logica di questo tipo perche a puo essere a volte un numero grande!!)
risulta piu veloce fare (assurdo ma e' cosi'):
IF a=1 then GOTO 1001
IF a=2 then GOTO 1003
IF a=3 then GOTO 1004
etc...
per non parlare dei "SELECT CASE" che per elaborare cio' il processore ci mette una vita!
SELECT CASE a
case 1 GOTO 1001
case 2 GOTO 1003
case 3 GOTO 1004
Una volta con i vecchiii linguaggi si poteva usare
GOTO 1000+a oppure in caso di label "GOTO a$" o GOTO VAL(a$)
lorenzo001
17-11-2013, 10:53
In effetti così si perde tempo a seguire il discorso ...
Per ora non ha importanza il GOTO ma capire qual è il problema.
Cosa vuoi fare con il tuo programma che pensi di risolvere in quel modo?
Si, le vestre richieste di sapere a cosa sto lavorando sono lecite,
tuttavia vi informo che e' solo un hobby e null'altro.
Trovo le risposte che mi avete dato sino ad ora mooolto soddisfacenti
percui di fronte a tanta buona volonta' da parte vostra non trovo corretto rifiutarmi (perche soprattutto mi vergogno parecchio) di svelare...
Ripeto: e' solo un Hobby... e mi vergogno di fronte a voi 'espertisssssimi programmatori'...ma forse anche voi avrete imparato un po alla volta iniziando proprio da cavolate come queste? sbaglio???
Mi e' capitata sotto mano il PEG Solitaire (tavoliere inglese)
dopo ore/giorni) di gioco non sono mai riuscita a vincere,
poi ho tirato fuori il mio vecchio ZX spextrum e ho realizzato un software per trovare la soluzione, poi accortami che ci sarebbero voluti anni, ho usato un emulatore ZX sul pc e li' la volocita' e' aumentata parecchio spingendo il clock al massimo e anche il moltiplicatore, ma non era sufficiente e quindi ho usato un convertitore BASIC to ASSEMBLER, ma la velocita' non era ancora abbastanza,
quindi ho dovuto aggiornarmi e imparare il Qbasic, e' stata una impresa per me!, ma dovevo aggionarmi (dal giurassico al medievale:stordita: )
La soluzione e' presto arrivata, ma ora c'e un pensiero che mi stordisce la testa giorno e notte:
voglio trovare TUTTE le soluzioni possibili!
quindi mi serve mooolta piu velocita'
mi sono accorta che il qbasic e' si piu veloce ma ha delle notevoli limitazioni
(non ha i GOTO/GOSUB 1000+a)
e l'uso di variabili del tipo a(1) a(2) a(3) portano via mooolto tempo di elaborazione e cosi mi e' toccato scrivere tutte le 33 mosse moltiplicato per 32 pedine (ho usato WORD trova e sostituisci ovviamente)
Poi mi sono accorta che la memoria in Qbasic e' poca e quindi ho provato il QuickBasic, ma ancora non basta la memoria
Poi ho trovato il QB64
qui la memoria e' abbastanza, ma comunque non tutta quella che mi servirebbe...ma diciamo che riesco ad adattarmi...
Comunque servono 100 anni per trovare tutte le soluzioni (miliardi di combinazioni diverse!!)
Ora l'idea di interpretare il mio programma in una logica binaria
il numero da elaborare e' di 33 bit (33 sono i fori della scacchiera) e cosi' non devo usare variabili del tipo a(1) a(2) ma solo variabili a1,a2,a3,a4 etc
quindi:
esempio:a=&B100000000011111000001111100000111
per trovare velocemente le pedine da muovere e non passare tutti i bit cercando il prossimo a valore 1 userei il logaritmo che mi avete consigliato:
la prima pedina esistente la posso trovare cosi':
if a>&B 100000000000000000000000000000000 (significa che nella scacchiera il foro 1 e' occupato)
la prossima e';
33(decimale) - (INT(ln &B10000000000000000000000000000000))/(ln 2)+1
e cosi' via
ancora non ho testato questa logica, e' per questo che ho chiesto se vi era una formula, e mi e' stata data, ora la provero'....
ho anche chiesto appunto visto che devo riscrivere l'intero programma se mi conveniva scriverlo in un linguaggio piu veloce perche ho il presentimanto che anche cosi ci vorranno anni di calcoli....
Arrampicandomi sugli specchi potre considerare anche che ho diversi PC a casa e sono multiprocessore X4 e X8,
quindi potrei 'scorporare' il programma e farlo elaborare a pezzi su diversi pc,,
se ho ho 1 pc a 8 processori e 4 pc a 4 processori vuol dire che riesco a processare (1 x 8) + (4 x 4) =24 ad una velocita x 24 volte
Ciao, ora ridete pure :mc: :mad:
NorysLintas
17-11-2013, 13:22
Che io sappia e come ti è stato già detto, se questo hobby e la tua pazienza te lo permettono, impara l'assembly e riformula l'algoritmo.
E' il linguaggio di programmazione di livello più basso e di conseguenza è anche il più veloce, se poi sbaglio correggetemi.
lorenzo001
17-11-2013, 14:51
Se lo riscrive in C usando un buon compilatore che usa decenti criteri di ottimizzazione, ottiene sicuramente un risultato apprezzabile.
ingframin
17-11-2013, 14:54
Non è necessario imparare assembly, è solo necessario aggiornarsi un poco
e riscrivere il programma in un linguaggio moderno facendo uso di cose moderne.
Puoi perfino usare Java secondo me...
http://it.wikipedia.org/wiki/Peg_Solitaire
Il problema è NP complesso effettivamente, però secondo me ce la fai anche senza spendere anni ;)
epimerasi
17-11-2013, 14:54
Si, le vestre richieste di sapere a cosa sto lavorando sono lecite,
tuttavia vi informo che e' solo un hobby e null'altro.
Trovo le risposte che mi avete dato sino ad ora mooolto soddisfacenti
percui di fronte a tanta buona volonta' da parte vostra non trovo corretto rifiutarmi (perche soprattutto mi vergogno parecchio) di svelare...
Ripeto: e' solo un Hobby... e mi vergogno di fronte a voi 'espertisssssimi programmatori'...ma forse anche voi avrete imparato un po alla volta iniziando proprio da cavolate come queste? sbaglio???
Mi e' capitata sotto mano il PEG Solitaire (tavoliere inglese)
dopo ore/giorni) di gioco non sono mai riuscita a vincere,
poi ho tirato fuori il mio vecchio ZX spextrum e ho realizzato un software per trovare la soluzione, poi accortami che ci sarebbero voluti anni, ho usato un emulatore ZX sul pc e li' la volocita' e' aumentata parecchio spingendo il clock al massimo e anche il moltiplicatore, ma non era sufficiente e quindi ho usato un convertitore BASIC to ASSEMBLER, ma la velocita' non era ancora abbastanza,
quindi ho dovuto aggiornarmi e imparare il Qbasic, e' stata una impresa per me!, ma dovevo aggionarmi (dal giurassico al medievale:stordita: )
La soluzione e' presto arrivata, ma ora c'e un pensiero che mi stordisce la testa giorno e notte:
voglio trovare TUTTE le soluzioni possibili!
quindi mi serve mooolta piu velocita'
mi sono accorta che il qbasic e' si piu veloce ma ha delle notevoli limitazioni
(non ha i GOTO/GOSUB 1000+a)
e l'uso di variabili del tipo a(1) a(2) a(3) portano via mooolto tempo di elaborazione e cosi mi e' toccato scrivere tutte le 33 mosse moltiplicato per 32 pedine (ho usato WORD trova e sostituisci ovviamente)
Poi mi sono accorta che la memoria in Qbasic e' poca e quindi ho provato il QuickBasic, ma ancora non basta la memoria
Poi ho trovato il QB64
qui la memoria e' abbastanza, ma comunque non tutta quella che mi servirebbe...ma diciamo che riesco ad adattarmi...
Comunque servono 100 anni per trovare tutte le soluzioni (miliardi di combinazioni diverse!!)
Ora l'idea di interpretare il mio programma in una logica binaria
il numero da elaborare e' di 33 bit (33 sono i fori della scacchiera) e cosi' non devo usare variabili del tipo a(1) a(2) ma solo variabili a1,a2,a3,a4 etc
quindi:
esempio:a=&B100000000011111000001111100000111
per trovare velocemente le pedine da muovere e non passare tutti i bit cercando il prossimo a valore 1 userei il logaritmo che mi avete consigliato:
la prima pedina esistente la posso trovare cosi':
if a>&B 100000000000000000000000000000000 (significa che nella scacchiera il foro 1 e' occupato)
la prossima e';
33(decimale) - (INT(ln &B10000000000000000000000000000000))/(ln 2)+1
e cosi' via
ancora non ho testato questa logica, e' per questo che ho chiesto se vi era una formula, e mi e' stata data, ora la provero'....
ho anche chiesto appunto visto che devo riscrivere l'intero programma se mi conveniva scriverlo in un linguaggio piu veloce perche ho il presentimanto che anche cosi ci vorranno anni di calcoli....
Arrampicandomi sugli specchi potre considerare anche che ho diversi PC a casa e sono multiprocessore X4 e X8,
quindi potrei 'scorporare' il programma e farlo elaborare a pezzi su diversi pc,,
se ho ho 1 pc a 8 processori e 4 pc a 4 processori vuol dire che riesco a processare (1 x 8) + (4 x 4) =24 ad una velocita x 24 volte
Ciao, ora ridete pure :mc: :mad:
Stai cercando di risolvere un problema NP-completo.
A seconda della dimensione dell'istanza del problema (e si fa molto presto ad arrivarci con questo tipo di problemi), potrebbe non bastarti neanche il computer della NSA.
http://en.wikipedia.org/wiki/Peg_solitaire#Studies_on_peg_solitaire
http://xorshammer.com/2008/11/03/how-to-show-that-games-are-hard/
http://en.wikipedia.org/wiki/NP-completeness
Che sfiga eh... 33 bit :p
TEST 3 (puro calcolo) ;) QB64 54sec Fortran 110sec
QB64 code:
DIM a AS LONG
FOR a = 1 TO 1000000000
b = a / 1003 + a / 1005
c = a / 1008 + a / 1002
d = a / 1001 + a / 1006
NEXT a
Fortran code:
program first
integer a,b,c,d
b=12
c=13
d=14
do a=1,1000000000
b = a / 1003 + a / 1005
c = a / 1008 + a / 1002
d = a / 1001 + a / 1006
end do
end program first
C# 21 sec.
(Ma non sono paragonabili, ovviamente la mia macchina e' diversa dalla tua)
static void Main(string[] args)
{
int b,c,d;
b=12;
c=13;
d=14;
Stopwatch sw = Stopwatch.StartNew();
Parallel.For(1, 1000000000, a =>
{
var b1 = a / 1003 + a / 1005;
var c1 = a / 1008 + a / 1002;
var d1 = a / 1001 + a / 1006;
});
sw.Stop();
Console.WriteLine("Elapsed {0}sec", sw.ElapsedMilliseconds / 1000);
Console.ReadKey();
}
Immagino in C venga fuori ancora meglio
ingframin
20-11-2013, 11:43
C# 21 sec.
(Ma non sono paragonabili, ovviamente la mia macchina e' diversa dalla tua)
static void Main(string[] args)
{
int b,c,d;
b=12;
c=13;
d=14;
Stopwatch sw = Stopwatch.StartNew();
Parallel.For(1, 1000000000, a =>
{
var b1 = a / 1003 + a / 1005;
var c1 = a / 1008 + a / 1002;
var d1 = a / 1001 + a / 1006;
});
sw.Stop();
Console.WriteLine("Elapsed {0}sec", sw.ElapsedMilliseconds / 1000);
Console.ReadKey();
}
Immagino in C venga fuori ancora meglio
package spdtst;
public class SpeedTest {
public static void main(String[] args) {
long b,c,d;
b=12;
c=13;
d=14;
long now = System.nanoTime();
for(int a=0;a<1000000000;a++){
long b1 = a / 1003 + a / 1005;
long c1 = a / 1008 + a / 1002;
long d1 = a / 1001 + a / 1006;
}
long stop = System.nanoTime();
System.out.println("Elapsed time=");
System.out.println((stop-now)/1000);
}
}
Java da dentro Eclipse impiega tra i 5 e gli 8 ms
Secondo me c'e' qualcosa che rallenta il tuo codice c# oppure ho sbagliato io a tradurre il sorgente.
ingframin
20-11-2013, 13:41
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
long b,c,d;
int a;
long b1;
long c1;
long d1;
clock_t start, stop;
b=12;
c=13;
d=14;
start = clock();
for(a=0;a<1000000000;a++){
b1 = a / 1003 + a / 1005;
c1 = a / 1008 + a / 1002;
d1 = a / 1001 + a / 1006;
}
stop = clock();
printf("Elapsed time=\t%.9f\t%.9f",stop,start);
return 0;
}
Questo e' in C. Pero' c'e' qualcosa che non mi torna nella misura dei tempi...
printf("Elapsed time=\t%.9f\t%.9f",stop,start);
Questo e' in C. Pero' c'e' qualcosa che non mi torna nella misura dei tempi...
Prova così:
printf("Elapsed time: %f\n", (stop - start) / CLK_TCK);
La misurazione che hai fatto col programma Java è evidentemente sbagliata.
vendettaaaaa
20-11-2013, 14:18
@infrag e gugo: grazie al cazzo, non usate le variabili quindi in release il compilatore salta tutto il ciclo a piè pari!! :D
Nel ciclo cmq assegnate a b, c e d, non create delle var (o dei long) aggiuntive visto che il codice originale assegna a b, c, d.
Fate stampare b alla fine, insieme al tempo, e vedrete che in release ci vorranno un paio di secondi almeno (2 sec sul mio i5 vecchio di 2 anni).
vendettaaaaa
20-11-2013, 14:52
Su i7 3770K @default:
con MinGW 4.8.1 in DEBUG (perchè in release MinGW salta il ciclo e calcola direttamente b con a = 1000000000, mettendoci 0 secondi):
https://public.bn1.livefilestore.com/y2pyFp8NqIy768DA_HVb7BoWE7OdSWY9NwIrga_ooZ_MQ7yZJXl1N2cnerrjaPo94R-4DaVbRlPovuGOhLX-fm-SyAKSvZ1trQjuKlSc-XNrko/SpeedTestCPP.JPG?psid=1
con gfortran 4.8.1 in DEBUG:
https://public.bn1.livefilestore.com/y2pnLP-U8tmMj2AbuqtqPATshd8Ue0vQz93icLtOU2J60hD6b8tJuJxabblXmG3aFngd37m_cOQHZtZ8pv39bB_d4HazdUfmzSrC30dpId24xo/SpeedTestF77.JPG?psid=1
Con gfortran in release ci mette 1.9 secondi circa, quindi siamo lì, il limite inferiore è sui 2 secondi con questa potenza di calcolo.
ingframin
20-11-2013, 15:22
Prova così:
printf("Elapsed time: %f\n", (stop - start) / CLK_TCK);
La misurazione che hai fatto col programma Java è evidentemente sbagliata.
Mi spieghi come correggerla quella in Java?
Credevo che usando System.nanoTime() venisse precisa la misura.
Quello che non mi torna e' la precisione.
Da documentazione sono nanosecondi, quindi diviso 1000 sono microsecondi.
~5000 microsecondi sono millisecondi.
Dove sbaglio?
Execution time datomi da Codeblocks per la versione in C=0.010s... Sono 10 millisecondi.
Anche con la printf che mi suggerisci tu mi stampa sempre elapsed time 0.000000
EDIT:
Stampando le variabili il tempo della versione Java sale a circa 9s
Il tempo della versione in C rimane sui 12ms :O
vendettaaaaa
20-11-2013, 15:26
Mi spieghi come correggerla quella in Java?
Credevo che usando System.nanoTime() venisse precisa la misura.
Quello che non mi torna e' la precisione.
Da documentazione sono nanosecondi, quindi diviso 1000 sono microsecondi.
~5000 microsecondi sono millisecondi.
Dove sbaglio?
Non so se hai letto, ma al 99% delle probabilità il ciclo che hai scritto viene (intelligentemente) saltato in toto dal compilatore, per quello ci mette solo 8 millisecondi.
Per curiosità ho provato sul mio mac i7-3770, in terminale.
Quindi ho usato time da li.
compilando con gcc senza nessuna ottimizzazione:
B= 1992032
real 0m9.285s
user 0m9.278s
sys 0m0.006s
gcc -O2:
B= 1992032
real 0m0.003s
user 0m0.001s
sys 0m0.001s
:sofico:
vendettaaaaa
20-11-2013, 15:28
Per curiosità ho provato sul mio mac i7-3770, in terminale.
Quindi ho usato time da li.
compilando con gcc senza nessuna ottimizzazione:
B= 1992032
real 0m9.285s
user 0m9.278s
sys 0m0.006s
gcc -O2:
B= 1992032
real 0m0.003s
user 0m0.001s
sys 0m0.001s
:sofico:
gcc con le ottimizzazioni calcola il ciclo con a = 999999999 (cioè l'ultimo valore), per quello ho fatto le prove in debug.
ingframin
20-11-2013, 15:48
Non so se hai letto, ma al 99% delle probabilità il ciclo che hai scritto viene (intelligentemente) saltato in toto dal compilatore, per quello ci mette solo 8 millisecondi.
Hai risposto prima che editassi il mio post ;)
Ora mi trovo circa 9s in Java e circa 12ms in C.
Direi che ha senso...
Ma cmq ancora non mi spiego come e' possibile che la versione in C# impieghi 21 s...
vendettaaaaa
20-11-2013, 15:53
Hai risposto prima che editassi il mio post ;)
Ora mi trovo circa 9s in Java e circa 12ms in C.
Direi che ha senso...
Ma cmq ancora non mi spiego come e' possibile che la versione in C# impieghi 21 s...
gfortran ci mette 1.9s in release, e fortran se non è più veloce del C, sicuramente non è più lento :D
Probabilmente anche nel tuo test in C il ciclo viene calcolato solo alla fine.
Hai risposto prima che editassi il mio post ;)
Ora mi trovo circa 9s in Java e circa 12ms in C.
Direi che ha senso...
Ma cmq ancora non mi spiego come e' possibile che la versione in C# impieghi 21 s...
No, secondo me non ha senso. 12ms è troppo poco. Sul mio PC ho valori comunque sulla decina di secondi. Anche andando a naso, 12ms per quel miliardo di iterazioni non è ipotizzabile.
ingframin
20-11-2013, 16:24
fare 1 miliardo di iterazioni con 6 operazioni per iterazione in 12 ms non e' molto verosimile... :D
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
long b,c,d;
int a;
long b1;
long c1;
long d1;
int i;
clock_t start, stop;
b=12;
c=13;
d=14;
for(i=0;i<100;i++){
start = clock();
for(a=0;a<1000000000;a++){
b1 = a / 1003 + a / 1005;
c1 = a / 1008 + a / 1002;
d1 = a / 1001 + a / 1006;
}
stop = clock();
printf("Elapsed time=\t%f\n",(stop-start)/CLK_TCK);
printf("%d\t%d\t%d\n",b1,c1,d1);
}
return 0;
}
Io non so dove e' l'errore allora.
Ci provate voi a farlo girare?
Se compili con gcc usa l'opzione -O0 (O grande e zero) che appunto disabilita ogni ottimizzazione (anche se di default dovrebbe proprio essere così).
Se compili con gcc usa l'opzione -O0 (O grande e zero) che appunto disabilita ogni ottimizzazione (anche se di default dovrebbe proprio essere così).
le ottimizzazioni quante bestemmie, mi ricordo ancora dei giorni persi a debuggare un pezzo di codice fondamentalmente giusto ma che il compilatore ottimizzava saltando gli assegnamenti ad una struttura e di conseguenza non inizializzandomi i porti GRRRRR
scherzi a parte non esiste un linguaggio più veloce degli altri tutto dipende da cosa ci vuoi fare e devi considerare anche le eventuali ottimizzazioni che puoi ottenere sfruttando il multithreading o il gpgpu
anche perchè se le operazioni sono semplici ve lo dico io quiale è il linguaggio più veloce: fai tutto in VHDL e vedrai come scheggia :D :D :D :D :D :D
C# 21 sec.
(Ma non sono paragonabili, ovviamente la mia macchina e' diversa dalla tua)
static void Main(string[] args)
{
int b,c,d;
b=12;
c=13;
d=14;
Stopwatch sw = Stopwatch.StartNew();
Parallel.For(1, 1000000000, a =>
{
var b1 = a / 1003 + a / 1005;
var c1 = a / 1008 + a / 1002;
var d1 = a / 1001 + a / 1006;
});
sw.Stop();
Console.WriteLine("Elapsed {0}sec", sw.ElapsedMilliseconds / 1000);
Console.ReadKey();
}
Immagino in C venga fuori ancora meglio
Come detto da vendettaaaaa il codice viene ottimizzato, ma giusto per cronaca e senza prendere il tutto troppo seriamente:
void benchmark(int b, int c, int d)
{
#pragma omp parallel for
for(int i = 1; i < 1000000000; ++i)
{
int b1 = i / 1003 + i / 1005;
int c1 = i / 1008 + i / 1002;
int d1 = i / 1001 + i / 1006;
}
}
Con OpenMP il codice è anche altrettanto chiaro rispetto la versione C# con TPL
Per curiosità, di quanti incrementi mettendo il tutto sotto un blocco unchecked?
ingframin
20-11-2013, 21:13
Se compili con gcc usa l'opzione -O0 (O grande e zero) che appunto disabilita ogni ottimizzazione (anche se di default dovrebbe proprio essere così).
Si ho le ottimizzazioni attive a O3 :D
Stasera non ho fatto in tempo a metterci mano, domani le disattivo e ricompilo.
mone.java
21-11-2013, 08:50
Parlo da perfetto profano, ma ho sentito dire che i compilatore della intel fanno letteralmente i miracoli, qualcuno di voi li ha provati? in questo caso possono essere utili? (lo chiedo più per curiosità personale che per altro, ma mi sembra attinente all'argomento)
epimerasi
21-11-2013, 20:24
Parlo da perfetto profano, ma ho sentito dire che i compilatore della intel fanno letteralmente i miracoli, qualcuno di voi li ha provati? in questo caso possono essere utili? (lo chiedo più per curiosità personale che per altro, ma mi sembra attinente all'argomento)
Il limite del problema è algoritmico, non è questione di linguaggi.
Il linguaggio macchina :sofico:
paolomec
26-11-2013, 18:43
agat scherza ma non troppo.
Credo che il C sia il linguaggio ad alto livello più veloce, perché è più vicino alla macchina di altri, meno certo dell'assembler.
I cicli iterativi, poi, credo che possano essere gestiti, se non ricordo male ma se non è più così correggetemi, con variabili register, cioè variabili che vengono elaborate direttamente nei registri interni di sistema, non nella ram, più esterna. Questo solo se il registro vien trovato libero e disponibile per tale operazione.
In tal caso l'operazione è velocissima.
Non credo che altri linguaggi, tipo Java per intenderci, diano al programmatore questa chance, ma potrebbe essere, visto che io il Java non lo conosco.
cdimauro
26-11-2013, 21:12
agat scherza ma non troppo.
Credo che il C sia il linguaggio ad alto livello più veloce, perché è più vicino alla macchina di altri, meno certo dell'assembler.
No, non è il più vicino alla macchina, nemmeno togliendo di mezzo l'assembly, perché non ha nulla che possa avvicinarlo alla macchina.
E non è nemmeno il più veloce. Il C++ è sicuramente più veloce, mentre per calcoli massicciamente paralleli il Fortran finora rimane saldamente al primo posto.
I cicli iterativi, poi, credo che possano essere gestiti, se non ricordo male ma se non è più così correggetemi, con variabili register, cioè variabili che vengono elaborate direttamente nei registri interni di sistema, non nella ram, più esterna. Questo solo se il registro vien trovato libero e disponibile per tale operazione.
In tal caso l'operazione è velocissima.
Questo lo fanno anche altri linguaggi. Ma il punto è che puoi dare soltanto delle indicazioni al compilatore, ma quest'ultimo le può tranquillamente ignorare.
Inoltre oggi è inutile utilizzare keyword come register: i compilatori hanno sofisticati algoritmi di allocazione dei registri che consentono di tirare fuori codice abbastanza ottimizzato da evitarti di insozzare il codice infarcendolo di register.
Un discorso simile vale per l'inline.
Non credo che altri linguaggi, tipo Java per intenderci, diano al programmatore questa chance, ma potrebbe essere, visto che io il Java non lo conosco.
No, e non ce n'è bisogno per quanto detto sopra.
vendettaaaaa
26-11-2013, 22:52
E non è nemmeno il più veloce. Il C++ è sicuramente più veloce, mentre per calcoli massicciamente paralleli il Fortran finora rimane saldamente al primo posto.
Cosa intendi con "massicciamente paralleli"? E parli sempre di prestazioni sulla CPU?
AnonimoVeneziano
27-11-2013, 11:35
E non è nemmeno il più veloce. Il C++ è sicuramente più veloce, mentre per calcoli massicciamente paralleli il Fortran finora rimane saldamente al primo posto.
Puoi argomentare e fornire un esempio please? Sono genuinamente interessato :) (soprattutto sulla prima parte della affermazione).
io rimango fedele al vhdl come linguaggio più veloce
che è pure più veloce del linguaggio macchina
:D :D :D :D :D :D :D :D :D
vendettaaaaa
27-11-2013, 11:47
Puoi argomentare e fornire un esempio please? Sono genuinamente interessato :) (soprattutto sulla prima parte della affermazione).
Idem, non pensavo che il C++ fosse "sicuramente più veloce" del C :D
Forse con i compilatori Intel? :sofico:
Oceans11
27-11-2013, 12:34
E non è nemmeno il più veloce. Il C++ è sicuramente più veloce
sono caduto dalla sedia :stordita:
Se penso alle eccezioni e a come vengono gestite, ai runtime bounds checkings, al polimorfismo ecc. mi riesce difficile crederlo.
Ad ogni modo concordo con chi diceva che il problema è np-completo.
Mi pare che per chi risolva il problema di p vs np ci sono in palio un milione di dollari. :cool:
ingframin
27-11-2013, 13:24
io rimango fedele al vhdl come linguaggio più veloce
che è pure più veloce del linguaggio macchina
:D :D :D :D :D :D :D :D :D
Peccato che non sia un linguaggio di programmazione ma di descrizione hardware.
Su molte piattaforme puoi fornire direttamente lo schema elettrico invece di scrivere codice VHDL.
Inoltre il VHDL non diventa un eseguibile ma puo' diventare o una bitmap di configurazione hardware per logiche programmabili (come FPGA o CPLD) o essere tradotto in un layout in caso tu lo stia usando per generare un ASIC.
Non e' qualcosa di "usabile a casa" come puo' essere C o Java...
vendettaaaaa
27-11-2013, 13:40
sono caduto dalla sedia :stordita:
Se penso alle eccezioni e a come vengono gestite, ai runtime bounds checkings, al polimorfismo ecc. mi riesce difficile crederlo.
Ovviamente, dato che queste cose il C non le implementa, credo proprio che cdm si riferisse a un confronto a parità di codice :fagiano:
Peccato che non sia un linguaggio di programmazione ma di descrizione hardware.
Su molte piattaforme puoi fornire direttamente lo schema elettrico invece di scrivere codice VHDL.
Inoltre il VHDL non diventa un eseguibile ma puo' diventare o una bitmap di configurazione hardware per logiche programmabili (come FPGA o CPLD) o essere tradotto in un layout in caso tu lo stia usando per generare un ASIC.
Non e' qualcosa di "usabile a casa" come puo' essere C o Java...
ovvio (non per niente c'erano una decina di faccine sotto) ma se il tuo codice è abbastanza semplice da poter essere tradotto in un circuito abbastanza semplice da poter essere implementato in un fpga ecco che ottieni una velocità di diversi ordini di grandezza superiore rispetto a qualsiasi programma implementato su una cpu
è il principio su cui si fondano le crio et similari di ni dove il codice "scritto" in g viene trasformato dal compilatore ed implementato tramite fpga
ed è stato anche l'approccio (ma basato su asic) con cui hano craccato il triplo DES dimostrando che ormai tale algoritmo di cifratura fosse superato
http://wiki.kairaven.de/_media/open/img/gpg/descracker.jpg
Oceans11
27-11-2013, 14:48
Ovviamente, dato che queste cose il C non le implementa, credo proprio che cdm si riferisse a un confronto a parità di codice :fagiano:
beh ma se al superset del c togli il superset che rimane?
troll: sono giunto ad un assurdo: il c è più veloce del c! :D
vendettaaaaa
27-11-2013, 17:15
beh ma se al superset del c togli il superset che rimane?
troll: sono giunto ad un assurdo: il c è più veloce del c! :D
:sofico:
A questo punto non rimane che attendere la spiegazione di cdm :read:
C++ risulta più veloce grazie ai template (tanti odiati da alcuni) al posto di usare puntatori ovunque (un pò tutti i linguaggi)
Basandosi su una semantica di valori, diventa più facile per il compilatore essere sicuro che non ci siano problemi di aliasing o effettuare inline. Inoltre diventa possibile per il programmatore gestire in maniera ottimale il layout dei propri dati
Tutto questo è aiutato da ottimizzazioni permesse da C++ (elisione delle copie (RVO, NRVO), move, constexpr, e chissà quanto altro)
Altra cosa non da poco, è la possibilità di cambiare il comportamento del proprio algoritmo specializzando a seconda dei dati da gestire
In poche parole la differenza esiste per codice scritto in maniera da essere riutilizzabile, ma non per C scritto da zero interamente pensato per le performance per un determinato problema
Oceans11
27-11-2013, 18:36
C++ risulta più veloce grazie ai template (tanti odiati da alcuni) al posto di usare puntatori ovunque (un pò tutti i linguaggi)
Basandosi su una semantica di valori, diventa più facile per il compilatore essere sicuro che non ci siano problemi di aliasing o effettuare inline. Inoltre diventa possibile per il programmatore gestire in maniera ottimale il layout dei propri dati
Tutto questo è aiutato da ottimizzazioni permesse da C++ (elisione delle copie (RVO, NRVO), move, constexpr, e chissà quanto altro)
Altra cosa non da poco, è la possibilità di cambiare il comportamento del proprio algoritmo specializzando a seconda dei dati da gestire
In poche parole la differenza esiste per codice scritto in maniera da essere riutilizzabile, ma non per C scritto da zero interamente pensato per le performance per un determinato problema
premetto che non conosco i costrutti e le altre cose che hai nominato, però mi sorge la domanda: "quand'è che si scrive codice in c non intermente pensato per un determinato problema?"
cdimauro
27-11-2013, 21:40
Cosa intendi con "massicciamente paralleli"?
Quando c'è da macinare parecchi dati, come avviene in sistemi HPC ad esempio.
E parli sempre di prestazioni sulla CPU?
Potremmo parlare più in generale di elemento computazionale, visto che pure le GPU si prestano ad essere usate allo scopo. E ci sarebbero anche i cosiddetti "coprocessori".
Puoi argomentare e fornire un esempio please? Sono genuinamente interessato :) (soprattutto sulla prima parte della affermazione).
Riguardo alla prima parte mi ha già anticipato nico159. L'esempio classico è quello del sort, che mostra come il compilatore C++ riesce a tirare fuori codice molto più ottimizzato, grazie alla conoscenza dei tipi coinvolti e all'opportuna applicazione dell'inlining del codice
Sulla seconda parte ho risposto sopra. Ci sono diversi benchmark su algoritmi come la risoluzione di sistemi di equazioni differenziali, ad esempio, in cui il Fortran mostra i muscoli rispetto a qualunque altro linguaggio. Ed è il motivo per cui, ancora oggi, rimane il linguaggio più usato in quest'ambito, nonostante la veneranda età.
Idem, non pensavo che il C++ fosse "sicuramente più veloce" del C :D
Forse con i compilatori Intel? :sofico:
Beh, sono molto buoni, ma senza sfruttare alcune caratteristiche del C++ non è che possano fare miracoli.
sono caduto dalla sedia :stordita:
Se penso alle eccezioni e a come vengono gestite, ai runtime bounds checkings, al polimorfismo ecc. mi riesce difficile crederlo.
Non è che del C++ devi usare tutto soltanto perché ti mette a disposizione tanti strumenti. Strong typing, template, inlining, memory handler li puoi utilizzare per ottimizzare al meglio il codice spesso con notevoli vantaggi rispetto agli altri linguaggi, come il C, che non consentono la stessa flessibilità.
Alla fine è il programmatore che deve usare sapientemente ciò che gli serve per ottenere il "miglior" compromesso possibile in base ai requisiti. Ed è chiaro che se uno dei requisiti è quello di ottenere il codice più veloce, userà certi strumenti piuttosto che altri.
Ad ogni modo concordo con chi diceva che il problema è np-completo.
Mi pare che per chi risolva il problema di p vs np ci sono in palio un milione di dollari. :cool:
Con tutta questa crisi non c'è nessuno che vuol diventare ricco. Mah. :D
Ovviamente, dato che queste cose il C non le implementa, credo proprio che cdm si riferisse a un confronto a parità di codice :fagiano:
No, il confronto si fa su base puramente prestazionale, se questo è l'obiettivo fissato. In tal caso si userà del C++ soltanto ciò che non compromette le prestazioni. E non importa se il codice sarà anche più lungo.
C++ risulta più veloce grazie ai template (tanti odiati da alcuni) al posto di usare puntatori ovunque (un pò tutti i linguaggi)
Basandosi su una semantica di valori, diventa più facile per il compilatore essere sicuro che non ci siano problemi di aliasing o effettuare inline. Inoltre diventa possibile per il programmatore gestire in maniera ottimale il layout dei propri dati
Tutto questo è aiutato da ottimizzazioni permesse da C++ (elisione delle copie (RVO, NRVO), move, constexpr, e chissà quanto altro)
Altra cosa non da poco, è la possibilità di cambiare il comportamento del proprio algoritmo specializzando a seconda dei dati da gestire
In poche parole la differenza esiste per codice scritto in maniera da essere riutilizzabile, ma non per C scritto da zero interamente pensato per le performance per un determinato problema
Concordo, a parte l'ultima parte: non è mi chiaro ciò che volevi dire.
AnonimoVeneziano
28-11-2013, 10:40
L'esempio classico è quello del sort, che mostra come il compilatore C++ riesce a tirare fuori codice molto più ottimizzato, grazie alla conoscenza dei tipi coinvolti e all'opportuna applicazione dell'inlining del codice
Ma intendi usando la qsort della standard library? Per quello si trovano implementazioni molto più veloci (chiamate qsort-inline) che sono molto più veloci della implementazione della standard library usando le MACRO per fare in inline della funzione di comparazione (quella della stdlib di default è abbastanza lenta visto che per fare una comparazione deve chiamare un puntatore a funzione). Lo scenario in questione non mi dice molto sulla qualità del linguaggio e non mi aiuta a reggere un discorso serio sulla questione.
Quello che cerco è uno scenario reale in cui l'utilizzo del C++ (codando in stile C++) nella soluzione di un problema risulta essere più veloce dell'equivalente in C (codando in stile C e non simulando lo stile C++ con strani stratagemmi in C).
Grazie.
cdimauro
28-11-2013, 22:28
Ma intendi usando la qsort della standard library?
Sì.
Per quello si trovano implementazioni molto più veloci (chiamate qsort-inline) che sono molto più veloci della implementazione della standard library usando le MACRO per fare in inline della funzione di comparazione (quella della stdlib di default è abbastanza lenta visto che per fare una comparazione deve chiamare un puntatore a funzione). Lo scenario in questione non mi dice molto sulla qualità del linguaggio e non mi aiuta a reggere un discorso serio sulla questione.
Aspetta un attimo. Come fa l'implementazione più veloce dellq qsort in C a scegliere se eseguire l'inline o usare il puntatore a funzione? Ha una catena di if/else per controllare i vari tipi, e usare l'uno o l'altro? Perché se è così diventa ingestibile.
In C++ è il compilatore che sceglie cosa fare automaticamente, senza intervento alcuno del programmatore. Mi sembra che la differenza sia notevole, no?
Quello che cerco è uno scenario reale in cui l'utilizzo del C++ (codando in stile C++) nella soluzione di un problema risulta essere più veloce dell'equivalente in C (codando in stile C e non simulando lo stile C++ con strani stratagemmi in C).
Grazie.
Ecco qui (http://unthought.net/c++/c_vs_c++.html) un bell'articolo sulla questione, che lessi parecchio tempo fa.
Ma è utile anche il classico Computer Language Shootout (http://benchmarksgame.alioth.debian.org/u64/benchmark.php?test=all&lang=gpp&lang2=gcc&data=u64), che consente di analizzare le diverse implementazioni, avendo anche sottomano i tempi d'esecuzione.
AnonimoVeneziano
29-11-2013, 01:42
Sì.
Aspetta un attimo. Come fa l'implementazione più veloce dellq qsort in C a scegliere se eseguire l'inline o usare il puntatore a funzione? Ha una catena di if/else per controllare i vari tipi, e usare l'uno o l'altro? Perché se è così diventa ingestibile.
In C++ è il compilatore che sceglie cosa fare automaticamente, senza intervento alcuno del programmatore. Mi sembra che la differenza sia notevole, no?
Una roba tipo
inline int cmpFun(...) {
... comparing stuff ...
return result;
}
#define QSORT(array, size, cmp) {
.... do stuff
cmp(array[i], array[j]);
.... do stuff
}
int main() {
... do stuff
QSORT(array_of_stuff, size, cmpFun)
... do stuff
}
anche qua il compilatore decide di inlineare la funzione di comparazione o no a seconda della situazione. (C99 ovviamente)
AnonimoVeneziano
29-11-2013, 01:53
Ecco qui (http://unthought.net/c++/c_vs_c++.html) un bell'articolo sulla questione, che lessi parecchio tempo fa.
Ma è utile anche il classico Computer Language Shootout (http://benchmarksgame.alioth.debian.org/u64/benchmark.php?test=all&lang=gpp&lang2=gcc&data=u64), che consente di analizzare le diverse implementazioni, avendo anche sottomano i tempi d'esecuzione.
Il primo articolo che hai postato indica che la soluzione C++ è più lenta di quella C a meno di scrivere il C++ praticamente come il C e la soluzione C++ è anche più lunga (e a quel punto le prestazioni sono identiche a differenza di una manciata di millisecondi).
Poi alla fine fornisce una soluzione in C++ molto più veloce , ma specifica chiaramente che usa un algoritmo diverso e che quindi non è comparabile con le soluzioni precedenti.
Il shootout da risultati abbastanza discordanti (nella maggior parte dei casi vince comunque il C) e la maggior parte dei programmi hanno implementazioni difficilmente comparabili tra loro. Non è facile stabilire se un programma è più lento perchè ha una implementazione scadente in quel linguaggio o perchè è il linguaggio in se che è più lento.
C++ risulta più veloce grazie ai template (tanti odiati da alcuni) al posto di usare puntatori ovunque (un pò tutti i linguaggi)
Basandosi su una semantica di valori, diventa più facile per il compilatore essere sicuro che non ci siano problemi di aliasing o effettuare inline. Inoltre diventa possibile per il programmatore gestire in maniera ottimale il layout dei propri dati
Tutto questo è aiutato da ottimizzazioni permesse da C++ (elisione delle copie (RVO, NRVO), move, constexpr, e chissà quanto altro)
Altra cosa non da poco, è la possibilità di cambiare il comportamento del proprio algoritmo specializzando a seconda dei dati da gestire
In poche parole la differenza esiste per codice scritto in maniera da essere riutilizzabile, ma non per C scritto da zero interamente pensato per le performance per un determinato problema
Credo tu ti riferissi a me :asd:
Il problema è l'abuso, quando il codice diviene completamente illeggibile e si defiscono type_traits per qualsiasi cosa e diventa difficile risalire di che tipo è un certo dato (c'è lo stesso problema con i typedef C ovviamente, e anche la nuova keyword auto di C++11, meglio non abusarne troppo).
Però è vero che si possono fare tante cose carine a tempo di compilazione (con il problema non sempre trascurabile che allunghi ENORMEMENTE i tempi di compilazione).
Edit: visto dopo che era gia' stato risposto ...
cdimauro
30-11-2013, 15:34
Una roba tipo
inline int cmpFun(...) {
... comparing stuff ...
return result;
}
#define QSORT(array, size, cmp) {
.... do stuff
cmp(array[i], array[j]);
.... do stuff
}
int main() {
... do stuff
QSORT(array_of_stuff, size, cmpFun)
... do stuff
}
anche qua il compilatore decide di inlineare la funzione di comparazione o no a seconda della situazione. (C99 ovviamente)
OK, a parte la bruttura della macro, diventa concettualmente simile all'approccio del C++.
A tal proposito c'è un post (http://www.agottem.com/blog/inlining_qsort_sort) avverso al C++, che espone sostanzialmente le stesse critiche, fornendo qualche numero.
C'è, però, da dire che la soluzione basata su C++ rimane comunque più veloce rispetto a quella scritta (e ottimizzata appositamente) in C.
Il primo articolo che hai postato indica che la soluzione C++ è più lenta di quella C a meno di scrivere il C++ praticamente come il C e la soluzione C++ è anche più lunga (e a quel punto le prestazioni sono identiche a differenza di una manciata di millisecondi).
Non mi pare sia così: ci sono 1,2 secondi di differenza, che non è poco su risultati dell'ordine dei 35 secondi. C++ rimane, in ogni caso, in vantaggio rispetto al C, confermando la tesi di cui sopra...
Sempre riguardo all'ordinamento, c'è un altro post (http://theory.stanford.edu/~amitp/rants/c++-vs-c/) che mostra come C++ rimanga sempre in vantaggio rispetto al C, e con risultati tutt'altro che trascurabili a favore del primo.
Poi alla fine fornisce una soluzione in C++ molto più veloce , ma specifica chiaramente che usa un algoritmo diverso e che quindi non è comparabile con le soluzioni precedenti.
Senz'altro, e infatti non la considero nemmeno: si confrontano mele con pere. Ma l'autore non ha voluto barare: lo dice esplicitamente.
Il shootout da risultati abbastanza discordanti (nella maggior parte dei casi vince comunque il C) e la maggior parte dei programmi hanno implementazioni difficilmente comparabili tra loro. Non è facile stabilire se un programma è più lento perchè ha una implementazione scadente in quel linguaggio o perchè è il linguaggio in se che è più lento.
L'obiettivo dovrebbe essere quello di realizzare la versione più veloce, per cui ogni linguaggio può usare la soluzione più opportuna.
Non importa che l'implementazione sia comparabile o meno; al più è possibile stigmatizzare l'incapacità dello sviluppatore che per un certo linguaggio ha fornito una soluzione non al top.
A tal proposito vale quanto avevo già detto prima: del C++ si dovrebbero utilizzare gli strumenti adeguati alla risoluzione del problema. Questo significa che se l'obiettivo è quello delle prestazioni migliori, chi ha realizzato il codice C++ fornendo una versione più lenta rispetto al C, ha completamente sbagliato. Se in C++ non è possibile fare meglio del C usando i suoi strumenti peculiari, allora si può benissimo usare la soluzione C e ottenere almeno le stesse prestazioni di quest'ultimo. ;)
Una roba tipo
<cut>
anche qua il compilatore decide di inlineare la funzione di comparazione o no a seconda della situazione. (C99 ovviamente)
In linea di massima quello che fai coi template riesci ad ottenerlo con le macro.
Ma quando cominci ad andare su cose piu' complesse e' facile che le macro da scrivere diventino parecchio complicate.
Alcune cose che mi vengono in mente:
* Strutture dati ad uso interno specializzate sui tipi degli argomenti (e.g. una struttura che contenga anche chiave e valore per i nodi di un albero)
* Specializzazioni da parte dell'utente (i.e. scelte da fare in base a tipi non noti quando scrivo
* Scelte effettuate in base a calcoli fatti a tempo di compilazione
Le performance sono una funzione non solo delle potenzialita' del linguaggi, ma quanto mi ci vuole ad usarle/mantenerle.
ingframin
01-12-2013, 08:56
Mentre qui si gioca a chi ce l'ha più lungo, Soniaaaa si è persa per strada... :rolleyes:
Mentre qui si gioca a chi ce l'ha più lungo, Soniaaaa si è persa per strada... :rolleyes:
Ci si puo' attendere un risultato diverso con un titolo come questo ? Nel momento in cui uno dice "Linguaggio X e' piu' veloce" e' naturale che la discussione finisca sul perche' lo e' (o non lo e').
Diverso sarebbe stato se la richiesta fosse stata "Con quale linguaggio posso far andare piu' veloce QUESTO codice" (con codice allegato).
Domanda2:
Inoltre posso chedervi se qualcuno sa' la formula per sapere da quanti bit e' composto un mumero ?
es: premdiamo il numero 8 che in unsigned binario e' 1000 e quindi composto da 4 bit, esiste una formula veloce(la velocita' e' essenziale!) per sapere quanti bit occupa ??? (cioe' da 8 o 1000 ottenere 4 o 100)
Grazie in anticipo, Soniaa
http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious
Qua trovi un po' di soluzioni, anche se sono C
Ho scritto il mio codice utilizzando varie tecniche
Questa e' la piu 'BARBARARICA' ma rimane tutt'ora la piu veloce
ne ho provate di altre (calcoli del quadro in unica variabile a metodo binario, e tecnica a numero pedina(la pedina mangiata veniva sostituita dall'ultima pedina in modo da sapere sempre senza tanti if quale era la prossima pedina da spostare...ma bisognava tenere un secondo conteggio e conseguente aggiornamento in quanto ogni pedina era numerata e non quadro, ma sono risultate piu lente)
REM _______________ PEG 1 verso1, verso2 _______________
mossa1quadro1verso1:
IF quadro1 = 0 THEN GOTO mossa1quadro2verso2
IF quadro2 = 0 THEN GOTO mossa1quadro1verso2
IF quadro3 = 1 THEN GOTO mossa1quadro1verso2
quadro1 = 0: quadro2 = 0: quadro3 = 1: soluzionemossa1=1.1
GOSUB mossa2quadro1verso1
REM rollback
quadro1 = 1: quadro2 = 1: quadro3 = 0
m1p1v2:
IF quadro4 = 0 THEN GOTO mossa1quadro2verso2
IF quadro9 = 1 THEN GOTO mossa1quadro2verso2
quadro1 = 0: quadro4 = 0: quadro9 = 1: soluzionemossa1=1.2
GOSUB mossa2quadro1verso1
REM rollback
quadro1 = 1: quadro4 = 1: quadro9 = 0
REM _______________ PEG 2 verso2 _______________
mossa1quadro2verso2:
IF quadro2 = 0 THEN GOTO mossa1quadro3verso2
IF quadro5 = 0 THEN GOTO mossa1quadro3verso2
IF quadro10 = 1 THEN GOTO mossa1quadro3verso2
IF velociferox < 3 THEN
velociferox = velociferox + 1
quadro2 = 0: quadro5 = 0: quadro10 = 1: soluzionemossa1=2.2
GOSUB mossa2quadro1verso1
REM rollback
quadro2 = 1: quadro5 = 1: quadro10 = 0
velociferox = velociferox - 1
END IF
REM _______________ PEG 3 verso2, verso3 _______________
etc, etc,etc 33 quadri(76 possibili mosse) moltiplicate per 31 mosse
(ovviamente una volta scritte le prime, poi con word-trova e sostituisci ho scritto tutte le 2356 mosse in un lampooo)
Tecnica quadro in una unica variabile intesa binaria
(i punti di forza di questa tecnica e che non vi e' bisogno di rollback e il logaritmo mi consente di sapere senza if quale e' la prossima pedina presente sul tavoliere)
MA e' piu leentaa!! del 50 per cento
REM movem1:
qtm1 = qm1
DO
bitqm1 = INT(LOG(qtm1) / lg2#) + 1
ON bitqm1 GOTO m1q33v3, m1q32v4, m1q31v1, m1q30v3, m1q29v4, m1q28v1, m1q27v3, m1q26v3, m1q25v1, m1q24v1, m1q23v1, m1q22v1, m1q21v1, m1q20v3, m1q19v3, m1q18v1, m1q17v1, m1q16v1, m1q15v1, m1q14v1, m1q13v2, m1q12v2, m1q11v1, m1q10v1, m1q9v1, m1q8v1, m1q7v1, m1q6v2, m1q5v2, m1q4v1, m1q3v2, m1q2v2, m1q1v1
retm1:
LOOP UNTIL qtm1 = 0
PRINT "Programma terminato con successo": END
REM _______________ PEG 1 v1 v2 _______________
m1q1v1:
REM print "m1q1v1"
qtm1 = qtm1 - sottrattore33 - 1
qmttm1 = qm1 MOD 1073741824
IF qm1 - qmttm1 = 6442450944 THEN
qm2 = qm1 - 5368709120: REM + 1073741824 - 6442450944
rm1 = 11
GOSUB movem2
END IF
REM m1q1v2:
REM print "m1q1v2"
IF qmttm1 > 536870911 THEN
IF qm1 MOD 33554432 < 16777216 THEN
qm2 = qm1 - 4815060992: REM + 16777216 - 4831838208
rm1 = 12
GOSUB movem2
END IF
END IF
GOTO retm1
REM _______________ PEG 2 v2 _______________
m1q2v2:
REM print "m1q2v2"
qtm1 = qtm1 - sottrattore32
IF qm1 MOD 536870912 > 268435455 THEN
IF qm1 MOD 16777216 < 8388608 THEN
IF x < 3 THEN
x = x + 1
qm2 = qm1 - 2407530496: REM + 8388608 - 2415919104
rm1 = 22
GOSUB movem2
x = x - 1
END IF
END IF
END IF
GOTO retm1
REM _______________ PEG 3 v2 v3 _______________
vorrei provare col fortran , ma delle decine che ho trovato e provato solo silverfrost e Simply Fortran 2 (entrambe a pagamento) sono per me comprensibili!!!! ...scrivo il codice e poi build e il gioco e' fatto!
le altre sono tutte arabo puro! il play o il build neanche l'editor....trovo...
col silverfrost l'esempio che ho scritto ci metteva 1 minuto
e con simply fortran 10 secondi
...come mai a parita' di codice vendettaaaaa ci metteva 2 secondi col gfortran 4.8.1 ??????
come posso reperirlo in una forma di utilizzo per me comprensibile ????
Quidi la domanda:
in quale linguaggio devo trasformare questo semplice codice per ottenere velocita' molto piu alte?
forse solo il linguaggio macchina? (se cosi' fosse allora devo rinunciare, troppoooo off-limit per me!!..giusto qualcosina con lo ZXspectrum...ma qualcosinaaaaa----)..e poi fare l'output-append ad ogni soluzione trovata su file....nooohh, e' assolutamente troppo per me!
PS il linguaggio macchina e' l'assembler, giusto?
col QB64 sono arrivata ad un tempo di 500 anni, (ne ho trovate solo 10 milioni in qualche giorno)
se riesco ad arrivare ad un tempo di elaborazione di 2 anni, poi utilizzando piu pc multiprocessore dovrei facilmente riuscire a frazionare fino ad un mesetto circa per trovare tutte le soluzioni (qualcheeee miliardo....:D )
PS leggendo in rete nessuno ci e' mai riuscito a trovarle tutte!!!
ma gli ultimi che ci hanno provato avevano sottomano pc del medio-evo...(M20 usando cobol e pascal)
vendettaaaaa
01-12-2013, 18:35
Ciao, ti rispondo brevemente perché sono in giro con lo smartphone: scarica Code::Blocks (versione con MinGW incluso). MinGW (minimal gnu for Windows) include gcc, g++ e gfortran. Usare l'IDE è abbastanza immediato, come vuoi te.
Cmq se il tempo di calcolo è solo 500 anni col tuo PC puoi vendere un rene e affittare un cluster da qualche parte per un annetto, dovrebbe bastare :D
Non ho letto tutti i post e non ho visto l'algoritmo in questione, ma parlando come studente laureando di scienze e tecnologie informatiche, posso dirti che se l'algoritmo è abbastanza semplice e/o corto di scriverlo direttamente in assembly utilizzando gli instruction sets forniti dai processori moderni (MMX, SSE, FPU etc) e di lavorare direttamente sui registri del processore.
Ovviamente l'80% delle prestazioni dipende dall'algoritmo stesso, quindi prima sarebbe il caso di ridurre il più possibile il costo computazionale dell'algoritmo (tenendo presente che anche gli accessi a memoria centrale e di massa sono un rallentamento per il processore), poi se possibile parallelizzare.
Non esiste miglior compilatore della mente umana, anche perché essi stessi sono stati creati da umani e per essere general purpose (alcuni di più altri meno).
In ogni caso, per guadagnare qualche ns in più a ciclo controlla di aver tolto i controlli a runtime, sostituisci le divisioni con moltiplicazioni quando possibile, utilizza le versioni iterative degli algoritmi ricorsivi (l'accesso allo stack pesa), usare i tipi più adatti per i dati, ed altri accorgimenti che ogni programmatore dovrebbe sapere.
Inoltre ho notato quelli che mi sembrano dei modulo, può essere utile dare una ripassata agli algoritmi di aritmetica modulare (http://en.wikibooks.org/wiki/Discrete_mathematics/Modular_arithmetic)
Ciao
Ho scritto il mio codice utilizzando varie tecniche
Questa e' la piu 'BARBARARICA' ma rimane tutt'ora la piu veloce.
E' comprensibile che la versione con tutto per esteso sia piu' veloce rispetto ad utilizzare gli array (come mi sembrava avessi detto di aver fatto) ma in un linguaggio moderno la differenza non dovrebbe farsi sentire piu' di tanto.
Consiglio il passaggio piu' moderno comunque non tanto per le performance, ma per migliorare l'algoritmo: invece che limare i tempi potresti riuscire a ridurre la complessita di uno o piu' ordini di grandezza.
La prima cosa che mi viene in mente e' che il problema presenta un notevole grado di simmetria: ad esempio inutile che provi tutte e quattro le possibili mosse iniziali: fatta la prima, i risultati per le altre le ottieni semplicemente ruotando la plancia di 90/180/270 gradi.
Gia' questo porterebbe i tempi del tuo programma da 500 a 125 anni.
Un programma che tenesse traccia di quali configurazioni ha gia' studiato e salti quelle che sono semplicemente speculari e/o rotate, potrebbe essere molto piu' veloce, ma come dicevo sopra per questo ti ci vorrebbe un linguaggio che fornisca sturmenti un po' piu' potenti di quelli che hai a disposizione ora, non necessariamente piu' veloce.
si, si per il conteggio degli anni (2000) avevo gia' calcolato che la prima mossa (quadro 5 in quadro 17)per speculiarita' mi portasse ad un conteggio di 2000 /4 = 500.
Per il resto sto studiando un po altre tecniche di speculiarita', e di scarto mose che non portano sicuramente ad una soluzione (come avrai notato in quadro 5,15,17,19,29 deve SEMPRE rimanere una pedina (si nota infatti ad esempio che alla mossa quadro2verso2 c'e quella variabile "x" che tiene un conteggio da 1 a 4 impedisce appunto di effettuare tale mossa se ne sono state fatte altre tre di quel tipo, questo porta via pochissimo dispendio di tempo.
Per Verso intendo verso1=dx, v2=giu, v3=sx, v4=su
Ma con un codice cosi semplice " if ,goto ,gosub, int o ceil" quale e' un linguaggio veloooceee?
NB: lo sapete quanto tempo impiega il basic per trasformare un nuero con decimali in INT o CEIL o FIX ???.....troppooo!!! ovvero come 20 IF o 10 MOD
Su i7 3770K @default:
con MinGW 4.8.1 in DEBUG (perchè in release MinGW salta il ciclo e calcola direttamente b con a = 1000000000, mettendoci 0 secondi):
https://public.bn1.livefilestore.com/y2pyFp8NqIy768DA_HVb7BoWE7OdSWY9NwIrga_ooZ_MQ7yZJXl1N2cnerrjaPo94R-4DaVbRlPovuGOhLX-fm-SyAKSvZ1trQjuKlSc-XNrko/SpeedTestCPP.JPG?psid=1
con gfortran 4.8.1 in DEBUG:
https://public.bn1.livefilestore.com/y2pnLP-U8tmMj2AbuqtqPATshd8Ue0vQz93icLtOU2J60hD6b8tJuJxabblXmG3aFngd37m_cOQHZtZ8pv39bB_d4HazdUfmzSrC30dpId24xo/SpeedTestF77.JPG?psid=1
Con gfortran in release ci mette 1.9 secondi circa, quindi siamo lì, il limite inferiore è sui 2 secondi con questa potenza di calcolo.
Temo ci sia un errore anche nel tuo codice; nel tuo esempio tu ci metti solo 2 secondi in release in quanto utilizzi solo b "write(*,*)b", ma fai "write (*,*)a,b,c,d" ottieni il vero tempo!!!
dico bene???
epimerasi
02-12-2013, 17:40
E' comprensibile che la versione con tutto per esteso sia piu' veloce rispetto ad utilizzare gli array (come mi sembrava avessi detto di aver fatto) ma in un linguaggio moderno la differenza non dovrebbe farsi sentire piu' di tanto.
Consiglio il passaggio piu' moderno comunque non tanto per le performance, ma per migliorare l'algoritmo: invece che limare i tempi potresti riuscire a ridurre la complessita di uno o piu' ordini di grandezza.
La prima cosa che mi viene in mente e' che il problema presenta un notevole grado di simmetria: ad esempio inutile che provi tutte e quattro le possibili mosse iniziali: fatta la prima, i risultati per le altre le ottieni semplicemente ruotando la plancia di 90/180/270 gradi.
Gia' questo porterebbe i tempi del tuo programma da 500 a 125 anni.
Un programma che tenesse traccia di quali configurazioni ha gia' studiato e salti quelle che sono semplicemente speculari e/o rotate, potrebbe essere molto piu' veloce, ma come dicevo sopra per questo ti ci vorrebbe un linguaggio che fornisca sturmenti un po' piu' potenti di quelli che hai a disposizione ora, non necessariamente piu' veloce.
Se riesce a farlo vince 1 milione di dollari, la medaglia Fields e inviti a convegni di matematica per il resto della sua vita
vendettaaaaa
02-12-2013, 17:56
Temo ci sia un errore anche nel tuo codice; nel tuo esempio tu ci metti solo 2 secondi in release in quanto utilizzi solo b "write(*,*)b", ma fai "write (*,*)a,b,c,d" ottieni il vero tempo!!!
dico bene???
Ebbene sì, le ottimizzazioni colpiscono di nuovo, anche in Fortran (potevo immaginarlo, visto che le fanno il backend di GCC anzichè il frontend per il particolare linguaggio)! In debug il tempo rimane sui 6.5 secondi, in release così facendo sale a 4.7 secondi (da 1.9 circa) :D
Se riesce a farlo vince 1 milione di dollari, la medaglia Fields e inviti a convegni di matematica per il resto della sua vita
Anche no. ho detto ridurne la complessita', non renderlo polinomiale :D
Ammetto cmq che la mia affermazione era abbastanza ambigua e non precisa
Se riesce a farlo vince 1 milione di dollari, la medaglia Fields e inviti a convegni di matematica per il resto della sua vita
secondo me col linguaggio macchina e computers moderni e' possibile, lo affermo con una probabilita' del 70 per cento.
Secondo me il fatto che sembrerebbe che nessuno ci sia mai riuscito, come ho detto, e' che gli ultimi che ci hanno provato avevano sottomano pc del medio-evo...
Nessun milione di dollari, il codice e' di complessita' elementere, anzi da asilo nido per chi conosce l'assembler pero!!!
Tuttavia e' possibile che ci vogliano una trentina di thread e un paio di mesi...ma questo non sarebbe assolutamente un problema in quanto la metodologia di risoluzione del logaritmo in questione e' mooooolto compatibile con l'eventuale frazionamento su piu PC, quindi 30 thread(7 PC multicore che volendo li ho gia') * 2 mesi = [60 mesi (5 anni) per un thread solo],
Quindi devo arrivare ad un tempo di circa 5 anni!!!
...oppure visto che dal mio sito si puo' scaricare il codecMod pack piu potente del mondo (codecmod k-lite addOn "per chi non lo sapesse"), potrei inserire all'interno una macro per fare risolvere il mio problema agli altri....e cosi' i pc di tutto il mondo mi ivierebbero i risultati a me... (sto scherzando ovviamente...)
vendettaaaaa
03-12-2013, 13:28
secondo me col linguaggio macchina e computers moderni e' possibile, lo affermo con una probabilita' del 70 per cento.
Secondo me il fatto che sembrerebbe che nessuno ci sia mai riuscito, come ho detto, e' che gli ultimi che ci hanno provato avevano sottomano pc del medio-evo...
Nessun milione di dollari, il codice e' di complessita' elementere, anzi da asilo nido per chi conosce l'assembler pero!!!
Tuttavia e' possibile che ci vogliano una trentina di thread e un paio di mesi...ma questo non sarebbe assolutamente un problema in quanto la logica di risoluzione del logaritmo in questione e' mooooolto compatibile con l'eventuale frazionamento su piu PC, quindi 30 thread(7 PC multicore che volendo li ho gia') * 2 mesi = [60 mesi (5 anni) per un thread solo],
Quindi devo arrivare ad un tempo di circa 5 anni!!!
Complessità non vuol dire difficoltà come da dizionario ma indica una caratteristica dell'algoritmo, cioè quanto aumentano i conti all'aumentare della dimensione del problema (linearmente, polinomialmente, esponenzialmente). Ad esempio la ricerca di un valore ha complessità lineare (N), alcuni algoritmi di sorting hanno complessità logaritmica (log(N)), eccetera. Magari ho detto qualche imprecisione, il corso di algoritmi è cominciato solo ieri :D
epimerasi
03-12-2013, 13:29
Anche no. ho detto ridurne la complessita', non renderlo polinomiale :D
Ammetto cmq che la mia affermazione era abbastanza ambigua e non precisa
Immagino che stia gia` utilizzando un algoritmo non cosi` naif, ma che sia cmq superpolinomiale.
Se e` superpolinomiale cambia poco (infatti ha paralto di 200 anni di calcolo).
epimerasi
03-12-2013, 13:32
secondo me col linguaggio macchina e computers moderni e' possibile, lo affermo con una probabilita' del 70 per cento.
Secondo me il fatto che sembrerebbe che nessuno ci sia mai riuscito, come ho detto, e' che gli ultimi che ci hanno provato avevano sottomano pc del medio-evo...
Nessun milione di dollari, il codice e' di complessita' elementere, anzi da asilo nido per chi conosce l'assembler pero!!!
Tuttavia e' possibile che ci vogliano una trentina di thread e un paio di mesi...ma questo non sarebbe assolutamente un problema in quanto la logica di risoluzione del logaritmo in questione e' mooooolto compatibile con l'eventuale frazionamento su piu PC, quindi 30 thread(7 PC multicore che volendo li ho gia') * 2 mesi = [60 mesi (5 anni) per un thread solo],
Quindi devo arrivare ad un tempo di circa 5 anni!!!
...oppure visto che dal mio sito si possono scaricare i codec mod piu potenti del mondo (codecmod k-lite addOn "per chi non lo sapesse"), potrei inserire all'interno una macro per fare risolvere il mio problema agli altri....e cosi' i pc di tutto il mondo mi ivierebbero i risultati a me... (sto scherzando ovviamente...)
E` ovvio che dipende dall'istanza del problema, se ho un problema del commesso viaggiatore con 5/6 citta` posso pure risolverlo in maniera naif.
Non mi pare proprio il tuo caso.
In generale, mi sembra di capire che non ti e` chiara la teoria che c'e` dietro la questione. Dovresti leggere i link che ho postato all'inizio del topic per schiarirti le idee.
epimerasi
03-12-2013, 13:34
Se qualcuno scrive l'algoritmo in pseudocodice ci vuole poco a fare un'analisi della complessita` e calcolare quanto tempo ci vuole.
E` ovvio che dipende dall'istanza del problema, se ho un problema del commesso viaggiatore con 5/6 citta` posso pure risolverlo in maniera naif.
Non mi pare proprio il tuo caso.
In generale, mi sembra di capire che non ti e` chiara la teoria che c'e` dietro la questione. Dovresti leggere i link che ho postato all'inizio del topic per schiarirti le idee.
Ci ho dato un'occhiata (un'occhiata non perche non sia interessante, ma perche ci ho capito pocooo e il mio inglese non mi consente di buttarmici a capofitto...)
Comunque qui si sta parlando di attaccare il logaritmo con sistema "brute force",credo nulla a che vedere con le strategie (ampiamente descritte in molti libri da varie eccellenti menti degli anni '80 del pianeta proprio per il peg soliatire) tanto e' vero che nei vari libri il matematico che riusci a scrivere il programma per trovare la soluzione piu veloce (con metodo a strategia) ci metteva un'ora (lui si che vinse dei premi matematici davvero importanti proprio per quel lavoro), io col mio programma basic la prima soluzione la trovo in meno di 1 secondo....e piu di 1 milione in un ora...
Tutti quei libri sono incentrati all'interessantissima logica di logaritmi che si possono adottare per calcolare una strategia e nulla hanno a che vedere col mio tentativo di "brute force"
Se qualcuno scrive l'algoritmo in pseudocodice ci vuole poco a fare un'analisi della complessita` e calcolare quanto tempo ci vuole.
Forse si?...
ma forse anche no, in quanto per stabilire il tempo secondo me ti tocca petr forza scriverlo tutto e lanciarlo almeno qualche minuto, altrimenti il tempo stimato per la fine del programma risulterebbe approssimativo del 500 per cento o forse piu (secondo me...)
Immagino che stia gia` utilizzando un algoritmo non cosi` naif, ma che sia cmq superpolinomiale.
Se e` superpolinomiale cambia poco (infatti ha paralto di 200 anni di calcolo).
Puo' sembrare controintuitivo, ma un algoritmo puo' essere esponenzialmente piu' veloce di un altro anche se entrambi sono superpolinomiali.
Aggiungiamo inoltre che in molti contesti (e il nostro e' uno di questi) non ce ne frega nulla della complessita' asintotica perche' tanto lavoriamo sempre con dimensioni fisse. In particolare, la dimensione della scacchiera del nostro giorno e' fissa e non ci importa di risolvere efficientemente il caso generico.
In quest'ottica quindi un algoritmo esponenziale non e' un problema se il guadagno che mi da rispetto ad un altro mi porta il tempo di esecuzione per un problema di una certa dimensione sotto una soglia di accettablita'
Faccio un esempio. Per semplificare fa conto che l'algoritmo di ricerca valuti esattamente 4 mosse per ogni configurazione e che tutte le partite durino 25 mosse (ovviamente nel nostro caso la situazione e' piu' complessa in quanto sia la durata che le mosse ad ogni passo della ricerca posso essere maggiori o inferiori).
Questo vuol dire che durante la ricerca elaborero' 4^20 configurazioni e ci mettero' 500 anni.
Supponiamo che mi accorga di una condizione di simmetria, per cui ad ogni passo posso eliminare una mossa sapendo che non mi serve. Il numero di posizioni da valutare passa a 3^20. Sempre esponenziale sul numero di mosse (e quindi dimensione della plancia, nel nostro caso), ma la differenza nel risultato e' notevole
500 anni nel primo caso diventano nel secondo 500 / 4^20 * 3^20 = ~ 1.5 anni.
A questo punto diventa gia' piu' ragionevole pensare di ottimizzare il codice, cambiare il linguaggio, parallelizzarlo etc.
secondo me col linguaggio macchina e computers moderni e' possibile, lo affermo con una probabilita' del 70 per cento.
Secondo me il fatto che sembrerebbe che nessuno ci sia mai riuscito, come ho detto, e' che gli ultimi che ci hanno provato avevano sottomano pc del medio-evo...
Il problema sembra ben studiato in realta', se guardi sulla pagina inglese di wikipedia (https://en.wikipedia.org/wiki/Peg_solitaire), troverai un po' di riferimenti.
io col mio programma basic la prima soluzione la trovo in meno di 1 secondo....e piu di 1 milione in un ora...
Ma come soluzioni intendi quella che finisce con un'unica pedina in centro, o genericamente con un'unica pedina ? Nel primo caso dubito che ci siano milioni di soluzioni, anzi.
[/QUOTE]
epimerasi
06-12-2013, 18:14
Puo' sembrare controintuitivo, ma un algoritmo puo' essere esponenzialmente piu' veloce di un altro anche se entrambi sono superpolinomiali.
Aggiungiamo inoltre che in molti contesti (e il nostro e' uno di questi) non ce ne frega nulla della complessita' asintotica perche' tanto lavoriamo sempre con dimensioni fisse. In particolare, la dimensione della scacchiera del nostro giorno e' fissa e non ci importa di risolvere efficientemente il caso generico.
In quest'ottica quindi un algoritmo esponenziale non e' un problema se il guadagno che mi da rispetto ad un altro mi porta il tempo di esecuzione per un problema di una certa dimensione sotto una soglia di accettablita'...
Si`, e` quello che dicevo anche io qualche messaggio prima. Ma ha parlato di soluzioni che ci mettono 200 anni anche tenendo presente la simmetria, credo quindi stia cercando di trovare la soluzione ottima per un caso in cui la dimensionalita` lo frega comunque.
E` per questo cmq che chiedevo di mettere l'algoritmo in pseudocodice, almeno ci si puo` ragionare sopra.
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.