Pages: [1] 2   Go Down
Print
Author Topic: La volpe nel sacco  (Read 2702 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
XDnl
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 376



« on: 19-04-2010, 14:52:32 »

Non dovrebbe uscire oggi la classifca? 
Logged
gaernik
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 114


« Reply #1 on: 19-04-2010, 15:08:06 »

eggià, aspettiamo  boh
Logged
Simone Faro
Moderator
Matricola
*****
Offline Offline

Gender: Male
Posts: 67


WWW
« Reply #2 on: 19-04-2010, 16:29:06 »

A causa di esami fuori sede, questa mattina non ho potuto lavorare alla classifica per il 4° esercizio della competizione.
La classifica uscirà in serata.
Logged

________________________________
Simone Faro, Ph.D.
Dipartimento di Matematica e Informatica
Università di Catania
________________________________
R3m
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 486



« Reply #3 on: 19-04-2010, 19:30:49 »

i risultati sono usciti complimenti a tutti, io sono arrivato terzo, dato che non ho commentato il codice (e non lo commenterò mai  nono) se vi interessa la mia soluzione per studio e avete bisogno di aiuto chiedete pure 
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.
Riki Chardo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 101


r36tig89tgcj


« Reply #4 on: 19-04-2010, 23:53:11 »

vedo che java è fortemente influenzato dalla macchina sulla quale gira. Strano il mio tempo... nel netbook mi esegue in 120 ms e quello di Danilo in 80ms la proporzione non quadra, e poi non ha un dual core il prof con linux non puo eseguire in un tempo che è per quasi 4 volte quello del mio portatilino, o ha messo i tempi inproporzione agli altri esercizi per far pesare in modo uguale ogni eser? voi che ne pensate?
Logged
XDnl
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 376



« Reply #5 on: 20-04-2010, 11:24:34 »

vedo che java è fortemente influenzato dalla macchina sulla quale gira. Strano il mio tempo... nel netbook mi esegue in 120 ms e quello di Danilo in 80ms la proporzione non quadra, e poi non ha un dual core il prof con linux non puo eseguire in un tempo che è per quasi 4 volte quello del mio portatilino

Devi tener conto che l'input sul quale vengono testati i nostri algoritmi non è lo stesso che utilizziamo noi (nell'ultimo pdf c'è specificato).
Se mi fai avere il tuo sorgente vedo di testarlo anche sul mio portatile.

, o ha messo i tempi inproporzione agli altri esercizi per far pesare in modo uguale ogni eser? voi che ne pensate?
Non saprei, io credo che per la sfida "Il benefattore" il file di input utilizzato per testare gli algoritmi sia stato ridotto di molto rispetto a quello pubblicato sul sistema.

Edit: Tu che funzione utilizzi per misuare la velocità dell'algoritmo?
Edit2: Ho eseguito dei benchmark per "Il benefattore" e "La volpe nel sacco" ed ecco i risultati:
Code:
--------------------
"Il benefattore"
---------------------
1) Nel mio PC (tempo 2° classificata / mio tempo):
381949178 / 144258483 = 2,6476722204267183372502260404333

Nella classifica (tempo 2° classificata / mio tempo)
243.23 / 145.73 = 1,6690454950936663693131132917038

2) Nel mio PC (tempo 3° classificato / mio tempo):
1932593402 / 144258483 = 13,39674008633516546822414595889

Nella classifica (tempo 3° classificata / mio tempo)
252.34 / 145.73 = 1,731558361353187401358677005421
Code:
--------------------------
"La volpe nel sacco"
--------------------------
1)
Nel mio PC (tempo 2° classificata / mio tempo):
24457842 / 13985025 = 1,7488593692181458381375793035765

Nella classifica (tempo 2° classificata / mio tempo):
278.03 / 191.15 = 1,4545121632226000523149359142035

2)
Nel mio PC (tempo 3° classificato / mio tempo):
28044833 / 13985025 = 2,0053473626253796471582996812662

Nella classifica (tempo 3° classificato / mio tempo):
288.25 / 191.15 = 1,5079780277269160345278577033743

Come vedi ci sono discrepanze più o meno accentuate (un 7.73 volte per il benefattore!) tra i test eseguiti "in casa" e quelli della classifica.

I motivi possono essere più di uno:
  • Oltre che alle differenze hardware bisogna tener conto che Linux magari è più efficiente nella gestione del disco (e della memoria!) rispetto a Windows.
  • Eventuali applicazioni aperte possono falsare i test (ho visto che anche il solo movimento del mouse influisce sui tempi!)
  • I portatili per esempio non "girano" sempre al massimo (alimentazione da batteria e/o profili d'uso).

Confrontare i rapporti dei tempi non penso sia un buon metodo, perchè i file di input sono differenti nei due test.
Anche se un determinato algoritmo risulta essere poco più veloce di un altro (a parità di input), lo scarto di tempo può diventare notevole per un file più grande, soprattutto se si utilizzano strutture dati per accelerare.
« Last Edit: 20-04-2010, 12:38:52 by XDnl » Logged
Riki Chardo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 101


r36tig89tgcj


« Reply #6 on: 20-04-2010, 15:59:37 »

Quote
Devi tener conto che l'input sul quale vengono testati i nostri algoritmi non è lo stesso che utilizziamo noi (nell'ultimo pdf c'è specificato).
Se mi fai avere il tuo sorgente vedo di testarlo anche sul mio portatile.

Ah ecco era quello che credevo, ma non ne ero sicuro perchè era scritto in modo implicito.
si ti do il mio vedi un po che esce fuori
Code:
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.math.*;

public class SS7_003399
{
protected final String nome;
protected final String cognome;
protected final String famiglia;
protected final String soprannome;
protected final String eta;
protected final String nc;
protected final String nr;
protected final String no;
protected final String nf;
protected final String na;
protected final String ac;
protected final String figli;

public static class Builder
{
//Parametri obbligatori
protected final String nome;
protected final String cognome;
protected final String famiglia;

//parametri facoltativi
protected String soprannome="-";
protected String eta="-";
protected String nc="-";
protected String nr="-";
protected String no="-";
protected String nf="-";
protected String na="-";
protected String ac="-";
protected String figli="-";

public Builder(String nome, String cognome, String famiglia)
{
this.nome =nome;
this.cognome = cognome;
this.famiglia=famiglia;
}


public Builder soprannome(String soprannome)
{
    this.soprannome = soprannome;
    return this;
}
public Builder eta(String eta)
{
this.eta=eta;   
return this;
}
public Builder nc(String nc)
{
this.nc=nc;
return this;
}
public Builder nr(String nr)
{
this.nr=nr;     
return this;
}
public Builder no(String no)
{
this.no=no;
return this;
}
public Builder nf(String nf)
{
this.nf=nf;
return this;
}
public Builder na(String na)
{
this.na=na;
return this;
}
public Builder ac(String ac)
{
this.ac=ac;
return this;
}
public Builder figli(String figli)
{
this.figli=figli;     
return this;
}

public SS7_003399 build()
{
return new SS7_003399(this);
}
public  void tostring()
{
System.out.println("nome "+nome+"\ncognome "+cognome+"\nfamiglia "+famiglia+"\nsoprannome "+soprannome+"\netà "+eta+"\nnumero condanne "+nc+"\nnumero rapine "+nr+"\nomicidi "+no+"\nfurti "+nf+"\narresti "+na+"\nanni carcere "+ac+"\nfigli "+figli);
}
}
private SS7_003399(Builder builder)
{
nome=builder.nome;
cognome=builder.cognome;
famiglia=builder.famiglia;
soprannome=builder.soprannome;
eta=builder.eta;
nc=builder.nc;
nr=builder.nr;
no=builder.no;
nf=builder.nf;
na=builder.na;
ac=builder.ac;
figli=builder.figli;
   
}
public static class nodo
{
protected  nodo next;
protected  SS7_003399 info;
public nodo(nodo next, SS7_003399 info)
{
this.next=next;
this.info=info;
}
}
public static class nodo2
{
protected  nodo2 next;
protected  SS7_003399 info;
public nodo2(nodo2 next, SS7_003399 info)
{
this.next=next;
this.info=info;
}
}
public static class lista
{
protected static nodo head;
public lista()
{
head=null;
}
public void insert(SS7_003399 p)
{
if (head==null)
{
head=new nodo(null,p);
}
else
{
nodo aux2 =head;
for( ;aux2.next!=null;aux2=aux2.next);
aux2.next=new nodo(null, p);
}
}
}
public static class lista2
{
protected static nodo2 head;
public lista2()
{
head=null;
}
public void insertord(SS7_003399 p)
{
if (head==null)
{
head=new nodo2(null,p);
}
else
{
if(head.info.nome.compareTo(p.nome)>0||(head.info.cognome.compareTo(p.cognome)>0&&head.info.nome.compareTo(p.nome)==0))
{

head=new nodo2(head,p);
}
else
{
nodo2 aux2 =head;
for(; aux2.next!=null&&aux2.next.info.nome.compareTo(p.nome)<0;aux2=aux2.next);
for(; aux2.next!=null&&aux2.next.info.cognome.compareTo(p.cognome)<=0&&aux2.next.info.nome.compareTo(p.nome)<=0;aux2=aux2.next);
aux2.next=new nodo2(aux2.next, p);
}
}
}
public void printlist(short g)throws Exception
{
short j=(short)Math.floor(((double)(g))/3);
BufferedWriter w=new BufferedWriter(new FileWriter("SS7_003399.txt"));
nodo2 aux2=head;
w.write("LISTA DI FAZIO:\n");
short k=0;
while(k<j)
{
w.write(aux2.info.nome+" "+aux2.info.cognome);
if(aux2.info.soprannome.charAt(0)!='-')
w.write(" detto "+aux2.info.soprannome);
w.write(" ("+aux2.info.eta+", "+aux2.info.nc+", "+aux2.info.nf+", "+aux2.info.nr+", "+aux2.info.no+", "+aux2.info.na+", "+aux2.info.figli+", "+aux2.info.ac+")\n");
aux2=aux2.next;k++;
}
w.write("\nLISTA DI GALLO:\n");
k=0;
while(k<j)
{
w.write(aux2.info.nome+" "+aux2.info.cognome);
if(aux2.info.soprannome.charAt(0)!='-')
w.write(" detto "+aux2.info.soprannome);
w.write(" ("+aux2.info.eta+", "+aux2.info.nc+", "+aux2.info.nf+", "+aux2.info.nr+", "+aux2.info.no+", "+aux2.info.na+", "+aux2.info.figli+", "+aux2.info.ac+")\n");
aux2=aux2.next;
k++;
}
w.write("\nLISTA DI GALLUZZO:\n");
k=0;
int uu=g-2*j;
while(k<uu)
{
w.write(aux2.info.nome+" "+aux2.info.cognome);
if(aux2.info.soprannome.charAt(0)!='-')
w.write(" detto "+aux2.info.soprannome);
w.write(" ("+aux2.info.eta+", "+aux2.info.nc+", "+aux2.info.nf+", "+aux2.info.nr+", "+aux2.info.no+", "+aux2.info.na+", "+aux2.info.figli+", "+aux2.info.ac+")\n");
aux2=aux2.next;
k++;
}
w.close();
}
}

public static void main(String args[])throws Exception
{
short g=0;
String family="";

lista l= new lista();
lista2 o= new lista2();
BufferedReader b=new BufferedReader(new FileReader("input.txt"));
b.skip(11);
String preg=b.readLine();
String S[]=preg.split(" ");
char a;
lo: while(b.read()!=-1)
{
try
{
String nome="";

while ((a=((char)b.read()))!=' ')
{
nome+=a;
}
String cognome="";
while ((a=((char)b.read()))!=',')
{
cognome+=a;
}
b.skip(1);
b.skip(31);
String famiglia="";
while ((a=((char)b.read()))!=';')
{
famiglia+=a;
}
b.skip(31);
a=' ';
SS7_003399.Builder p=new SS7_003399.Builder(nome,cognome,famiglia);
if(nome.compareTo(S[0])==0&&cognome.compareTo(S[1])==0)
{
family=famiglia;
while (a!=';')
{
if((a=((char)b.read()))==';')
break;
String parametro="";
while ((a=((char)b.read()))!=' ')
{
parametro+=a;
}
String nomeparametro="";
while ((a=((char)b.read()))!=',')
{
if(a==';')
break;
else
nomeparametro+=a;
}
if(parametro.compareTo("detto")==0)p.soprannome(nomeparametro);
else{
if(parametro.compareTo("di")==0) {String []lol=nomeparametro.split(" "); p.eta(lol[lol.length-1]);}
else
{
if(parametro.compareTo("condanne")==0)  p.nc(nomeparametro);
else
{
if(parametro.compareTo("rapine")==0)  p.nr(nomeparametro);
else
{
if(parametro.compareTo("omicidi")==0)  p.no(nomeparametro);
else
{
if(parametro.compareTo("furti")==0)  p.nf(nomeparametro);
else
{
if(parametro.compareTo("arresti")==0)  p.na(nomeparametro);
else
{
if(parametro.compareTo("anni")==0)  {String[] lmao=nomeparametro.split(" ");p.ac(lmao[lmao.length-1]);}
else
p.figli(nomeparametro);
}
}
}
}
}
}
}
}
o.insertord(p.build());
g++;
b.skip(1);







while(b.read()!=-1)
{
try
{
nome="";

while ((a=((char)b.read()))!=' ')
{
nome+=a;
}
cognome="";
while ((a=((char)b.read()))!=',')
{
cognome+=a;
}
b.skip(1);
b.skip(31);
famiglia="";
while ((a=((char)b.read()))!=';')
{
famiglia+=a;
}
b.skip(31);
a=' ';
if(famiglia.compareTo(family)==0)
{


p=new SS7_003399.Builder(nome,cognome,famiglia);
while (a!=';')
{
if((a=((char)b.read()))==';')
break;
String parametro="";
while ((a=((char)b.read()))!=' ')
{
parametro+=a;
}
String nomeparametro="";
while ((a=((char)b.read()))!=',')
{
if(a==';')
break;
else
nomeparametro+=a;
}
if(parametro.compareTo("detto")==0)p.soprannome(nomeparametro);
else{
if(parametro.compareTo("di")==0) {String []lol=nomeparametro.split(" "); p.eta(lol[lol.length-1]);}
else
{
if(parametro.compareTo("condanne")==0)  p.nc(nomeparametro);
else
{
if(parametro.compareTo("rapine")==0)  p.nr(nomeparametro);
else
{
if(parametro.compareTo("omicidi")==0)  p.no(nomeparametro);
else
{
if(parametro.compareTo("furti")==0)  p.nf(nomeparametro);
else
{
if(parametro.compareTo("arresti")==0)  p.na(nomeparametro);
else
{
if(parametro.compareTo("anni")==0)  {String[] lmao=nomeparametro.split(" ");p.ac(lmao[lmao.length-1]);}
else
p.figli(nomeparametro);
}
}
}
}
}
}
}
}
o.insertord(p.build());
g++;
b.skip(1);
}
else
{
while(b.read()!=';');
b.skip(1);

}
}
catch(Exception e)
{
System.out.println("lol");
}

}
















break lo;
}
else{
while (a!=';')
{
if((a=((char)b.read()))==';')
break;
String parametro="";
while ((a=((char)b.read()))!=' ')
{
parametro+=a;
}
String nomeparametro="";
while ((a=((char)b.read()))!=',')
{
if(a==';')
break;
else
nomeparametro+=a;
}
if(parametro.compareTo("detto")==0)p.soprannome(nomeparametro);
else{
if(parametro.compareTo("di")==0) {String []lol=nomeparametro.split(" "); p.eta(lol[lol.length-1]);}
else
{
if(parametro.compareTo("condanne")==0)  p.nc(nomeparametro);
else
{
if(parametro.compareTo("rapine")==0)  p.nr(nomeparametro);
else
{
if(parametro.compareTo("omicidi")==0)  p.no(nomeparametro);
else
{
if(parametro.compareTo("furti")==0)  p.nf(nomeparametro);
else
{
if(parametro.compareTo("arresti")==0)  p.na(nomeparametro);
else
{
if(parametro.compareTo("anni")==0)  {String[] lmao=nomeparametro.split(" ");p.ac(lmao[lmao.length-1]);}
else
p.figli(nomeparametro);
}
}
}
}
}
}
}
}
l.insert(p.build());
b.skip(1);
}
}
catch(Exception e)
{
System.out.println("lol");
}
}





























































for(nodo aaa=l.head;aaa!=null;aaa=aaa.next)
{
if(aaa.info.famiglia.compareTo(family)==0)
{
g++;
o.insertord(aaa.info);
}
}

o.printlist(g);


}
}


Quote
Non saprei, io credo che per la sfida "Il benefattore" il file di input utilizzato per testare gli algoritmi sia stato ridotto di molto rispetto a quello pubblicato sul sistema.

Esatto e quello che credo anch'io i risultati sono troppo bassi. Comunque testando dal mio portatile e dal fisso rispettivamente con un intel atom  windows 7 e un dual core con l'xp a volte ci sononotevoli differenze sul rapporto dei tempi diesecuzione didue programmi a parità diinput. Utilizzando il System.nanoTime() di java. Ho notato anche una cosa se racchiudo il codice dentro due nanoTime() ed eseguo piu volte houna media ben piu alta di come se racchiudo racchiudo sempre il blocco dentro i nanoTime() pero lo ciclo dentro un for avro una media piu bassa.

Quote
I motivi possono essere più di uno:
Oltre che alle differenze hardware bisogna tener conto che Linux magari è più efficiente nella gestione del disco (e della memoria!) rispetto a Windows.
Eventuali applicazioni aperte possono falsare i test (ho visto che anche il solo movimento del mouse influisce sui tempi!)
I portatili per esempio non "girano" sempre al massimo (alimentazione da batteria e/o profili d'uso).

si siamo d'accordo per le differenze hardware e software, poi penso che il test venga effettuato col pc attaccato alla corrente e contutte le applicazioni chiuse.
Quote
Confrontare i rapporti dei tempi non penso sia un buon metodo, perchè i file di input sono differenti nei due test.
Anche se un determinato algoritmo risulta essere poco più veloce di un altro (a parità di input), lo scarto di tempo può diventare notevole per un file più grande, soprattutto se si utilizzano strutture dati per accelerare.

si certo, bisognerebbe valutare il caso migliore, il caso peggiore, ed il caso medio. Con un input diverso puo cambiiare proprio tutto. Comunque utilizzare un input molto piu corto per il benefattore credo sia stata una cosa giusta  perche bisogna cercare di dare lo stesso peso piu o meno a tutti gli esercizi non possiamo mica conteggiare 2 secondi per un esercizio e poi 100 200 ms per gli altri, altrimenti un esercizio solo avrebbe il peso degli altri 10 messi insieme non pensi?
Logged
XDnl
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 376



« Reply #7 on: 20-04-2010, 16:14:50 »

Comunque utilizzare un input molto piu corto per il benefattore credo sia stata una cosa giusta  perche bisogna cercare di dare lo stesso peso piu o meno a tutti gli esercizi non possiamo mica conteggiare 2 secondi per un esercizio e poi 100 200 ms per gli altri, altrimenti un esercizio solo avrebbe il peso degli altri 10 messi insieme non pensi?
Si lo penso anch'io, non fraintendermi. Volevo solo dire che confrontare due algoritmi non è semplice, il test deve essere fatto sullo stesso file di input quantomeno.  ok
Comunque ho testato il tuo algoritmo ottenendo il seguente risultato:
La volpe nel sacco:

1) Tuo tempo / mio tempo
40192978 / 13985025 = 2,8740011548066592658933394827682

Classifica:
434.65 / 191.15 = 2,2738686895108553492021972273084

quindi più o meno siamo là...
Logged
R3m
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 486



« Reply #8 on: 20-04-2010, 16:20:40 »

Io sul mio portatile ottengo i seguenti risultati

Ricki   13,9 ms
Mio 7,9 ms ( lo stò ottimizzando comunque)
Danilo 4,7 ms

Direi quasi il doppio tra il mio e quello tuo...quindi siamo li anche con i risultati sul pc del prof
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.
Simone Faro
Moderator
Matricola
*****
Offline Offline

Gender: Male
Posts: 67


WWW
« Reply #9 on: 20-04-2010, 16:27:42 »

Bene ragazzi,
complimenti per la passione e l'interesse con cui affrontate la competizione e l'analisi delle varie soluzioni.
Di certo da discussioni come queste possono uscir fuori degli spunti interessanti.
Alcune osservazioni:
In genere la differenza nel tempo di esecuzione di due algoritmi diventa più sensibile (e più significativa) quando la dimensione dell'input aumenta (ricordate quello spiegato a lezione sull'andamento ASINTOTICO delle prestazioni di un algoritmo).
Questo significa che se un algoritmo è più veloce di un'altro su di un dato input, la differenza nel tempo di esecuzione sarà maggiore se il confronto viene fatto su di un input più grande.
Questo giustifica i rapporti sui tempi che avete ottenuto sull'esercizio "Il Benefattore" (in effetti il mio input era molto più piccolo di quello dato nell'esercizio).
facendo un paio di conti matematici, se un l'algoritmo  ALGO1 ha un tempo di esecuzione proporzionale a n, mentre l'algoritmo ALGO2 ha un tempo di esecuzione proporzionale a (n^2)/8, allora avremo che:
- per input n=2 si avrà T(ALGO1) = 2 e T(ALGO2)=1/2
- per input n=4 si avrà T(ALGO1) = 4 e T(ALGO2)=2
- per input n=8 si avrà T(ALGO1) = 8 e T(ALGO2)=8
- per input n=16 si avrà T(ALGO1) = 16 e T(ALGO2)=32
E' chiaro che i rapporti tra i tempi di esecuizione non saranno gli stessi.

Inoltre vi faccio riflettere anche sul fatto che il tempo di esecuzione di una soluzione ad un esercizio dipende anche dalla struttura dell'input e non solo dalla sua dimensione.
Per fare un'esempio, il tempo di esecuzione all'ultimo esercizio, "La volpe nel sacco", può dipendere anche dalla posizione in cui si trova il ricercato all'interno del file di input. Chi ha impostato la sua soluzione su una doppia lettura del file impiegherà più tempo per la ricerca della famiglia di appartenenza.

Ciao a tutti
« Last Edit: 20-04-2010, 16:42:41 by Simone Faro » Logged

________________________________
Simone Faro, Ph.D.
Dipartimento di Matematica e Informatica
Università di Catania
________________________________
R3m
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 486



« Reply #10 on: 20-04-2010, 16:35:24 »

Mi ha fatto venire uno spunto, ho calcolato i cosidetti casi migliori e casi peggiori, spostando rispettivamente all'inizio e alla fine il ricercato , ottenendo

Caso Migliore
Mio 7ms
Danilo 4,5
Riki 9,9

Caso Peggiore
Mio 7ms
Danilo 5,7ms
Riki 23,8ms

La cosa curiosa è che il mio rimane uguale sempre...non capisco come, l'ho eseguito piu di una volta....

EDIT
Credo di aver capito, il mio algoritmo legge sempre e comunque tutto il file di input 1 e 1 sola volta,mentre quello di Danilo legge il file finchè non trova il colpevole,dopodiche lo rilegge per ottenere le info sulla famiglia del ricercato. La differenza però si vedrebbe solo con un input enorme, con il ricercato alla fine...
« Last Edit: 20-04-2010, 16:41:11 by R3m » 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.
Riki Chardo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 101


r36tig89tgcj


« Reply #11 on: 20-04-2010, 16:40:39 »

Mi ha fatto venire uno spunto, ho calcolato i cosidetti casi migliori e casi peggiori, spostando rispettivamente all'inizio e alla fine il ricercato , ottenendo

Caso Migliore
Mio 7ms
Danilo 4,5
Riki 9,9

Caso Peggiore
Mio 7ms
Danilo 5,7ms
Riki 23,8ms

La cosa curiosa è che il mio rimane uguale sempre...non capisco come, l'ho eseguito piu di una volta....
esatto io ho fatto un algoritmo che andava bene nel caso che il ricercato si trovasse all'inizio del file... infatti hai visto il mio caso peggiore XD... ora che so che l'input non ha lo stesso caso di quello che ci da il prof. la prossima sfida realizzero un'algoritmo tentando di ottimizzare anche il caso peggiore.
Si davvero molto strano che il tuo resta uguale in ogni caso...

« Last Edit: 20-04-2010, 16:42:24 by Riki Chardo » Logged
XDnl
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 376



« Reply #12 on: 20-04-2010, 16:45:18 »

EDIT
Credo di aver capito, il mio algoritmo legge sempre e comunque tutto il file di input 1 e 1 sola volta,mentre quello di Danilo legge il file finchè non trova il colpevole,dopodiche lo rilegge per ottenere le info sulla famiglia del ricercato. La differenza però si vedrebbe solo con un input enorme, con il ricercato alla fine...
Si io leggo il file due volte, ma in compenso evito di ordinare dei ricercati che non mi interessano...
sono un dilemma questi esercizi  
Edit: Oltretutto c'è da dire che in generale la lettura/scrittura occupa una bella percentuale del tempo di esecuzione, più di quanto mi aspettavo...
Logged
Riki Chardo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 101


r36tig89tgcj


« Reply #13 on: 20-04-2010, 16:45:39 »

Quote
Credo di aver capito, il mio algoritmo legge sempre e comunque tutto il file di input 1 e 1 sola volta,mentre quello di Danilo legge il file finchè non trova il colpevole,dopodiche lo rilegge per ottenere le info sulla famiglia del ricercato. La differenza però si vedrebbe solo con un input enorme, con il ricercato alla fine...
Esatto il mio legge una sola volta ma inserisce tutti gli elementi letti in una lista finche non trovail ricercato dopodiche continua inserendo ordinatamente in un'altra lista solo quelli della famiglia di appartenenza e poi ri inserisce i restanti dell'altra lista in modo ordinato in quella di prima... Forse non mi sono spiegato bene. Tu invece com'è che fai?
Logged
R3m
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 486



« Reply #14 on: 20-04-2010, 16:46:36 »

Ho editato il post precedente e gli ho scritto una possibile soluzione xD

Ho provato anche quello di MariaCristina

Caso Migliore 7,8ms
Caso Peggiore 9ms
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: