Linguaggio di programmazione, quale e' il piu veloce?

[soniaa]

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 ????

[soniaa]

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?

[soniaa]

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.... )

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]

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

[Robotex]

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/Discret...lar_arithmetic)
Ciao

[marco.r]

Originariamente inviato da soniaa

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.

[soniaa]

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

[soniaa]

Originariamente inviato da vendettaaaaa

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...CPP.JPG?psid=1

con gfortran 4.8.1 in DEBUG:
https://public.bn1.livefilestore.com...F77.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]

Originariamente inviato da marco.r

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]

Originariamente inviato da soniaa

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)

[marco.r]

Originariamente inviato da epimerasi

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
Ammetto cmq che la mia affermazione era abbastanza ambigua e non precisa

[soniaa]

Originariamente inviato da epimerasi

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]

Originariamente inviato da soniaa

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

[epimerasi]

Originariamente inviato da marco.r

Anche no. ho detto ridurne la complessita', non renderlo polinomiale
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]

Originariamente inviato da soniaa

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]

Se qualcuno scrive l'algoritmo in pseudocodice ci vuole poco a fare un'analisi della complessita` e calcolare quanto tempo ci vuole.

[soniaa]

Originariamente inviato da epimerasi

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"

[soniaa]

Originariamente inviato da epimerasi

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...)

[marco.r]

Originariamente inviato da epimerasi

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.

[marco.r]

Originariamente inviato da soniaa

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.