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

Posts: 16


« Reply #15 on: 12-04-2011, 20:25:32 »

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.

Perfettamente daccordo su tutto.

Aggiungo anche che, sempre in nome della velocita' di esecuzione, e' stato prodotto a volte del codice che non si puo' definire ne di semplice lettura ne chiaro. Ma che senso ha utilizzare un linguaggio di alto livello se poi bisogna andare quasi a fare RE sul codice. Neanche uno straccio di commento nei punti piu' oscuri poi..

Comunque, credo che in questa fase sia importante _anche_ valutare la capacita' di sapere leggere, scrivere ed immagazzinare i dati in maniera efficente, oltre che di sapere scrivere buoni algoritmi che elaborino i dati stessi.
Logged
FReddy
Apprendista Forumista
**
Offline Offline

Posts: 367



« Reply #16 on: 12-04-2011, 21:47:26 »

Quote
oltre che di sapere scrivere buoni algoritmi che elaborino i dati stessi.

Credo che dalla prossima gara in poi saper elaborare un algoritmo efficiente servirà eccome.
Logged

Il presente è ora,
Il passato era ora,
Il futuro sarà ora.
zeridos89
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 127


Diego Sinitò


« Reply #17 on: 13-04-2011, 10:48:44 »

Code:
440 38083.19921875Kg
23405 723158.75Kg
18830 867228Kg
27261 1137257.625Kg
85215 4611728.5Kg
49063 2937791.5Kg
1925 62854.00390625Kg
6422 129706.734375Kg
44704 2452831.75Kg
56925 5135476.5Kg
68068 5481603.5Kg
238612 37849836Kg
9800 997878Kg

guardiamo per esempio questo output, il peso totale doveva essere scritto con un approsimazione di 2 cifre decimali.
Nella maggior parte dei casi produce un output errato!

Questo è un output 100% corretto

Code:
440 38083.20Kg
23405 723158.70Kg
18830 867227.90Kg
27261 1137257.55Kg
85215 4611728.85Kg
49063 2937790.10Kg
1925 62854.00Kg
6422 129706.72Kg
44704 2452831.04Kg
56925 5135476.50Kg
68068 5481604.44Kg
238612 37849847.64Kg
9800 997878.00Kg

le differenze tra questi due output sono molto evidenti, quindi secondo quale criterio è stato valutato?
confrontando tutte le 40000 linee quelli scritti in maniera errata sono 39576

guardando altri output dei primi in classifica abbiamo circa 2500 righe errate, prodotti dalla cattiva gestione delle cifre decimali.
È normale che evitando di arrotondare in maniera corretta si risparmia molto tempo.

Io non dico di scartare tutti gli output errati, ma almeno dare un malus in proporzione agli errori per pareggiare il gap con chi produce un output giusto tenendo in cosiderazione tutti i casi. Anche perché è possibile produrre un output corretto e veloce (vedi i primi 3 in classifica), basta solo impegnarsi di più!
« Last Edit: 13-04-2011, 11:58:18 by zeridos89 » Logged
zeridos89
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 127


Diego Sinitò


« Reply #18 on: 13-04-2011, 12:26:54 »

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.

se il tuo programma nell'input grande (non quello del pdf) ti da una correttezza del 100% sono quasi certo che te lo darà anche in quello che usa il professore al momento del controllo, quindi puoi correggere i tuoi errori e fare in modo che il programma sia corretto al 100%. Quindi perchè vengono consegnate soluzioni errate?
Logged
R3m
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 486



« Reply #19 on: 13-04-2011, 12:57:09 »

Code:
440 38083.19921875Kg
23405 723158.75Kg
18830 867228Kg
27261 1137257.625Kg
85215 4611728.5Kg
49063 2937791.5Kg
1925 62854.00390625Kg
6422 129706.734375Kg
44704 2452831.75Kg
56925 5135476.5Kg
68068 5481603.5Kg
238612 37849836Kg
9800 997878Kg

guardiamo per esempio questo output, il peso totale doveva essere scritto con un approsimazione di 2 cifre decimali.
Nella maggior parte dei casi produce un output errato!

Questo è un output 100% corretto

Code:
440 38083.20Kg
23405 723158.70Kg
18830 867227.90Kg
27261 1137257.55Kg
85215 4611728.85Kg
49063 2937790.10Kg
1925 62854.00Kg
6422 129706.72Kg
44704 2452831.04Kg
56925 5135476.50Kg
68068 5481604.44Kg
238612 37849847.64Kg
9800 997878.00Kg

le differenze tra questi due output sono molto evidenti, quindi secondo quale criterio è stato valutato?
confrontando tutte le 40000 linee quelli scritti in maniera errata sono 39576

guardando altri output dei primi in classifica abbiamo circa 2500 righe errate, prodotti dalla cattiva gestione delle cifre decimali.
È normale che evitando di arrotondare in maniera corretta si risparmia molto tempo.

Io non dico di scartare tutti gli output errati, ma almeno dare un malus in proporzione agli errori per pareggiare il gap con chi produce un output giusto tenendo in cosiderazione tutti i casi. Anche perché è possibile produrre un output corretto e veloce (vedi i primi 3 in classifica), basta solo impegnarsi di più!

Non è vero che arrotondando le cifre si risparmia molto tempo...il mio programma le gestisce correttamente, poi sono un #@!!01Z#@!!@$^ che ho usato il printf che nel c risulta veloce e nel java no -.- f**k yeah xD altrimenti avrei avuto una posizione mooooooolto più alta in classifica...

E comunque nessuno ti vieta di produrre programmi più veloci con output meno corretti...
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.
zeridos89
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 127


Diego Sinitò


« Reply #20 on: 13-04-2011, 13:16:35 »

bhè puoi gestire le cifre decimali in vari modi: double, float, big decimal, moltiplicare per 100 e usare i long..
se usi i big decimal avrai un programma al 100% ma lentissimo, se usi i float hai un programma il doppio più veloce solo che non riesce a gestire tutti i numeri infatti in alcuni avrai l'esponenziale...

quindi dal tipo di gestione delle cifre dipende la velocità del programma
Logged
R3m
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 486



« Reply #21 on: 13-04-2011, 14:05:08 »

Il bigdecimal viene corretto ma è lentissimoooooooo, i float/double sballano (di molto) i calcoli quindi avrebbe una correttezza minore dell'80%...il modo migliore è moltiplicare x 100 e usare i long..

Come mai hai usato il BigDecimal?
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.
FReddy
Apprendista Forumista
**
Offline Offline

Posts: 367



« Reply #22 on: 13-04-2011, 14:35:07 »

Quote
E comunque nessuno ti vieta di produrre programmi più veloci con output meno corretti...

Sinceramente non credo sia possibile pensare cose del tipo: "questo lo faccio meno corretto e risparmio tempo", per il semplice fatto che non puoi calcolare la percentuale di errore in anticipo. Inoltre anche se fosse possibile, in generale (magari in questo caso no), non credo che, anche se fosse possibile raggiungere in maniera millimetrica la soglia dell' 80%, l'esecuzione risulti più veloce.

Per quanto riguarda la possibilità di ridurre il punteggio in base alla correttezza dell'output è fattibile, ma alla fine non credo cambi un granché dato che non esiste il "gruppo fisso di quelli che danno soluzioni veloci con correttezza 80%" ed il "gruppo fisso di quelli che danno soluzioni corrette al 100% ma meno veloci", ma soltanto delle persone che una volta possono dare una soluzione corretta e  non tanto veloce ed un'altra una soluzione veloce ma non proprio corretta. 
Logged

Il presente è ora,
Il passato era ora,
Il futuro sarà ora.
zeridos89
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 127


Diego Sinitò


« Reply #23 on: 13-04-2011, 17:39:04 »

@R3m: ne ho fatte tre versioni, alla fine ho usato i lentissimi big decimal perchè con quelli l'output era corretto al 100%. Anche se lunedì ho sistema la versione long.

Comunque Freddy bisognerebbe sempre farli al 100%, ed è possibile! Basta solo provare il programma con l'input grande,  scambiare l'output con un collega e confrontarli, se magari i due file sono diversi si fa un controllo carta e penna e si guarda quello corretto. Nella prima gara invece era anche presente un output.

Riguardo il malus, se la memoria non mi inganna ricordo che avevo un vecchio gioco di formula1 e se nel percorso evitavo una curva e tagliavo sul prato mi veniva dato un malus; quindi dare un malus porterebbe un po di equilibrio tra errori e velocità, io personalmente sono scavalcato da circa 10 persone con output errati.
Logged
R3m
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 486



« Reply #24 on: 13-04-2011, 18:18:42 »

Non voglio scatenare una polemica, però facendo l'esercizio con i long l'output viene corretto al 100% e viene anche veloce (credo che sia il migliore rapporto qualità/velocità).

Tra l'altro ,per esperienza, sò che adesso le prove andranno a complicarsi molto, ed eseguire un programma che sia corretto più dell'80% in modo che sia molto più veloce di uno tutto corretto diventerà quasi impossibile....

In questo caso specifico, comunque, farlo al 100% corretto era molto semplice, furbate tipo stampare un solo numero dopo la virgola o nessuno non migliorano di molto la velocità del programma...
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.
Pages: 1 [2]   Go Up
Print
Jump to: