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

Gender: Male
Posts: 376



« on: 26-04-2010, 11:46:29 »

 [Emoticon] Asd Stavolta è andata "male".. comunque ho testato i tre algoritmi sul file di input originale, ottenendo

Arcidiacono Danilo: 12690031 nanosec(s).   yoh
Caruso Daniele:     19282271 nanosec(s). ( )
Vetrano Andrea:    20466252 nanosec(s).

anche in questo caso la dimensione dell'input gioca un ruolo fondamentale...  pc
Adesso però sarei curioso di vedere il file di input su cui sono stati testati gli algoritmi... una volta stilata la classifica potrebbe anche essere pubblicato no?  
« Last Edit: 26-04-2010, 12:04:30 by XDnl » Logged
Riki Chardo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 101


r36tig89tgcj


« Reply #1 on: 26-04-2010, 15:29:24 »

Ecco i miei risultati
Arcidiacono Danilo: 45281637 nanosec(s) 
Caruso Daniele:     55803103 nanosec(s)
Vetrano Andrea:    63232580 nanosec(s)
Logged
XDnl
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 376



« Reply #2 on: 26-04-2010, 15:31:19 »

Ecco i miei risultati
Arcidiacono Danilo: 45281637 nanosec(s)  
Caruso Daniele:     55803103 nanosec(s)
Vetrano Andrea:    63232580 nanosec(s)
Sempre sul file di input originale?
Edit: ho provato a fare generare le permutazioni di 10 elementi, è venuto un file di 40 MB!
Logged
Riki Chardo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 101


r36tig89tgcj


« Reply #3 on: 26-04-2010, 15:37:55 »

si con il file originale.
Ho provato con il seguente file di input
Code:
{5, 3, 7, 0, 4, 6, 9}
[6*****4]

{9, 2, 7, 0, 3, 5, 6, 8}
[**7**83*]

{6, 3, 1, 9, 7, 5, 2, 4}
[*3*5**7*]

{9, 4, 1, 7, 3, 8, 6, 2}
[****93*6]

{0, 3, 6, 1, 7, 5, 9, 2, 4}
[3****4*9*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{5, 2, 9, 4, 0, 1, 7, 3, 8}
[**0*2**3*]

{3, 9, 0, 5, 4}
[**450]

{6, 2, 0, 5, 9}
[2**50]

{5, 2, 9, 7, 4, 1, 6}
[*6**5*7]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{8, 0, 7, 9, 3, 6, 2, 5, 1}
[*70****9*]

{7, 5, 2, 3, 9, 6}
[*65**2]

{8, 6, 4, 3, 2, 0, 1, 7, 9}
[***102***]

{0, 7, 8, 5, 4}
[**758]

{1, 5, 9, 7, 8, 6, 4}
[65***1*]

{0, 1, 6, 7, 3, 9, 8, 2}
[****821*]

{5, 4, 9, 1, 2, 6, 7, 0}
[*56*1***]

{2, 1, 8, 0, 5}
[*8*01]

{2, 3, 6, 9, 7, 5, 1, 0}
[67*1****]

{5, 3, 9, 4, 0, 7}
[409***]

{7, 5, 9, 3, 6, 1, 0, 2}
[*63***7*]

{9, 0, 7, 8, 2, 3, 1, 4, 6}
[*3**0***9]

{5, 3, 0, 1, 9}
[*0*19]

{3, 0, 9, 2, 6}
[032**]

{6, 8, 4, 1, 7, 5, 3, 0, 9}
[****78**3]

{0, 1, 2, 6, 4, 5}
[**0*12]

{9, 4, 8, 5, 6, 3, 7, 2}
[****7*95]

{9, 1, 2, 7, 4}
[*4*97]

{8, 0, 5, 4, 7, 9, 2, 1, 6}
[***75***0]

{0, 9, 6, 2, 1, 4, 8, 7}
[*1**2*9*]

{5, 9, 1, 2, 3, 7, 8, 6, 0}
[*9****3*0]

{7, 5, 8, 0, 2, 6}
[*78*6*]

{9, 5, 1, 8, 3, 2, 6, 7, 0}
[*7*92****]

{9, 8, 4, 7, 1, 5, 3, 0}
[8***01**]

{3, 4, 0, 2, 5, 9, 6}
[05*9***]

{4, 7, 1, 3, 8, 5, 6, 9}
[8**9**3*]

{0, 3, 7, 4, 9}
[**049]

{3, 0, 6, 7, 4, 2, 9}
[***7*02]

{5, 1, 0, 8, 2}
[*1*80]

{2, 3, 8, 9, 6, 4, 0}
[*20*3**]

{0, 8, 5, 1, 3}
[8*5*3]

{5, 8, 2, 1, 3}
[**183]

{6, 2, 3, 1, 4, 7}
[2*1**3]

{9, 0, 5, 8, 3}
[3*0*5]

{4, 0, 5, 6, 7, 3, 1}
[*76**3*]

{4, 7, 1, 8, 6, 5}
[**457*]

{2, 7, 5, 4, 9}
[*572*]

{5, 9, 1, 8, 0, 2, 6, 3}
[0****6*9]

{4, 8, 1, 2, 0, 3, 9, 6, 7}
[***7**24*]

{9, 3, 4, 2, 0, 5, 8}
[824****]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

{2, 3, 7, 0, 5, 6, 1, 8, 9}
[*****279*]

ecco i risultati
Arcidiacono Danilo: 70586024nanosec(s)
Caruso Daniele:    108697228nanosec(s)
Vetrano Andrea:    123463467 nanosec(s)
« Last Edit: 26-04-2010, 15:46:16 by Riki Chardo » Logged
XDnl
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 376



« Reply #4 on: 26-04-2010, 15:39:26 »

Se non sbaglio ho visto una ù in mezzo al file.
L'algoritmo non funziona se non viene rispettato completamente il formato.

edit: http://www.facebook.com/pages/La-u-che-sintromette-sempre-quando-scrivi-una-parolau/54839460794  cry
« Last Edit: 26-04-2010, 15:50:23 by XDnl » Logged
Riki Chardo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 101


r36tig89tgcj


« Reply #5 on: 26-04-2010, 15:46:55 »

ma lol... sistemato...
Logged
peppe89ct
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 288


very normal people


« Reply #6 on: 26-04-2010, 18:00:18 »

scusate ma ve ne siete accorti che qualche persona che è arrivata nei primi tre non ha utilizzato la ricorsione per calcolare le permutazioni(cosa che chiedeva il professore) e quindi il tempo di esecuzione è stato basso?Huh??
 
Logged

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

Posts: 100



« Reply #7 on: 26-04-2010, 18:08:42 »

scusate ma ve ne siete accorti che qualche persona che è arrivata nei primi tre non ha utilizzato la ricorsione per calcolare le permutazioni(cosa che chiedeva il professore) e quindi il tempo di esecuzione è stato basso?Huh??
 
Ma appunto...cioè non ha senso mettere nella consegna di utilizzare la ricorsione e poi anche se non viene usata il codice è valido lo stesso..
Logged
Riki Chardo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 101


r36tig89tgcj


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

chi è che non ha utilizzato la ricorsione?
Logged
Riki Chardo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 101


r36tig89tgcj


« Reply #9 on: 26-04-2010, 18:28:57 »

è vero non riesco a trovare la ricorsione nel codice di danilo...
Logged
XDnl
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 376



« Reply #10 on: 26-04-2010, 18:31:17 »

è vero non riesco a trovare la ricorsione nel codice di danilo...
Guarda bene,  la ricorsione c'è  ok, lol il mio metodo si chiama RecursiveTrace() non per nulla  cry
« Last Edit: 26-04-2010, 18:33:19 by XDnl » Logged
peppe89ct
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 288


very normal people


« Reply #11 on: 26-04-2010, 18:40:30 »

ma infatti non è stato danilo........non mi va di fare nomi no...è che mi sembra ingiusto che chi utilizza la ricorsione perde posizioni!!!
Logged

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

Gender: Male
Posts: 376



« Reply #12 on: 26-04-2010, 19:24:00 »

è che mi sembra ingiusto che chi utilizza la ricorsione perde posizioni!!!
E' vero che il sorgente in questione non presenta un vero metodo ricorsivo (ossia richiamante se stesso), ma nonostante questo credo che non abbia un vantaggio sostanziale. Mi spiego:

  • La soluzione ricorsiva effettua una chiamata a funzione (la ricorsione, appunto) per ogni permutazione.
  • Nella soluzione iterativa, se ci fate caso, viene comunque fatta una chiamata a funzione per ogni permutazione.

E' vero che nel file di testo viene imposto l'uso della ricorsione, ma personalmente credo che "invalidare" la soluzione proposta non sia giusto.

Detto questo, vorrei condividere alcuni miei dubbi considerazioni, riguardanti le prestazioni dell'algoritmo (penso che la "Sfida di programmazione" sia stata creata per incentivare il confronto tra noi studenti, non tanto per vedere chi è il più veloce).

Analizzando il problema, mi sono accorto che per generare le permutazioni ordinate è necessario avere sempre ben ordinato l'array dei simboli.
Per fare ciò bisognerebbe ordinare i simboli ad ogni permutazione (o perlomeno "shiftare" gli elementi), cosa non molto efficiente, dato il numero elevato di permutazioni.

Nella mia soluzione, utilizzo un array di appoggio (LTable) che mi permette di avere i simboli sempre ordinati, al costo di qualche (veloce) operatore bitwise (tipo & >> ecc..).

Esaminando gli altri sorgenti però mi sono accorto che vengono eseguiti 3/4 cicli for (seppur su pochi elementi) ad ogni permutazione (contro un singolo mio ciclo for), eppure la differenza di velocità non è poi tantissima come credevo.

Non so, magari c'è qualche altro fattore che rallenta, sono rimasto sorpreso nel vedere così poca differenza (su input piu' grandi ovviamente)  

edit: ah, oltre a questo ho anche cercato di ridurre l'uso del new (allocare memoria richiede tempo!), mentre in un'altra soluzione viene usata tranquillamente una lista (creando quindi in continuazione nodi col new)  
« Last Edit: 26-04-2010, 20:06:33 by XDnl » Logged
peppe89ct
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 288


very normal people


« Reply #13 on: 26-04-2010, 20:36:11 »

io ordinavo prima i simboli prima di passarli nel metodo che calcolava le permutazioni!!!!e poi penso il fatto che quando si alloca memoria il processore non impiega poi così tanto tempo da evitare la parola chiave new....
fidati impiegano + tempo le iterazioni e non un byte in confronto ad un int!!!
Ma che dico a te che sei il maestro dell'efficienza boh ok ciao Ciao
« Last Edit: 26-04-2010, 20:44:40 by peppe89ct » Logged

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

Gender: Male
Posts: 376



« Reply #14 on: 26-04-2010, 20:41:28 »

io ordinavo prima i simboli prima di passarli nel metodo che calcolava le permutazioni!!!!
Beh anche io ovviamente ordino (senza ordinare in realtà  boh)

e poi penso il fatto che quando si alloca memoria il processore non impiega poi così tanto tempo da evitare la parola chiave new....
Se i new sono tantissimi viene impiegato piu' tempo... ad esempio allocare un array di 10000 byte tutti in una volta non è come allocare 10000 byte singolarmente...

fidati impiegano + tempo le iterazioni e non un bite in confronto ad un int!!!
Beh sicuramente le iterazioni, essendo parecchie, hanno un loro peso, ma in generale non è da sottovalutare l'aspetto "memoria".

Ma che dico a te che sei il maestro dell'efficienza boh ok ciao Ciao
lol ma che dici
Logged
Pages: [1] 2   Go Up
Print
Jump to: