Mer 21 Agosto, 15:28:04 - 2019

Autore Topic: Challenge 2008: Tema 1  (Letto 8059 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline shark

  • Moderatori
  • Professore Ordinario
  • ****
  • Post: 991
  • FeedBack: +1040/-42
  • Andate oltre Vista, è tempo di prendere un Mac!
    • Mostra profilo
    • Andrea Giuliano
Re: Challenge 2008: Tema 1
« Risposta #30 il: Dom 11 Maggio, 15:06:38 - 2008 »
manno scusa eh....basta semplicemente contare il tempo di esecuzione del metodo...non la creazione del visualizzatore...
Shark™
-------------------
Annunci immobiliari

Offline Alexander

  • Studente di Dottorato
  • ***
  • Post: 239
  • FeedBack: +17/-7
    • Mostra profilo
Re: Challenge 2008: Tema 1
« Risposta #31 il: Dom 11 Maggio, 15:26:26 - 2008 »
premettendo ke la misura nn sarà mai precisa (per via di diversi fattori), a me una matrice 300x300 ci impiega circa 300ms..il problema è ke ho un problema di stackOverflow, quindi nn posso testare l'algoritmo su matrici + grandi..cmq c'è da considerare:
1. il pc su quale fate i test (io ho un modesto Centrino!! :asd:)
2. quantità di Ram
3. cos'avete in esecuzione al momento..(il Winamp è come un freno a mano :P)
.:: Ad Astra Per Aspera ::.

Offline axyz

  • Studente di Dottorato
  • ***
  • Post: 116
  • FeedBack: +0/-1
    • Mostra profilo
Re: Challenge 2008: Tema 1
« Risposta #32 il: Dom 11 Maggio, 16:05:59 - 2008 »
allora proporrei come metodo di confronto standardizzato di utilizzare una variabile long time nella classe Tema1 e all'inizio del metodo mettere:

time = System.nanoTime();

e subito prima del return finale mettere:

time = (System.nanoTime() - time)/1000000;

così alla fine time sarà il tempo di esecuzione in millisecondi del metodo

Offline shark

  • Moderatori
  • Professore Ordinario
  • ****
  • Post: 991
  • FeedBack: +1040/-42
  • Andate oltre Vista, è tempo di prendere un Mac!
    • Mostra profilo
    • Andrea Giuliano
Re: Challenge 2008: Tema 1
« Risposta #33 il: Dom 11 Maggio, 16:56:18 - 2008 »
guardate che bisogna calcolare il tempo che impiega il METODO pathFinder e non tutto il main!!!
quindi i calcoli del tempo dovrebbero essere messi subito prima la chiamata al metodo (dal main) e subito dopo...
Shark™
-------------------
Annunci immobiliari

Offline Alexander

  • Studente di Dottorato
  • ***
  • Post: 239
  • FeedBack: +17/-7
    • Mostra profilo
Re: Challenge 2008: Tema 1
« Risposta #34 il: Dom 11 Maggio, 16:56:41 - 2008 »
io lo faccio esattamente così  :P
ma nn è tanto preciso se vogliamo confrontarci seriamente..
per una migliore stima bisogna eseguire n volte l'algoritmo, prendere il tempo e dividerlo per n..
una media insomma! ;)
.:: Ad Astra Per Aspera ::.

Offline shark

  • Moderatori
  • Professore Ordinario
  • ****
  • Post: 991
  • FeedBack: +1040/-42
  • Andate oltre Vista, è tempo di prendere un Mac!
    • Mostra profilo
    • Andrea Giuliano
Re: Challenge 2008: Tema 1
« Risposta #35 il: Dom 11 Maggio, 17:00:19 - 2008 »
si certo...ma occhio e croce anche da una sola chiamata ti accorgi se il tuo algoritmo è veloce...
Shark™
-------------------
Annunci immobiliari

Offline Alexander

  • Studente di Dottorato
  • ***
  • Post: 239
  • FeedBack: +17/-7
    • Mostra profilo
Re: Challenge 2008: Tema 1
« Risposta #36 il: Dom 11 Maggio, 17:06:09 - 2008 »
lo so lo so ;D
infatti la media nn la sto facendo adesso..anke perchè mi basta giusto un'approssimazione per vedere migliorie/rallentamenti ecc... :sisi:
cmq postate qualke risultato!!giusto per vedere in ke "range" siete!
( sempre se nn avete Quad Core o roba simile  :asd: )
.:: Ad Astra Per Aspera ::.

Offline shark

  • Moderatori
  • Professore Ordinario
  • ****
  • Post: 991
  • FeedBack: +1040/-42
  • Andate oltre Vista, è tempo di prendere un Mac!
    • Mostra profilo
    • Andrea Giuliano
Re: Challenge 2008: Tema 1
« Risposta #37 il: Dom 11 Maggio, 17:15:37 - 2008 »
alex te in che range sei?
hai testato con i nanosecondi?
Shark™
-------------------
Annunci immobiliari

Offline axyz

  • Studente di Dottorato
  • ***
  • Post: 116
  • FeedBack: +0/-1
    • Mostra profilo
Re: Challenge 2008: Tema 1
« Risposta #38 il: Dom 11 Maggio, 17:25:55 - 2008 »
io per un 100x100 sto tra i 10 e i 30 ms
per un 1000x1000 tra i 400 e gli 800 ms
e per un 1450x1450 tra 1 e 3 secondi

risultati molto variabili come vedete in base a come capita lungo il giro suppongo

comunque ho netbeans aperto migliaia di applicazioni e compiz fusion con mille effetti, quindi nn so quanto siano attendibili i risultati

Offline Alexander

  • Studente di Dottorato
  • ***
  • Post: 239
  • FeedBack: +17/-7
    • Mostra profilo
Re: Challenge 2008: Tema 1
« Risposta #39 il: Dom 11 Maggio, 17:26:55 - 2008 »
allora..si ho usato nanoTime come funzione di riferimento..
qualke tempo (approssimato):
matrice 100x100 ---> 50 ms
matrice 200x200 ---> 90 ms
matrice 300x300 ---> 160 ms
una precisazione: i percorsi ke faccio calcolare all'algoritmo sono abbastanza lunghi, nel senso ke nn lo faccio partire da (1,1) per farlo arrivare a (1,2)  :asd:
di solito in e out li scrivo da tastiera e metto: in=(1,1) e out(max row-2,max col-2)
es.:
matrice: 300x300
in(1,1) out(298,298)

.:: Ad Astra Per Aspera ::.

Offline Baduel

  • Studente
  • *
  • Post: 6
  • FeedBack: +1/-0
    • Mostra profilo
Re: Challenge 2008: Tema 1
« Risposta #40 il: Dom 11 Maggio, 18:26:48 - 2008 »
Per essere sicuri di non beccare una casella murata (e perdere quindi tempo prezioso incrociando le dita..) ho scritto due cicli per trovarle in automatico (la distanza tra le due caselle dovrebbe essere la maggiore possibile...)

Codice: [Seleziona]
MazeGenerator gen = new MazeGenerator(1000,1000);
        boolean[][] labirinto = gen.generate();
       
        Cell in = new Cell(0,0);
        Cell out = new Cell(0,0);
       
        for(int i=1;i<labirinto.length;i++) {
            for(int j=1;j<labirinto[0].length;j++) {
                if(!labirinto[i][j]) {
                    in = new Cell(i,j);
                    System.out.println("Trovata casella iniziale: " + i + " " + j);
                    i = j = Integer.MAX_VALUE-1;
                }
            }
        }
       
        for(int i=labirinto.length-1;i>0;i--) {
            for(int j=labirinto[0].length-1;j>0;j--) {
                if(!labirinto[i][j]) {
                    out = new Cell(i,j);
                    System.out.println("Trovata casella finale: " + i + " " + j);
                    i = j = 0;
                }
            }
        }

Offline Martino

  • Studente di Dottorato
  • ***
  • Post: 150
  • FeedBack: +1/-3
  • Diventa chi sei!
    • Mostra profilo
Re: Challenge 2008: Tema 1
« Risposta #41 il: Dom 11 Maggio, 20:52:39 - 2008 »
Mamma mia! Tutta la domenica passato su quest'algoritmo... Ma alla fine regà posso dirmi soddisfatto... I miei tempi:

100x100 --> 10ms

300x300 --> 50ms

1000x1000 --> 300ms

Speriamo solo di non essere troppo in ritardo!
Colui che si volge a guardare il suo passato, non merita di avere futuro avanti a sè.

Offline defrenz

  • Direttore di Dipartimento
  • ***
  • Post: 1346
  • FeedBack: +35/-82
    • Mostra profilo
Re: Challenge 2008: Tema 1
« Risposta #42 il: Mar 13 Maggio, 12:55:48 - 2008 »
c'ho passato quell'oretta sopra per correggere gli errori che sapevo essere cavolate e con un altro pochino di tempo mi son testato i tempi

Sempre + o meno usando gli angoli come in e out e guardando tipo una 20ina di tentativi:
100x100: ~5-8ms (ma ho visto anche una volta 13 e una volta 96 °_°)
200x200: ~8-12ms (ma ho visto anche una volta 18)
300x300: ~12-20ms (ma ho visto anche una volta 30)
500x500: ~15-25ms (ma ho visto TRE volte sul 40-45)
1000x1000: ~80-130ms (ho visto sia sui 60 che sui 150)
1500x1500: ~150-250ms

e poi finisce l'heap :P


dopo pranzo lo mando :D

Offline axyz

  • Studente di Dottorato
  • ***
  • Post: 116
  • FeedBack: +0/-1
    • Mostra profilo
Re: Challenge 2008: Tema 1
« Risposta #43 il: Mar 13 Maggio, 13:01:46 - 2008 »
piuttosto come si fa a mandarli? se il link non è attivo

Offline defrenz

  • Direttore di Dipartimento
  • ***
  • Post: 1346
  • FeedBack: +35/-82
    • Mostra profilo
Re: Challenge 2008: Tema 1
« Risposta #44 il: Mar 13 Maggio, 13:36:51 - 2008 »
si in effetti me ne son accorto °_°

cmq da notare anche:
Citazione
Il codice inviato dovrà contenere, tramite opportuni commenti, la descrizione
ad alto livello concettuale dell'approccio/algoritmo utilizzato; è ammesso
l'uso dello pseudo-codice. Dovrà altresì contenere le generalità dello studente
(nome, cognome, matricola, email, consenso sì/no alla pubblicazione del nominativo
reale nelle graduatorie, eventuale nickname, diritto sì/no al bonus 
cfr. sez. 6).
:o ma davvero si deve far sta roba?