ornati

.primate.

User info:

Registered: Apr 2005
Posts: 78 (0.01 al dì)
Location:
Corso: Informatica
Anno: 3
Time Online: 21:49:35 [...]
Status: Offline

Post actions:

Questi sono i sorgenti del mio progetto Mappe.

Il programma in generale è corretto (o almeno sembra però voglio chiarire una cosa. La funzione per l'inserimento nella tabella a doppio hash NON funziona sempre correttamente: è infatti possibile, in certe condizioni, che inserendo una chiave già presente non avvenga la sovrascrittura... PERO' questo non avviene mai per come la hash table viene utilizzata.

Diciamo che è un BUG latente...

Probabilmente era meglio implementare la hash table in modo + semplice (risoluzione collisioni mediante liste).

Per quanto riguarda MapTree si può migliorare in 2 modi:
- implementando il "ricompattamento" dell'albero
- sbarazzandosi dell'allocazione dinamica per la gestione delle stringhe (non entro nei dettagli altrimenti mi dilungo).

COMPILAZIONE (se usate un sistema operativo serio):

mkdir mappe
cd mappe
tar xf ../ornati.tar
make


Per i Windowsiani: non conosco tale sistema(?) operativo(?)

Attachment: ornati.tar
This has been downloaded 236 time(s).

maynard80

.novellino.

User info:

Registered: Jul 2007
Posts: 3 (0.00 al dì)
Location: Milano (e non interland, tendo a precisare)
Corso: informatica
Anno: SESTO
Time Online: 12 Days, 14:28:38 [...]
Status: Offline

Post actions:

beh direi che visto i tempi di esecuzione sei un mago, spero che parteciperai alla discussione del nuovo progetto

__________________
msn Messenger: giamma80 at tiscali.it
ATHENA !

ornati

.primate.

User info:

Registered: Apr 2005
Posts: 78 (0.01 al dì)
Location:
Corso: Informatica
Anno: 3
Time Online: 21:49:35 [...]
Status: Offline

Post actions:

Originally posted by maynard80
beh direi che visto i tempi di esecuzione sei un mago, spero che parteciperai alla discussione del nuovo progetto

No. Se fossi stato un mago avrei chiamato la funzione "hash_get(key)" con il nome "accio_valore(key)" (per chi non l'ha capita: leggi "Harry Potter e il Calice di Fuoco").

A parte gli scherzi: ho solo speso un po' di tempo a pensare alle strutture dati invece di iniziare subito a programmare.


Perchè dovrei partecipare alla discussione del nuovo progetto dato che ho appena passato l'esame?

Forse dovrei sviluppare la mia versione e metterla nella sezione Filez in tempo utile ??
Ho sentito dire che è simile...

:-)

darkAntAreS

...bloup will rule you...

User info:

Registered: Jun 2004
Posts: 267 (0.04 al dì)
Location: gorgonzola(MI)
Corso: informatica
Anno: x
Time Online: 3 Days, 14:49:45 [...]
Status: Offline

Post actions:

non so quanto sia riutilizzabile, ma io un'occhiata gliela darò...al limite mi faccio un'idea

__________________
"Ash nazg durbatulûk, ash nazg gimbatul, ash nazg thrakatulûk agh burzum-ishi krimpatul"

ornati

.primate.

User info:

Registered: Apr 2005
Posts: 78 (0.01 al dì)
Location:
Corso: Informatica
Anno: 3
Time Online: 21:49:35 [...]
Status: Offline

Post actions:

Per aiutare la comprensione del mio codice allego la relazione.

PS: mi sono accorto che nell'analisi della complessità computazionale delle varie operazioni non tengo conto della gestione delle stringhe (pezzi di specifica) associate ad ogni nodo dell'albero....

Attachment: mappe-relazione.pdf
This has been downloaded 147 time(s).

tyzer

.illuminato.

User info:

Registered: Sep 2004
Posts: 227 (0.03 al dì)
Location: Novara
Corso: Ticom
Anno: Laureato ^_^
Time Online: 3 Days, 18:31:58 [...]
Status: Offline

Post actions:

Scusate la mia enorme ignoranza in materia...ma le tabelle hash quando mai le ha spiegate Goldwurm o Aguzzoli??
Nei lucidi delle lezioni non le ho viste...

ornati

.primate.

User info:

Registered: Apr 2005
Posts: 78 (0.01 al dì)
Location:
Corso: Informatica
Anno: 3
Time Online: 21:49:35 [...]
Status: Offline

Post actions:

Originally posted by tyzer
Scusate la mia enorme ignoranza in materia...ma le tabelle hash quando mai le ha spiegate Goldwurm o Aguzzoli??
Nei lucidi delle lezioni non le ho viste...

Io sono (ero) con Torelli e cmq il concetto di tabella di hash è abbastanza semplice (la mia implementazione un po' meno...

Inoltre non è obbligatorio usarle...

MaurizioL

User info:

Registered: Feb 2006
Posts: 17 (0.00 al dì)
Location: Omegna
Corso: Informatica
Anno: 2
Time Online: 3:44:01: [...]
Status: Offline

Post actions:

Per chi me l'aveva chiesta questa è la mia funzione hash basata su xor e shift

unsigned int hash1(int x,int y){
unsigned int hash=0xF4DB98A1;
hash^=x;
hash= ((hash & 0x000000FF) << 16) |
((hash & 0x00FF0000) >> 8 ) |
((hash & 0x0000FF00) << 16) |
((hash & 0xFF000000) >> 24);
hash^=y;
return hash;
}

__________________
Maurizio Lombardi
Linux 2.6.14.2
-----------------------

tyzer

.illuminato.

User info:

Registered: Sep 2004
Posts: 227 (0.03 al dì)
Location: Novara
Corso: Ticom
Anno: Laureato ^_^
Time Online: 3 Days, 18:31:58 [...]
Status: Offline

Post actions:

Noi eravamo con Goldwurm ed Aguzzoli...e di hash manco a parlarne, so che non sono obbligatorie ma allora che struttura dati si deve usare per il Piano?Qualcuno pensava una lista di liste o che altro...boh...la matrice l'ha esclusa il Prof per primo nel testo dell'esercizio...

Simeon

User info:

Registered: Aug 2004
Posts: 984 (0.13 al dì)
Location: Milano
Corso: Informatica
Anno: IT IS OVER!
Time Online: 14 Days, 19:29:42 [...]
Status: Offline

Post actions:

Originally posted by tyzer
Noi eravamo con Goldwurm ed Aguzzoli...e di hash manco a parlarne, so che non sono obbligatorie ma allora che struttura dati si deve usare per il Piano?Qualcuno pensava una lista di liste o che altro...boh...la matrice l'ha esclusa il Prof per primo nel testo dell'esercizio...

No no che lista di liste, è sbagliato

Leggi nell'altro thread le possibili alternative.

MaurizioL

User info:

Registered: Feb 2006
Posts: 17 (0.00 al dì)
Location: Omegna
Corso: Informatica
Anno: 2
Time Online: 3:44:01: [...]
Status: Offline

Post actions:

Originally posted by tyzer
Noi eravamo con Goldwurm ed Aguzzoli...e di hash manco a parlarne, so che non sono obbligatorie ma allora che struttura dati si deve usare per il Piano?Qualcuno pensava una lista di liste o che altro...boh...la matrice l'ha esclusa il Prof per primo nel testo dell'esercizio...

__________________
Maurizio Lombardi
Linux 2.6.14.2
-----------------------

gighen991

User info:

Registered: Feb 2013
Posts: 6 (0.00 al dì)
Location:
Corso: informatica
Anno: 2
Time Online: 3:04:54 [...]
Status: Offline

Post actions:

Scusate.. sto provando a far funzionare il programma di ornati.. ma c'è qualcosa che non quadra.. io faccio ./mappe nella shell di linux e lui parte.. poi faccio
c 10
v 2 3 25
v 3 4 20
v 4 5 40
m prima 1 0 NWWSEENESSWNNNEN
m seconda 2 1 NNEEEESSWWNNNEEESSWWWWNN
l

ma quando faccio l non stampa niente.. come mai?.. sono io che sbaglio qualcosa? grazie mille

Cronovirus

dsy core staff

User info:

Registered: Jun 2012
Posts: 471 (0.10 al dì)
Location:
Corso: Magistrale in Informatica
Anno: 2
Time Online: 4 Days, 2:45:03: [...]
Status: Offline

Post actions:

Originally posted by gighen991
Scusate.. sto provando a far funzionare il programma di ornati.. ma c'è qualcosa che non quadra.. io faccio ./mappe nella shell di linux e lui parte.. poi faccio
c 10
v 2 3 25
v 3 4 20
v 4 5 40
m prima 1 0 NWWSEENESSWNNNEN
m seconda 2 1 NNEEEESSWWNNNEEESSWWWWNN
l

ma quando faccio l non stampa niente.. come mai?.. sono io che sbaglio qualcosa? grazie mille

Come avrai visto è un post di 10 anni fa Dubito che ti risponderanno gli autori.. cmq ho appena dato un'occhiata e direi che ti rimane appeso sulla read. Ti consiglio di modificare il makefile e di inserire l'opzione per i simboli di debug così puoi debuggare ad alto livello con gdb. Oppure usa 'strace' e vedrai che per l'input che gli dai tu rimane sulla read.

Prova a leggere meglio il codice, probabilmente non va bene come stai dando gli input

gighen991

User info:

Registered: Feb 2013
Posts: 6 (0.00 al dì)
Location:
Corso: informatica
Anno: 2
Time Online: 3:04:54 [...]
Status: Offline

Post actions:

Originally posted by Cronovirus
Come avrai visto è un post di 10 anni fa Dubito che ti risponderanno gli autori.. cmq ho appena dato un'occhiata e direi che ti rimane appeso sulla read. Ti consiglio di modificare il makefile e di inserire l'opzione per i simboli di debug così puoi debuggare ad alto livello con gdb. Oppure usa 'strace' e vedrai che per l'input che gli dai tu rimane sulla read.

Prova a leggere meglio il codice, probabilmente non va bene come stai dando gli input

Perfetto.. grazie mille .. proverò anche se non sono molto pratico con la hash table.. e essendo il progetto lo stesso di quest'anno volevo farlo con gli alberi o i grafi, ma non trovo sorgenti con quelli.. almeno per capire come strutturare il problema..

Cronovirus

dsy core staff

User info:

Registered: Jun 2012
Posts: 471 (0.10 al dì)
Location:
Corso: Magistrale in Informatica
Anno: 2
Time Online: 4 Days, 2:45:03: [...]
Status: Offline

Post actions:

Beh se il progetto è lo stesso assicurati che nessun altro prenda spunto da questo