Pages: [1] 2   Go Down
Print
Author Topic: Programma veloce || output corretto ?  (Read 3233 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Gerry
Matricola
*
Offline Offline

Posts: 73


« on: 11-04-2011, 22:08:42 »

Perchè mai si dovrebbe preferire un programma veloce che dia un output non del tutto corretto ad uno leggermente più lento ma che calcoli la giusta soluzione??? D'altra parte è probabile che un programma non del tutto corretto sia più veloce proprio perchè non svolge alcune operazioni che lo renderebbero un programma robusto e funzionante al 100%. Forse esagero, dato che noi non svolgiamo ancora programmi complessi, ma chi comprerebbe mai un programma veloce che non funziona bene?
Logged
zElOtO
Forumista
***
Offline Offline

Gender: Male
Posts: 845



WWW
« Reply #1 on: 11-04-2011, 22:22:41 »

  
Logged

I computer sono incredibilmente veloci, accurati e stupidi. Gli uomini sono incredibilmente lenti, inaccurati e intelligenti. Insieme sono una potenza che supera l'immaginazione. (A. Einstein)

Damiano Cancemi
www.damianocancemi.com
www.nerdbren.com
www.nerdbren.com/blog
RobyP
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 111



« Reply #2 on: 11-04-2011, 22:39:24 »

chi comprerebbe mai un programma veloce che non funziona bene?
Logged
R3m
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 486



« Reply #3 on: 11-04-2011, 22:44:25 »

La questione è abbastanza complessa...qui non si parla di un intero programma che non funziona perfettamente, ma di soluzioni ad alcuni problemi.

Ad esempio, uno di questi è l'ordinamento..molti modi di ordinare, molti algoritmi veloci, ma anche molti che funzionano sotto certe condizioni...

Altro argomento è la ricerca, puoi cercare in maniera lineare, oppure mediante ricerca dicotomica, oppure con le tabelle hash...la differenza è il tempo...ed è una differenza nettissima confrontando hash e le altre due.
Di contro, però, le tabelle hash potrebbero presentare collisioni e quindi fallire in alcuni casi.

Io sono dell'idea che un programma debba funzionare al 100% perchè esistono soluzioni che possono migliorare la velocità di un programma, ovvero sfruttare i multicore, sfruttare le gpu e ottimizzare come meglio si può senza compromettere il funzionamento...
Logged

Ciò che è nostro è stato in campo sudato....ciò che vostro è stato in aula assegnato.
In serie B non sei mai stato perchè la prescrizione t'ha salvato.
ɹǝǝuıƃuǝsɹǝʌǝɹ
Administrator
God of the Forum
*****
Offline Offline

Gender: Male
Posts: 4.474


Più grande è la lotta, e più è glorioso il trionfo


WWW
« Reply #4 on: 11-04-2011, 22:49:14 »

Fermo restando che eliminare i bug al 100% è impossibile, ricordo che il "bug" non è una cosa voluta.
Qui si sta parlando, invece, di una caratteristica che è stata deliberatamente e volontariamente lasciata da parte -la totale correttezza- perché si vuole fare una cosa "veloce"... mmm...

Un programma che non calcola quello che deve certamente non mi interessa , nè se è veloce nè se è lento no.
Un programma che calcola quello che mi interessa potrebbe interessarmi, a seconda di tanti fattori.

La questione è più delicata e, se volete, filosofica di quanto possiate immaginare...
È un po' come la distinzione tra giusto e sbagliato, o se volete tra vero e falso: non si dovrebbe essere interessati alle cose sbagliate, sia che i suoi risultati portino avanti quantomeno un nostro personalissimo interesse sia che facciano del male a tutti (in realtà è vera solo la seconda parte); e anche: ciò che è falso non contribuisce a nulla di buono, ma, piuttosto, la verità apre gli occhi, e non può fare altro che bene...

Mi fa piacere che sia stata posta questa domanda, anche se non si è data una risposta assoluta.
Porsi domande (sì, anche solo porsele, senza pretendere di avere la risposta in tasca) di questo tipo fa certamente bene .

Buonanotte .
Logged

La grande marcia della distruzione mentale proseguirà. Tutto verrà negato. Tutto diventerà un credo. È un atteggiamento ragionevole negare l'esistenza delle pietre sulla strada; sarà un dogma religioso affermarla. È una tesi razionale pensare di vivere tutti in un sogno; sarà un esempio di saggezza mistica affermare che siamo tutti svegli. Accenderemo fuochi per testimoniare che due più due fa quattro. Sguaineremo spade per dimostrare che le foglie sono verdi in estate. Non ci resterà quindi che difendere non solo le incredibili virtù e saggezze della vita umana, ma qualcosa di ancora più incredibile: questo immenso, impossibile universo che ci guarda dritto negli occhi. Combatteremo per i prodigi visibili come se fossero invisibili. Guarderemo l'erba e i cieli impossibili con uno strano coraggio. Saremo tra coloro che hanno visto eppure hanno creduto.

In tutto, amare e servire.

  
                            ن                           
I can deal with ads,
I can deal with buffer,
but when ads buffer
I suffer...

...nutrimi, o Signore, "con il pane delle lacrime; dammi, nelle lacrime, copiosa bevanda...

   YouTube 9GAG    anobii  S  Steam T.B.o.I. Wiki [univ] Lezioni private  ʼ  Albo d'Ateneo Unicode 3.0.1
Usa "Search" prima di aprire un post - Scrivi sempre nella sezione giusta - Non spammare - Rispetta gli altri utenti - E ricorda di seguire il Regolamento
Zarathustra^
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 100


« Reply #5 on: 12-04-2011, 07:53:59 »

Se per output non del tutto corretto s'intende un'approssimazione del risultato, perché no?

Esempio: http://en.wikipedia.org/wiki/Fast_inverse_square_root
Logged
Simone Faro
Moderator
Matricola
*****
Offline Offline

Gender: Male
Posts: 67


WWW
« Reply #6 on: 12-04-2011, 08:02:15 »

La domanda è interessante. Abbiamo anche accennato il problema a lezione, parlando della correttezza di un programma.
In effetti non siamo interessati ad una soluzione non ottima, ma potremmo essere interessati ad una soluzione quasi ottima, se l'errore legato alla nostra soluzione è molto basso.
Questo dipende dal fatto che molti problemi di interesse pratico purtroppo sono NP-completi (non esiste un algoritmo efficiente per risolverli), ma sono troppo importanti per rinunciarvi soltanto perchè non si riesce ad elaborare una loro soluzione ottima in un tempo ragionevole. Se un problema è NP-completo, è poco probabile che riusciamo a trovare un algoritmo con tempo polinomiale che lo risolve con esattezza.
Ci sono tre approcci principali per affrontare la NP-completezza.
1) se gli input effettivi sono piccoli un algoritmo con tempo di esecuzione esponenziale può fornire il risultato ottimo in tempi soddisfacenti.
2) potremmo riuscire ad isolare importanti casi speciali del problema risolvibili in tempo polinomiale.
3) potrebbe essere possibile trovare soluzioni quasi ottime in tempo polinomiale. Nella pratica una soluzione quasi ottima è spesso accettabile. Un algoritmo in grado di restituire soluzioni quasi ottime è detto algoritmo di approssimazione.
Un algoritmo approssimato può anche dare una soluzione errata al problema ma garantisce sempre che l'errore legato al costo della sua soluzione sia al di sotto di una certa soglia di tolleranza.
Una soluzione quasi ottima ad un problema potrebbe essere considerata accettabile anche per problemi non NP-completi ma la cui dimensione risulti troppo elevata per essere risolto in tempo ragionevole.

Facciamo un esempio banale:
Sareste disposti ad aspettare 1 minuto per conoscere la distanza minima da percorrere per raggiungere il vostro luogo di destinazione, o preferite saperlo in 2 secondi con un margine di errore di +/- 100 m ?
« Last Edit: 12-04-2011, 08:04:05 by Simone Faro » Logged

________________________________
Simone Faro, Ph.D.
Dipartimento di Matematica e Informatica
Università di Catania
________________________________
Chuck_son
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 1.583



WWW
« Reply #7 on: 12-04-2011, 10:35:10 »

Sareste disposti ad aspettare 1 minuto per conoscere la distanza minima da percorrere per raggiungere il vostro luogo di destinazione, o preferite saperlo in 2 secondi con un margine di errore di +/- 100 m ?


che stile  yoh
Logged

Aliens Exist
Gerry
Matricola
*
Offline Offline

Posts: 73


« Reply #8 on: 12-04-2011, 11:59:01 »

I 58 secondi che risparmio di attesa sicuramente li perdo nel cercare il luogo preciso di destinazione in quei 100 metri di approssimazione. Se si tratta di conoscere il percorso.
« Last Edit: 12-04-2011, 12:18:55 by Gerry » Logged
m4rc0
Matricola
*
Offline Offline

Posts: 16


« Reply #9 on: 12-04-2011, 12:40:47 »

Gerry.. era un esempio per dire che in certe situazioni e' preferibile la velocita' alla precisione.. solo un esempio. In certe situazioni +/- 100m potrebbe essere un buon margine di errore. Dipende.
Logged
Gerry
Matricola
*
Offline Offline

Posts: 73


« Reply #10 on: 12-04-2011, 12:50:43 »

Un errore che si può evitare ...ok comunque io resto dell'idea che è meglio la precisione. In particolare che è meglio imparare a programmare senza errori. ( Avrei perso sicuramente meno tempo a fare il programma della gara se non mi fossi impegnata per avere l'output corretto al 100%  ... )
Logged
zElOtO
Forumista
***
Offline Offline

Gender: Male
Posts: 845



WWW
« Reply #11 on: 12-04-2011, 13:08:53 »

I 58 secondi che risparmio di attesa sicuramente li perdo nel cercare il luogo preciso di destinazione in quei 100 metri di approssimazione. Se si tratta di conoscere il percorso.

Gerry.. era un esempio per dire che in certe situazioni e' preferibile la velocita' alla precisione.. solo un esempio. In certe situazioni +/- 100m potrebbe essere un buon margine di errore. Dipende.
Logged

I computer sono incredibilmente veloci, accurati e stupidi. Gli uomini sono incredibilmente lenti, inaccurati e intelligenti. Insieme sono una potenza che supera l'immaginazione. (A. Einstein)

Damiano Cancemi
www.damianocancemi.com
www.nerdbren.com
www.nerdbren.com/blog
m4rc0
Matricola
*
Offline Offline

Posts: 16


« Reply #12 on: 12-04-2011, 13:11:37 »

Se l'errore e' accettabile, perche' bisogna utilizzare un algoritmo magari di molto piu' lento per sforzarsi di avere un risultato esatto al 100%?

Tra l'altro non solo gli algoritmi possono essere imprecisi, ma da un po' di tempo si parla anche di "chip" imprecisi (chiamati anche probabilistici). L'idea e' simile: creare dei chip che non producono sempre risultati esatti, ma che sono piu' veloci ad elaborare i dati di input rispetto alla controparte piu' precisa.

http://www.hwupgrade.it/news/cpu/il-futuro-e-nei-chip-imprecisi_27992-80.html (qui se ne parla, per esempio)


Logged
GT89
Matricola
*
Offline Offline

Posts: 18


« Reply #13 on: 12-04-2011, 16:27:00 »

Quote
( Avrei perso sicuramente meno tempo a fare il programma della gara se non mi fossi impegnata per avere l'output corretto al 100%  ... )

Ciao,    NON credo che avresti risolto il quesito in meno tempo se tu avessi deciso di consegnare una soluzione con una percentuale di correttezza inferiore a 100% ma comunque non inferiore all'80%.
Come fai a dire che -quella parte di output che ti manca o non è corretta- non ti farà scendere al di sotto dell'80%?
Non sai mai in anticipo quale sarà l'input sul quale verrà fatto il calcolo delle prestazioni, quindi in ogni caso l'algoritmo va fatto in modo che l'output sia corretto al 100% (nel caso delle gare di programmazione 2); così, se per qualche ragione imprevista, l'output corretto dovesse contenere valori che non corrispondono con quello tuo, almeno potrai aver raggiunto una percentuale di correttezza maggiore di quella che avresti ottenuto tenendo conto di voler raggiungere una percentuale inferiore a 100%, sperando sempre che non scenda al di sotto di 80.
Credo che si perda molto tempo per rendere la soluzione più efficiente, non per renderla più corretta.
Logged
eLis
Apprendista Forumista
**
Offline Offline

Gender: Female
Posts: 111



« Reply #14 on: 12-04-2011, 19:24:33 »

mi sembra ragionevole che spesso non sia indispensabile la correttezza assoluta quando questo voglia dire guadagnare in velocita', e credo talvolta "correttezza" tocchi problemi quasi filosofici sul concetto di verita'.

Pero' vorrei riportare la discussione alla nostra competizione. Il punto fondamentale per me e' che qui la correttezza e' misurata sulla pura differenza in byte tra uscita di un programma e quella di riferimento.
Mettiamo la prima competizione, in cui il risultato richiesto e' la coordinata in una matrice.
Supponiamo che il risultato di riferimento sia
           (00, 23)
e che qualcuno produca invece
             0        23
naturalmente le coordinate sono le stesse, uno che acquisti quel software sarebbe soddisfatto, ma la percentuale di correttezza misurata nella nostra competizione sarebbe meno del 10%
se un altro invece producesse
           (90, 23)
sarebbe rientrato ampiamente nel 80% di correttezza, ma chiaramente se la coordinata dovesse essere usata da un utente di quel software, ci rimarrebbe piuttosto deluso...
Insomma, non mi pare che qui il concetto di approssimazione sia proprio quello in gioco.
La correttezza dell'algoritmo viene posta sullo stesso piano della precisione nella formattazione in scrittura.

Il punto mi sembra simile alla questione anche della velocita': di fatto nelle due gare finora svolte, l'efficienza nell'algoritmo solutivo era di fatto poco rilevante rispetto all'efficienza nella lettura e scrittura dei file, sono di gran lunga quelle le operazioni che hanno deciso i tempi complessivi di esecuzione.
Logged

The Man in Black fled across the desert, and the Gunslinger followed.
Pages: [1] 2   Go Up
Print
Jump to: