.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [Algoritmi] Progetto "RICHIAMI" (http://www.dsy.it/forum/showthread.php?threadid=17192)
Posted by LjL on 22-02-2005 14:14:
Originally posted by Skilotto83
[snip]
Certo che ci pensavo ieri...chi ha risolto con ricerca esaustiva su una ricerca di percorso da (-10000,-5000) a (10000,5000) ci mette un botto....deve spararsi migliaia di celle...
[snip]
Sì, ma c'è da dire che o sono molto tonto io oppure riuscire a fare il calcolo *senza* una ricerca esaustiva non è proprio così facile! Adesso ci sono riuscito anch'io, ma ci ho messo veramente un bel po', e comunque la complessità in spazio e in tempo è O(n²), e sono sicuro che volendo si può diminuire... tu fai meglio di così? (tra l'altro O(n²) è per ogni automa; se devi far spostare tutti gli automi, O(n³))__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Posted by p2p on 22-02-2005 14:20:
voi avete un idea di perchè la mia funzione va in loop con t 1000 2000 01 mentre con tutti gli altri input va?
quale potrebbe essere la causa??
sto facendo un po' di prove con valori diversi e gia' un t 50 100 01 va in loop...va in loop per valori un po' troppo grossi...se sono piccoli ok altrimenti va in loop...
Posted by LjL on 22-02-2005 14:35:
Originally posted by p2p
voi avete un idea di perchè la mia funzione va in loop con t 1000 2000 01 mentre con tutti gli altri input va?
quale potrebbe essere la causa??
sto facendo un po' di prove con valori diversi e gia' un t 50 100 01 va in loop...va in loop per valori un po' troppo grossi...se sono piccoli ok altrimenti va in loop...
Non ne ho idea anche perché non so (e non voglio sapere!) che algoritmo usi... non so, prova il comando 't' sullo stesso automa con tutte le coordinate da 0 in poi (facendo in modo che il rettangolo descritto da automa e punto di richiamo sia un quadrato), e guarda qual è esattamente il punto in cui comincia a bloccarsi.
Se usi una funzione ricorsiva, potrebbe essere un problema di stack, altrimenti potrebbe essere comunque un problema di memoria di qualche genere (magari vai a scrivere dove non dovresti, ma per input piccoli le probabilità che il sistema se ne accorga sono basse).
Potrebbe esserti d'aiuto un debugger.
Tra l'altro per fare prove con input un po' grossi ti consiglio il mio programmino, che se per altri tipi di test non è un granché, sulla "quantità" è abbastanza utile 
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Posted by elpampero on 22-02-2005 14:59:
scusate ma su windows come faccio a calcolarmi il tempo di esecuzione?
Posted by LjL on 22-02-2005 15:09:
Originally posted by elpampero
scusate ma su windows come faccio a calcolarmi il tempo di esecuzione?
O ti guardi come si usano le funzioni che sono state citate, oppure
http://groups-beta.google.com/group...da01bf1525cc09a
Anche se così ad occhio non mi sembra un approccio di gran precisione.__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Posted by elpampero on 22-02-2005 15:11:
il problema è che se io faccio
TIME programma<input mi da come output "ora specificata non valida.
Tuttavia ho provato a fare un test con cifre molto grandi e ci impiega sicuramente meno di un secondo
Posted by LjL on 22-02-2005 15:18:
Originally posted by elpampero
il problema è che se io faccio
TIME programma<input mi da come output "ora specificata non valida.
Tuttavia ho provato a fare un test con cifre molto grandi e ci impiega sicuramente meno di un secondo
Grazie, il comando time su Windows fa un'altra roba
Le funzioni a cui mi riferivo sono quelle di cui parlava qualcun altro, non io, quelle nell'header time.h o quel che è.
Fondamentalmente all'inizio della main() devi guardare che ora è, e alla fine del main() guardi di nuovo e fai la differenza.
In quel thread che ho indicato comunque c'è un metodo più semplice basato su un file .BAT.
P.S. per curiosità, per input *quanto* grandi ci mette meno di un secondo (e che processore hai)?
P.P.S. se ci mette meno di un secondo, comunque, i valori che puoi ottenere col file .BAT sicuramente non saranno molto significativi...__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Posted by mattcobain on 22-02-2005 15:22:
Originally posted by virtual
Quanto impiega il vostro programma ad eseguire tutto l'input delle specifiche?
Il mio 37 secondi su PIII 1GHz.
37 secondi sull'input del prof?!?!?!
e la madonna!!!!!
cmq il mio, l'input del prof lo esegue in 0.03 secondi...il mio pc (non deridetemi 
) è un malconcio pentium 2, 450 Mhz con 196 KB di ram.... sono all'antica!!! 
e poi, cosa davvero strana, per fare invece l'input che ho postato qui, ci metto 0 secondi!!! per far arrivare il tempo a 0.03 devo copiare ed incollare le stesse righe di input almeno una 50ina di volte, ogni volta ricreando il piano!!!!
ho fatto un mega algoritmo della madonna supersonico (considerando su che pc lo sto facendo girare) oppure è una cosa normalissima!?!?!
Posted by LjL on 22-02-2005 15:30:
Originally posted by mattcobain
37 secondi sull'input del prof?!?!?!
e la madonna!!!!!
cmq il mio, l'input del prof lo esegue in 0.03 secondi...il mio pc (non deridetemi ) è un malconcio pentium 2, 450 Mhz con 196 KB di ram.... sono all'antica!!!
Figurati, io ho un 350MHz e solo perché me l'hanno regalato (altrimenti 233MHz)...
Certo, i 196 *kilo*byte di RAM un po' perplesso mi lasciano
e poi, cosa davvero strana, per fare invece l'input che ho postato qui, ci metto 0 secondi!!! per far arrivare il tempo a 0.03 devo copiare ed incollare le stesse righe di input almeno una 50ina di volte, ogni volta ricreando il piano!!!!
ho fatto un mega algoritmo della madonna supersonico (considerando su che pc lo sto facendo girare) oppure è una cosa normalissima!?!?!
Boh, è un po' strano che tu ci metta di meno col tuo input che con quello del prof, dato che il tuo sembra più grosso...
Tieni conto che time ha una certa granularità, e anch'io devo avere input di una certa dimensione prima di superare gli "0 secondi".
Io comunque per l'input del prof ci metto 0.05 secondi (tempo reale) e 0.005 secondi (tempo utente).
Per il tuo input, 0.1 e 0.005 rispettivamente.
[Non sono i numeri veri che mi vengono fuori, sono medie fatte a occhio su 4-5 esecuzioni, dato che i valori cambiano parecchio di volta in volta]
[Compilato con gcc -O3]__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Posted by LjL on 22-02-2005 15:34:
Piuttosto comunque, quanto ci mettete voi per quest'input generato col programmino mio solito?
9182c0a200o200s200p200e200t200
Io ci metto 15 secondi (350MHz).
P.S. 15 secondi tolto il tempo per stampare l'output a video, cioè guardando il "tempo utente" sul comando time, o sopprimendo in qualche modo l'output (su Unix, aggiungendo >/dev/null alla linea di comando, su Windows, boh, forse >NIL: o >NUL: )
Ricordatevi anche di aggiungere 'f' alla fine dell'input, dato che il mio programma non lo mette 
__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Posted by mattcobain on 22-02-2005 15:36:
Originally posted by LjL
...Boh, è un po' strano che tu ci metta di meno col tuo input che con quello del prof, dato che il tuo sembra più grosso...
esatto, proprio quello mi ha fatto rimanere stranito!!!!
cmq ho riprovato piu volte e mi da sempre cosi....come ho detto, per fargli raggiungere un tempo nell'ordine degli 0.03 secondi devo copiare l'input e incollarlo una 50ina di volte, ogni volta facendogli ricreare il piano!!!!
e anche quello del prof....vero che la libreria time da valori non sempre uguali, ma anche qui, provando e riprovando, ottengo sempre o 0.03 o 0.04 secondi.....niente piu, niente meno!!!
ma fico....magari ho fatto davvero un buon lavoro!!! 
boicottiamo i supercomputeroni degli ultimi 2 anni....torniamo ai 486!!!
Posted by LjL on 22-02-2005 15:47:
Originally posted by mattcobain
ma fico....magari ho fatto davvero un buon lavoro!!!
Se non fai dipendere il tempo di calcolo dalla distanza tra automi e richiamo, secondo me hai già fatto un buon lavoro.
Prova anche con input più grossi però, per vedere effettivamente come cresce la complessità... io ad esempio ho provato degli input che non fanno altro che creare n automi, con n da 0 a 2000 in incrementi di 10 (nel mio programma la creazioni di un'automa non è un'operazione O(1)).
Il grafico che mi viene fuori fa vedere una cosa che sembra proprio una parabola, come mi aspettavo.
Ad esempio:
500 automi = 0.5 secondi
1000 automi = 1.8 secondi
1500 automi = 4.23 secondi
2000 automi = 7.5 secondi
boicottiamo i supercomputeroni degli ultimi 2 anni....torniamo ai 486!!! [/B]
E chi se ne è mai andato?
Ok magari dai 486 me ne sono andato, però i quattro computer che uso sono un 350MHz, un 200MHz, un altro 200MHz e un 36MHz __________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
Posted by mattcobain on 22-02-2005 15:53:
Originally posted by LjL
Piuttosto comunque, quanto ci mettete voi per quest'input generato col programmino mio solito?
9182c0a200o200s200p200e200t200
Io ci metto 15 secondi (350MHz).
P.S. 15 secondi tolto il tempo per stampare l'output a video, cioè guardando il "tempo utente" sul comando time, o sopprimendo in qualche modo l'output (su Unix, aggiungendo >/dev/null alla linea di comando, su Windows, boh, forse >NIL: o >NUL
Ricordatevi anche di aggiungere 'f' alla fine dell'input, dato che il mio programma non lo mette
maledetto, stai mettendo in crisi il mio pc
è tipo da 6 minuti che sto aspettando i risultati, ma ancora è qui che macina...poveraccio!!!!
anche perché non ho mica soppresso l'output....mica ho capito come si fa....
ma si, ormai aspetterò i risultati, magari domani riuscirò a postarli!!!!!
Posted by Petrik22 on 22-02-2005 16:07:
panico!!!
Posted by LjL on 22-02-2005 16:19:
Originally posted by mattcobain
maledetto, stai mettendo in crisi il mio pc
è tipo da 6 minuti che sto aspettando i risultati, ma ancora è qui che macina...poveraccio!!!!
anche perché non ho mica soppresso l'output....mica ho capito come si fa....
ma si, ormai aspetterò i risultati, magari domani riuscirò a postarli!!!!!
Ihihihi... be', di sicuro se aggiungi ">filequalsiasi" alla linea di comando l'output finisce su filequalsiasi, il che potrebbe essere comunque più veloce che farlo stampare sulla console.
Comunque stampando su console io ci metto 20 secondi. Vedete che non conta solo il tempo di esecuzione sui bassi numeri? O meglio, se conta o no non lo sappiamo, dato che non sappiamo che tipo di input propinerà il prof ai nostri programmi... però il senso del corso di algoritmi, sempre che io l'abbia capito, è quello di insegnarci a scrivere algoritmi asintoticamente buoni.
Se ti può consolare del fatto che il mio programma sembra meno complesso in tempo del tuo, è probabile che in spazio il tuo sia il sogno di ogni automa rispetto al mio Specialmente se usi liste dinamiche...
P.S. Oh, a proposito, hai detto "macina"? Sarebbe a dire semplicemente che è lì a calcolare, o macina nel senso che macina il disco fisso? Se è la seconda vuol dire che il tuo algoritmo è subottimale in *spazio* e non in tempo, o in altre parole che finisci la RAM e il sistema è costretto a usare lo swap. Se è così interrompi pure, tanto il risultato non avrebbe nessun significato.__________________
by LjL
ljlbox@tiscali.it
http://ljl.150m.com - appunti corsi
