[Contest] Proposta per i nuovi contest

[cionci]

Visto che ne avete parlato, faccio qui la mia proposta per il contest.
L'idea è quella di rendere il più possibile indipendente il contest dal linguaggio e di poter giudicare l'algoritmo migliore e non il programma più veloce.
Come fare ? L'unica soluzione che mi viene in mente è quella di proporre una soluzione di riferimento in pseudo-linguaggio data da chi propone il contest. Ovviamente questa sarà la soluzione più immediata, ma anche computazionalmente meno efficiente (ed esempio la forza bruta).
Per ogni linguaggio che partecipa al contest, il primo utente che lo usa deve proporre una soluzione che rispecchia fedelmente quella in pseudo-linguaggio, con tanto di struttura e nomi corrispondenti.
Chi crea il contest si occuperà di raccogliere queste soluzioni nel primo post. Queste saranno le soluzioni di riferimento sulle quali il contest si dovrà basare e sulle quali verranno prese le misure di prestazioni delle soluzioni ottimizzate.
Posto 1 il valore della soluzione di riferimento si dovrà ottenere il coefficiente relativo alla soluzione ottimizzata in questo modo:

X = TempoEsecuzioneSoluzioneOttimizzata / TempoEsecuzioneSoluzioneRiferimento

Edit: avevo invertito i valori

Vince il contest chi ottiene il coefficiente migliore rispetto alla soluzione di riferimento nel proprio linguaggio.

[banryu79]

Non ho capito una cosa: se chi propone il Contest, è lo stesso utente che scrive la soluzione di riferimento in pseudocodice, e gli altri partecipanti, la prima volta che partecipano con un linguaggio X che non era ancora stato adoperato nel Contest, si devono limitare a implementare la soluzione descritta dallo pseudocodice in un linguaggio a loro scelta, allora per formulare una nuova soluzione, diversa da quella di riferimento, bisogna utilizzare un linguaggio che è già stato usato almeno una volta nel contest e si può presentare subito la sua implementazione in quel linguaggio X senza prima stendere lo pseudocodice che la descrive?

(scusa il periodo lungo)


@EDIT:
Altra cosa... La sintassi dello pseudocodice è a scelta dell'utente che propone il contest (e in caso gli altri partecipanti ne vogliano fare uso devono cercare di aderire alle convenzioni usate dal proponente del contest) oppure si fa tutti riferimento sempre e comunque ad uno "standard" noto? (ad esempio lo pseudocodice usato nel testo "Introduzione agli algoritmi e strutture dati" di Cormen, Leiserson, Rivest e Stein)

[cionci]

Allora spiego meglio:
- chi scrive lo pseudocodice per la soluzione di riferimento è chi crea il contest
- un utente vuole partecipare al contest:
---- deve presentare la soluzione di riferimento scritta nel linguaggio scelto se ancora non esiste una soluzione di riferimento in quel linguaggio
---- se esiste una soluzione di riferimento scritta in quel linguaggio allora può passare direttamente a scrivere la sua soluzione ottimizzata

L'implementazione della soluzione di riferimento deve essere identica in tutto e per tutto alla soluzione di riferimento scritta in pseudocodice, sia nei nomi delle variabili sia nella struttura, ovviamente nei limiti imposti dal linguaggio.

[cionci]

Allo scrivere la soluzione ottimizzata in pseudo codice non ci avevo pensato. Potrebbe essere una possibilità, magari lasciata a chi ha implementato gli algoritmi più performanti.

Riguardo alla scelta dello pseudocodice io lascerei piena libertà, anche se non segue uno standard è uguale, l'importante è che definisca bene le strutture dati, il loro dimensionamento e la struttura del codice. Anche una descrizione algoritmica in italiano con le varie righe numerate va benissimo.

[gugoXX]

Per me si puo' fare.
Peccato sempre non riuscire ad inserire un metro di misura sulla bellezza, sulla possibilita' di errori, sulla compattezza, etc.
Comunque e' un primo passo, magari ci verra' in mente altro.

[cionci]

Ah altra cosa: bisogna sempre inserire un test che verifichi che sia mantenuta la correttezza anche con dati di test più piccoli.
Ad esempio: in quello dell'altra volta del lotto alcune soluzioni (pure la mia) non funzionavano ricercando il singolo estratto. Manteniamo nei test di varie dimensioni anche la verifica del funzionamento dei subset più piccoli

[cionci]

Originariamente inviato da gugoXX

Peccato sempre non riuscire ad inserire un metro di misura sulla bellezza, sulla possibilita' di errori, sulla compattezza, etc.

Difficile misurare la bellezza. Per la compattezza qualcosa si può fare, ma dipende sempre troppo dal linguaggio usato, senza contare che compattezza e leggibilità, oltre un certo limite, non vanno quasi mai di pari passo

[marco.r]

La vedo difficile. Diversi linguaggi si comporteranno in modo differente rispetto alla soluzione naive, per cui non e' detto che il rapporto con questa sia indicativo. In alcuni casi potrebbe pure non essere praticabile perche' molto innaturale. In altri casi potrebbe non essere ovvia (es: in C++ qual e' la scelta naive per gli array ? puntatori? vector<> ? con [] o con .at ?).
Premesso che per il momento non ho comunque tempo per partecipare, secondo me ci sono tre modi corretti per procedere.
1 - Come si e' fatto finora, pero' con maggior rigore, ovvero con delle regole ben definite (come e' fatto l'input come e' fatto l'output etc.), con un insieme di test chiaro e non variabile, e che chi propone il contest fornisca un metodo per validare il risultato.
2 - Confronto sull'output generato e basta. Ad esempio vedere chi trova la piu' lunga sottosequenza palindroma di cifre nella rappresentazione decimale del pi greco . Ovviamente programmi piu' veloci permetteranno di trovare una soluzione in tempo piu' breve ma si eviteranno confronti tra i tempi di esecuzione alla terza cifra decimale
3 - Proporre una contest dove le soluzioni si "scontrano" (ad esempio come player di qualche giochino)

[DanieleC88]

Originariamente inviato da marco.r

3 - Proporre una contest dove le soluzioni si "scontrano" (ad esempio come player di qualche giochino)

Questa può essere una strada praticabile, ma bisogna scegliere il giochino giusto. Qualche tempo fa un nostro professore ha organizzato una sessione di "giochi di programmazione" includendo nel programma anche lo scontro di C-Robots. Io l'ho provato un po', ma non mi ci sentivo a mio agio (bisogna programmarli in un C castrato, parecchio castrato... a questo punto era meglio un linguaggio di scripting).

[marco.r]

Originariamente inviato da DanieleC88

Questa può essere una strada praticabile, ma bisogna scegliere il giochino giusto. Qualche tempo fa un nostro professore ha organizzato una sessione di "giochi di programmazione" includendo nel programma anche lo scontro di C-Robots. Io l'ho provato un po', ma non mi ci sentivo a mio agio (bisogna programmarli in un C castrato, parecchio castrato... a questo punto era meglio un linguaggio di scripting).

Una cosa che si puo' fare e' quella di definire una semplice interfaccia testuale tra l'arbitro e il programmino. A quel punto con qualsiasi linguaggio che permetta l'IO da console sei a posto. c'e' un po' di overhead dovuto al parsing delll'input e la generazione dell'output ma visto che lo devono fare tutti non dovrebbe costituire un problema. E' una soluzione che ho visto adottare in diverse competizioni di questo tipo.

[cionci]

Originariamente inviato da marco.r

In alcuni casi potrebbe pure non essere praticabile perche' molto innaturale.

Appunto ho scritto nei limiti del linguaggio adottato.

Originariamente inviato da marco.r

In altri casi potrebbe non essere ovvia (es: in C++ qual e' la scelta naive per gli array ? puntatori? vector<> ? con [] o con .at ?).

Dove c'è da fare una scelta di implementazione della soluzione, direi di scegliere sempre la scelta più performante.

Sia chiaro che non è semplice confrontare linguaggi diversi, però già l'ordine di grandezza del fattore relativo alla soluzione più performante è indicativo.
Possiamo stabilire che a parità di ordine di grandezza le soluzioni siano considerate equivalenti.

[Vincenzo1968]

Originariamente inviato da banryu79

...
Altra cosa... La sintassi dello pseudocodice è a scelta dell'utente che propone il contest (e in caso gli altri partecipanti ne vogliano fare uso devono cercare di aderire alle convenzioni usate dal proponente del contest) oppure si fa tutti riferimento sempre e comunque ad uno "standard" noto? (ad esempio lo pseudocodice usato nel testo "Introduzione agli algoritmi e strutture dati" di Cormen, Leiserson, Rivest e Stein)

Mi pare una buona idea. Riporto le convenzioni di codifica elencate nel libro citato:

Convenzioni di pseudocodifica
Adotteremo le seguenti convenzioni nelle nostre pseudocodifiche.
1. L’indentazione (rientro verso destra delle righe) serve a indicare la struttura a blocchi dello pseudocodice. Per esempio, il corpo del ciclo for, che inizia nella riga 1, `e formato dalla righe 2–8 e il corpo del ciclo while, che inizia nella riga 5, contiene le righe 6–7, ma non la riga 8. Il nostro stile di indentazione si applica anche alle istruzioni if-then-else. Utilizzando l’indentazione, anziché gli indicatori convenzionali della struttura a blocchi, come le istruzioni begin e end, si riduce molto la confusione, preservando o perfino migliorando la chiarezza(nei linguaggi di programmazione reali, in generale, non è consigliabile utilizzare soltanto l’indentazione per indicare la struttura a blocchi, in quanto i livelli di indentazione sono difficili da determinare quando il codice è distribuito su più pagine).

2. I costrutti iterativi while, for e repeat e i costrutti condizionali if, then ed else hanno interpretazioni simili a quelle del Pascal. C'è tuttavia una piccola differenza nei cicli for: nel Pascal il valore del contatore del ciclo è indefinito dopo la conclusione del ciclo, mentre in questo libro il contatore del ciclo mantiene il suo valore dopo la fine del ciclo. Quindi, immediatamente dopo un ciclo for, il valore del contatore del ciclo è quello che ha appena superato il limite del ciclo for. Abbiamo utilizzato questa proprietà nella nostra analisi della correttezza di insertion sort. La prima istruzione del ciclo for (riga 1) è for j ← 2 to lunghezza[A]; quindi, alla fine di questo ciclo, j = lunghezza[A] + 1 (che equivale a j = n +1, in quanto n = lunghezza[A]).

3. Il simbolo “//” indica che il resto della riga è un commento.

4. Un’assegnazione multipla della forma i ← j ← e assegna a entrambe le variabili i e j il valore dell’espressione e; deve essere considerata equivalente all’assegnazione j ← e seguita dall’assegnazione i ← j.

5. Le variabili (come i, j e chiave) sono locali a una determinata procedura. Non dovremmo utilizzare variabili globali senza un’esplicita indicazione.

6. Per identificare un elemento di un array, specifichiamo il nome dell’array seguito dall’indice dell’elemento fra parentesi quadre. Per esempio, A[i] indica l’elemento i-esimo dell’array A. La notazione “. .” `e utilizzata per indicare un intervallo di valori all’interno di un array. Quindi, A[1 . . j] indica il sottoarray di A che `e composto da j elementi: A[1],A[2], . . . ,A[j].

7. I dati composti sono tipicamente organizzati in oggetti, che sono formati da attributi o campi. Un particolare campo è identificato utilizzando il nome del campo seguito dal nome del suo oggetto fra parentesi quadre. Per esempio, noi trattiamo un array come un oggetto con l’attributo lunghezza che indica il numero di elementi contenuti nell’array. Per specificare il numero di elementi di un array A, scriviamo lunghezza[A]. Anche se utilizziamo le parentesi quadre sia per gli indici degli array sia per gli attributi degli oggetti, di solito, è chiaro dal contesto a cosa intendiamo riferirci.
Una variabile che rappresenta un array o un oggetto è trattata come un puntatore ai dati che costituiscono l’array o l’oggetto. Per tutti i campi f di un oggetto x, l’assegnazione y ← x implica che f[y] = f[x]. Inoltre, se poi impostiamo f[x] ← 3, allora non soltanto sarà f[x] = 3, ma anche f[y] = 3. In altre parole, x e y puntano allo stesso oggetto dopo l’assegnazione y ← x.
Un puntatore può non fare riferimento ad alcun oggetto; in questo caso daremo ad esso il valore speciale NIL.

8. I parametri vengono passati a una procedura per valore: la procedura chiamata riceve la sua copia dei parametri e, se viene assegnato un valore a un parametro, la modifica non viene vista dalla procedura chiamante. Quando viene passato un oggetto, viene copiato il puntatore ai dati che costituiscono l’oggetto, ma non vengono copiati i campi dell’oggetto. Per esempio, se x è un parametro di una procedura chiamata, l’assegnazione x ← y all’interno della procedura chiamata non è visibile alla procedura chiamante. L’assegnazione f[x] ← 3, invece, è visibile.

9. Gli operatori booleani “and” e “or” sono operatori cortocircuitati.
Questo significa che, quando valutiamo l’espressione “x and y”, prima dobbiamo valutare x. Se x è FALSE, allora l’intera espressione non può essere TRUE, quindi non occorre valutare y. Se, invece, x è TRUE, dobbiamo valutare y per determinare il valore dell’intera espressione. Analogamente, se abbiamo l’espressione “x or y”, valutiamo y soltanto se x è FALSE. Gli operatori di cortocircuito ci consentono di scrivere espressioni booleane come “x <> NIL and f[x] = y” senza preoccuparci di ciò che accade quando tentiamo di valutare f[x]quando x è NIL.

Esempio:

INSERTION-SORT(A)
1 for j ← 2 to lunghezza[A]
2   do chiave ← A[j]
3     // Inserisce A[j] nella sequenza ordinata A[1 . . j − 1].
4     i ← j − 1
5     while i > 0 and A[i] > chiave
6       do A[i + 1] ← A[i]
7         i ← i − 1
8     A[i + 1] ← chiave

[Vincenzo1968]

Originariamente inviato da cionci

Difficile misurare la bellezza. Per la compattezza qualcosa si può fare, ma dipende sempre troppo dal linguaggio usato, senza contare che compattezza e leggibilità, oltre un certo limite, non vanno quasi mai di pari passo

E se utilizzassimo, come abbiamo fatto per il contest sul lotto, il criterio proposto da Repne?

Per la bellezza si potrebbe organizzare una sfilata in passerella in un Grand Hotel. Ogni programmatore sfila mentre il proprio codice viene mostrato su un grande schermo. Alla fine, chi perde, dovrà sfilare con indosso il sambenito.

[cionci]

Originariamente inviato da Vincenzo1968

E se utilizzassimo, come abbiamo fatto per il contest sul lotto, il criterio proposto da Repne?

Cioè ?

[Vincenzo1968]

Originariamente inviato da cionci

Cioè ?

Praticamente è simile al tuo.

Si prendono due tempi. Un tempo T1 con dimensione dell'input D1. Il secondo tempo, T2, viene preso raddoppiando la dimensione dell'input: D2 = D1 * 2.
Dividendo T2 per T1, si dovrebbe ottenere una misura approssimativa della complessità dell'algoritmo, a prescindere da quale linguaggio venga utilizzato.
Per esempio, se raddoppiando l'input raddoppia anche il tempo di esecuzione, l'algoritmo dovrebbe avere complessità lineare. Se, invece, il tempo quadruplica, la complessità dovrebbe essere quadratica.

Se ho detto minchiate(ché non m'intendo di matematica), ditelo

[cionci]

Ni, dipende da molti fattori, come uso della memoria (se swappa è chiaro che rallenta non proporzionalmente), oppure un algoritmo può rendere meglio su pochi dati e rendere peggio su molti (o anche l'inverso).

Imho anche per questo sarebbe meglio definire una serie di data set iniziale e non cambiarli mai Inutile tirare fuori un data set più grande quando l'algoritmo è stato dimensionato su quello più piccolo. Anche perché un dato algoritmo potrebbe diventare inefficiente.

[Vincenzo1968]

Originariamente inviato da cionci

Ni, dipende da molti fattori, come uso della memoria (se swappa è chiaro che rallenta non proporzionalmente), oppure un algoritmo può rendere meglio su pochi dati e rendere peggio su molti (o anche l'inverso).

Imho anche per questo sarebbe meglio definire una serie di data set iniziale e non cambiarli mai Inutile tirare fuori un data set più grande quando l'algoritmo è stato dimensionato su quello più piccolo. Anche perché un dato algoritmo potrebbe diventare inefficiente.

Aaaaahhhh ho capito(almeno credo).
Col tuo metodo verrebbe misurato il tasso di incremento/decremento rispetto all'algoritmo di partenza(ferma restando la quantità in input). Giusto?

[khelidan1980]

ovviamente se ho capito bene la versione in pseudocodice dovrebbe essere molto generica, "banale" passatemi il termine

[cionci]

Originariamente inviato da khelidan1980

ovviamente se ho capito bene la versione in pseudocodice dovrebbe essere molto generica, "banale" passatemi il termine

Certo, la soluzione più banale...se voglio fare un ordinamento diciamo il Bubble Sort.

[VICIUS]

Originariamente inviato da Vincenzo1968

INSERTION-SORT(A)
1 for j ← 2 to lunghezza[A]
2   do chiave ← A[j]
3     // Inserisce A[j] nella sequenza ordinata A[1 . . j − 1].
4     i ← j − 1
5     while i > 0 and A[i] > chiave
6       do A[i + 1] ← A[i]
7         i ← i − 1
8     A[i + 1] ← chiave

L'unica cosa che mi ha sempre dato fastidio della notazione usata sul cormen sono le freccine che non sono mai riuscito a fare con la tastiera. Non potremmo usare dei semplici "="?