Pages: 1 [2]   Go Down
Print
Author Topic: Nella mente del professore  (Read 2765 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
peppe89ct
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 288


very normal people


« Reply #15 on: 26-04-2010, 20:46:33 »

maestro dell'efficienza utilizzavi gli alberi quando ancora il professore non li aveva spiegati!!!!!
Logged

"Real programmers always confuse Halloween and Christmas 'cause 31oct = 25dec"
leviadragon
Apprendista Forumista
**
Offline Offline

Posts: 217


WWW
« Reply #16 on: 26-04-2010, 21:14:52 »

interessante sta sfida   
Logged

www.darkzero.altervista.org <-- se vi piace mettetela come homepage

Link Immagine


--gratuitamente ricevete,gratuitamente date--
XDnl
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 376



« Reply #17 on: 26-04-2010, 22:43:31 »

edit: no, il mio algoritmo chiama meno volte la funzione a parità di input!
« Last Edit: 26-04-2010, 23:01:39 by XDnl » Logged
Riki Chardo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 101


r36tig89tgcj


« Reply #18 on: 26-04-2010, 23:48:18 »

eh no scusa danilo ho sbagliato... i l tuo metodo ricorsivo si certo ke l'ho visto... volevo dire daniele... Sono d'accordo cn te che annullare una soluzione ben valida solo perche non viene utilizzata la ricorsione sia sbagliato. Pero è stato esplicittato ad inizio prova e quindi va rispettato. Anche perche i primi 10 ricordiamoci che verranno esonerati dalla seconda prova. quindi i lprof vuole testarci da tutti i punti di vista.
Logged
XDnl
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 376



« Reply #19 on: 27-04-2010, 14:28:10 »

Ho riflettuto un po' sulle prestazioni degli algoritmi.  
Mi sono reso conto che questo esercizio non può essere ottimizzato più di tanto.
Lasciamo perdere per adesso la parte che si occupa di leggere l'insieme di simboli, acquisire il promemoria ecc.. e concentriamoci sulla parte più dispendiosa, ossia la generazione/scrittura su file delle permutazioni.
Supponiamo che il file di input contenga una sola cassaforte e consideriamo il seguente algoritmo in pseudocodice:
Code:
per ogni i = 0; i < numeroPermutazioni
{
p = GeneraPermutazione(i);
Scrivi(p);
}

Ora, essendo numeroPermutazioni = n! (dove n è il numero di wildcard), il tempo di esecuzione di un qualsiasi algoritmo DEVE essere nell'ordine di O(n!).
Questo perchè dobbiamo necessariamente scrivere TUTTE le permutazioni, una per volta.

L'algoritmo IDEALE è quello che genera una permutazione in tempo costante, ossia GeneraPermutazione(i) è nell'ordine di O(1) (supponiamo che Scrivi() sia ugualmente veloce per tutti gli algoritmi).

A questo proposito ho scritto una piccola routine di test, del tipo:
Code:
for (int i = 0; i < nPermutazioni; i++)
{
// Questa routine stampa sempre la stessa scritta, così simulo che la generazione delle permutazioni avvenga
// in modo costante.
output.write(promemoria, 0, promemoria.length);
}
Suppongo che questa routine sia quella ottimale, nel senso che non è possibile scrivere algoritmi asintoticamente più veloci.
Ovviamente le nostre soluzioni non riescono a generare le permutazioni in O(1), ma bensì in O(n) (anche se io uso un solo ciclo for contro 3/4 cicli di Daniele, il tempo è sempre nell'ordine di O(n)).
Si può dire che per i nostri 3 algoritmi O(n * n!) rappresenta un upperbound, cioè una stima per eccesso del tempo di esecuzione.
Dico questo perchè magari per una certa permutazione, il ciclo for itera n volte, ma per altre potrebbe impiegare meno iterazioni.

Ho fatto alcuni test, confrontando "l'algoritmo ideale" con le prime due soluzioni (il file di input conteneva una sola cassaforte):

8 wildcard
Algoritmo ideale:    31271172 nanosec(s).
Algoritmo Danilo:    32779511 nanosec(s).
Algoritmo Daniele:  56204580 nanosec(s).

2 wildcard
Algoritmo ideale:    6095273 nanosec(s).
Algoritmo Daniele:  6138487 nanosec(s).
Algoritmo Danilo:    6164461 nanosec(s).

Come si vede l'algoritmo ideale è sempre quello più veloce, e in presenza di poche wildcard (quindi quando n è basso) l'algoritmo di daniele risulta essere leggermente più veloce.
Il mio algoritmo però, resta più vicino a quello che ritengo essere ideale (il lowerbound O(n!)) quando ci sono più wildcard.

Spero di non aver detto troppe fesserie  cry
« Last Edit: 27-04-2010, 14:33:21 by XDnl » Logged
Riki Chardo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 101


r36tig89tgcj


« Reply #20 on: 27-04-2010, 14:44:03 »

danilo considera che tu crei sempre e comunque l'array di appoggio di 1024
Logged
XDnl
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 376



« Reply #21 on: 27-04-2010, 14:47:01 »

danilo considera che tu crei sempre e comunque l'array di appoggio di 1024
Si, ma questo non mi permette di abbattere il limite O(n!).
Anche se con quell'array evito di fare ordinamenti, le n! permutazioni devono essere generate comunque.
Ho fatto il test con 10 wildcard:
Ideale: 3556695368 nanosec(s).
Danilo: 3747207688 nanosec(s).
Caruso: 5735037185 nanosec(s).

E il rapporto di velocità è più o meno lo stesso, nonostante l'input più grande.
Questo perchè credo che entrambi i nostri algoritmi siano nell'ordine di O(n * n!), a meno di qualche costante moltiplicativa nascosta dalla notazione O-grande, il cui rapporto dovrebbe essere intorno a 1.5 - 1.7.
Secondo me, con le varie ottimizzazioni, possiamo "lavorare" solo sulla costante "nascosta" e su n, ma non possiamo "intaccare" n!, essendo costretti a generare tutte le permutazioni.
« Last Edit: 27-04-2010, 14:53:35 by XDnl » Logged
Riki Chardo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 101


r36tig89tgcj


« Reply #22 on: 27-04-2010, 14:54:11 »

io intendevo dire che tu danilo, generando sempre e comunque l'array d'appoggio perdi quel poco che ti serve per ragiungere l'algoritmo ideale, piu la costante di cui parli che fa si che la differenza tra il tuo algoritmo e quello ideale aumenti. Infatti con una sola permutazione e con poche wildcard quello di daniele è piu veloci perche tu perdi quel poco a generare l'array tutto qui.
Logged
XDnl
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 376



« Reply #23 on: 27-04-2010, 14:55:48 »

io intendevo dire che tu danilo, generando sempre e comunque l'array d'appoggio perdi quel poco che ti serve per ragiungere l'algoritmo ideale, piu la costante di cui parli che fa si che la differenza tra il tuo algoritmo e quello ideale aumenti. Infatti con una sola permutazione e con poche wildcard quello di daniele è piu veloci perche tu perdi quel poco a generare l'array tutto qui.

Ah ok, avevo capito male.
Beh potrebbe anche essere   pray
edit: anzi no, perchè la simulazione la faccio tantissime volte, ma l'array lo creo una volta sola.

edit2: Comunque credo che questo spieghi il perchè (nonostante la mia "trovata" dell'array) i due algoritmi non differiscono poi cosi' tanto (anche per input grossi). L'ordine dei due algoritmi resta sempre e comunque O(n * n!)
« Last Edit: 27-04-2010, 14:59:06 by XDnl » Logged
Riki Chardo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 101


r36tig89tgcj


« Reply #24 on: 27-04-2010, 14:59:36 »

appunto se fai molte volte le permutazioni ecc... il tempo di creazione dell'array viene ammortizzato dal numero di ricorsioni e iterazioni. Ma se lo usi per una sola cassaforte e in piu per pochi wildcard, ti batte daniele che fa il tuo stesso numero di iterazioni ma non inizializza l'array...
Logged
Pages: 1 [2]   Go Up
Print
Jump to: