[JAVA]Sfruttare le tabelle Hash

[:.Blizzard.:]

Ciao ragazzi :D
Sono agli sgoccioli per la mia tesi della triennale e ho un ultimo problema da affrontare e necessito dei vostri consigli.

Partiamo da questa immagine:

http://img6.imageshack.us/img6/2910/hashi.png

Premessa:

il mio problema è quello di individuare nel minor tempo possibile il bordo della figura evidenziata dai tratti verdi e viola.
Tutti questi punti vengono calcolati all'interno del programma tramite la differenza di punti di funzioni. Ciascuna funzione a sua volta mantiene i propri punti all'interno di un array bidimensionale di dimensione (#punti funzione ) * 2 , ovvero ascissa e ordinata. Iterando queste differenze in un determinato modo ottengo strada facendo i punti della figura di cui devo calcolarne il bordo.

Per risolvere il problema basterebbe conoscere per ogni valore dell'ascissa quali sono i punti di ordinata massima e minima.
E' per questo motivo che ho pensato alle tabelle hash: mano a mano che calcolo i punti della figura, utilizzo come chiave il valore dell'ascissa e faccio in modo che a quell'ordinata siano sempre associati soltanto due elementi, il massimo e il minimo, aggiornando questi due valori ogni volta che viene calcolato un nuovo punto di uguale ascissa.

Può andare come ragionamento? Avete qualche consiglio/idea ?

Per quanto riguarda il codice invece in teoria basta utilizzare il metodo put per l'inserimento:
put(Object key, Object value)
// Maps the specified key to the specified value in this hashtable.

mentre per scorrere gli elementi aventi la stessa chiave cosa devo fare?

[DavideV]

Ciao ragazzi :D
Sono agli sgoccioli per la mia tesi della triennale e ho un ultimo problema da affrontare e necessito dei vostri consigli.

Partiamo da questa immagine:

http://img6.imageshack.us/img6/2910/hashi.png

Premessa:

il mio problema è quello di individuare nel minor tempo possibile il bordo della figura evidenziata dai tratti verdi e viola.
Tutti questi punti vengono calcolati all'interno del programma tramite la differenza di punti di funzioni. Ciascuna funzione a sua volta mantiene i propri punti all'interno di un array bidimensionale di dimensione (#punti funzione ) * 2 , ovvero ascissa e ordinata. Iterando queste differenze in un determinato modo ottengo strada facendo i punti della figura di cui devo calcolarne il bordo.

Per risolvere il problema basterebbe conoscere per ogni valore dell'ascissa quali sono i punti di ordinata massima e minima.
E' per questo motivo che ho pensato alle tabelle hash: mano a mano che calcolo i punti della figura, utilizzo come chiave il valore dell'ascissa e faccio in modo che a quell'ordinata siano sempre associati soltanto due elementi, il massimo e il minimo, aggiornando questi due valori ogni volta che viene calcolato un nuovo punto di uguale ascissa.

Può andare come ragionamento? Avete qualche consiglio/idea ?

Per quanto riguarda il codice invece in teoria basta utilizzare il metodo put per l'inserimento:
put(Object key, Object value)
// Maps the specified key to the specified value in this hashtable.

mentre per scorrere gli elementi aventi la stessa chiave cosa devo fare?
Ho appena iniziato lo studio di Java quindi non saprei darti suggerimenti specifici del linguaggio. Per quanto riguarda il livello di astrazione, invece, direi che effettivamente una tabella di Hash sarebbe il massimo. Aiutato proprio dalla definizione stessa di funzione non corri il rischio di collisione e quindi riesci a implementare la tabella in tempo O(1)

Non capisco bene cosa intendi per "scorrere gli elementi aventi la stessa chiave". Intendi il fatto di leggere i valori min/max di entrambe le funzioni per uno stesso valore sul dominio? Potresti definire la tabella Hash nella classe di ogni funzione e richiamarla con un for ... each applicato alle classi...

spero di esserti stato d'aiuto!

[^TiGeRShArK^]

Dovresti crearti un oggetto che contenga il min e il max e poi mettere quell'oggetto nella mappa usando come chiava l'ascissa....

public class Interval {
double min;
double max;

public Interval(double min, double max) {
this.min = min;
this.max = max;
}
}


........

Map<Double, Interval> map = new HashMap<Double, Interval>();
map.put(x, new Interval(min, max));


Cos' ad occhio dovrebbe andare se non ho scritto qualche minchiata senza usare eclipse. :asd:

[^TiGeRShArK^]

pensandoci alternativamente potresti anche usare semplicemente un array di double in questo modo:

double[] border = new double[xSamples.length * 2];
for (int i = 0; i < xSamples.length; i++) {
border[i] = min;
border[i+1] = max;
}

Che maari è meno leggibile, ma ad occhio sembra + leggero....

ah.. xSamples è il vettore contenente tutti i punti da campionare sull'asse delle ascisse. :p

[:.Blizzard.:]

Ho appena iniziato lo studio di Java quindi non saprei darti suggerimenti specifici del linguaggio. Per quanto riguarda il livello di astrazione, invece, direi che effettivamente una tabella di Hash sarebbe il massimo. Aiutato proprio dalla definizione stessa di funzione non corri il rischio di collisione e quindi riesci a implementare la tabella in tempo O(1)

Non capisco bene cosa intendi per "scorrere gli elementi aventi la stessa chiave". Intendi il fatto di leggere i valori min/max di entrambe le funzioni per uno stesso valore sul dominio? Potresti definire la tabella Hash nella classe di ogni funzione e richiamarla con un for ... each applicato alle classi...

spero di esserti stato d'aiuto!

Sì, in termini di ottimalità la funzione hash è sicuramente la struttura dati più adatta ad una situazione di questo genere. Con "scorrere glie lementi aventi la stessa chiave" intendo una situazione di questo genere:

http://www.di.unipi.it/didadoc/labII/Dispense/parte3/img10.png

Ovvero sfruttare la collisione per ottenere sempre e solo due values, Max e Min appunto, per lo stesso valore key.

Min e Max sono valori ottenuti strada facendo perchè ogni volta che trovo un punto della stessa ordinata devo controllare che la sua ascissa non possa essere un eventuale punto appartenente al bordo.



Dovresti crearti un oggetto che contenga il min e il max e poi mettere quell'oggetto nella mappa usando come chiava l'ascissa....

public class Interval {
double min;
double max;

public Interval(double min, double max) {
this.min = min;
this.max = max;
}
}


........

Map<Double, Interval> map = new HashMap<Double, Interval>();
map.put(x, new Interval(min, max));


Cos' ad occhio dovrebbe andare se non ho scritto qualche minchiata senza usare eclipse. :asd:

Direi che è la soluzione migliore. Era giusto perchè mi sembrava eccessivo creare proprio un oggetto semplicemente per memorizzare due numeri. Credo userò un array di 2 elementi da scandire ogni volta.


pensandoci alternativamente potresti anche usare semplicemente un array di double in questo modo:

double[] border = new double[xSamples.length * 2];
for (int i = 0; i < xSamples.length; i++) {
border[i] = min;
border[i+1] = max;
}


Che maari è meno leggibile, ma ad occhio sembra + leggero....

ah.. xSamples è il vettore contenente tutti i punti da campionare sull'asse delle ascisse. :p

Intendi al posto di usare una tabella hash?

Se non ho capito male così tu avresti sulla cella i di xSamples il valore dell'ascissa e per trovare max e min dovrei leggere semplicemente il contenuto di i ed i+1 in border ? E min e max come faccio a trovarli? E' proprio questo il problema :D


Grazie a tutti e due, se avete altri consigli li accetto più che volentieri.

[^TiGeRShArK^]

ah ok, avevo capito ti servisse solo per memorizzare il valore di min e max, non per trovarli..
Ma a questo punto mi sfugge come fai a trovarli.. :fagiano:
Credevo che bastasse controllare per ogni ascissa campionata il valore + basso e più alto delle ordinate delle varie funzioni e memorizzarti solo max e min a quanto avevo capito.. :fagiano:

[:.Blizzard.:]

ah ok, avevo capito ti servisse solo per memorizzare il valore di min e max, non per trovarli..
Ma a questo punto mi sfugge come fai a trovarli.. :fagiano:
Credevo che bastasse controllare per ogni ascissa campionata il valore + basso e più alto delle ordinate delle varie funzioni e memorizzarti solo max e min a quanto avevo capito.. :fagiano:

No ok, allora mi sono spiegato male io.

Partiamo dal fatto che io ho due array bidimensionali, f2 e f1 contenenti i punti delle due funzioni. I punti della figura che si vede nell'immagine vengono calcolati tramite questo codice:

for (int i = 0; i < dimVectf2; i++) {
for (int j = 0; j < dimVectf1; j++) {
if (f_f_check && whoIsSottraendo.equals("funzione1")) {
g.fillRect(Math.round(larghezza / 2 + (f2[i][0] - f1[j][0]) * ripinPix) - 1, altezza / 2 - (Math.round((f2[i][1] - f1[j][1]) * ripinPix)), 1,1);
}
}
}



Ecco il modo in cui vengono calcolati. Praticamente ogni punto di f2 viene sottratto a sua volta con ogni punto di f1. Ecco perchè i due cicli annidati. E in teoria questo lavoro viene fatto anche con le simmetriche ecc. ecc.
Fatto stà che alla fine la figura risultante (o meglio, quella che ho postato è una parte) è quella dell'immagine.

Quindi in teoria io calcolo i punti strada facendo e non conosco il massimo e il minimo per un dato valore dell'ascissa. Posso quindi usare una tabella hash in modo che ogni volta che calcolo un punto con il codice che ho scritto sopra, controllo che questo faccia parte del bordo semplicemente vedendo i precedenti minimi e massimi salvati all'interno dell'hash_table per il valore key corrispondente all'ascissa del punto calcolato.

[^TiGeRShArK^]

Ma se mentre calcoli i punti li memorizzi direttamente nell'array se sono inferiori al minimo o superiori al massimo non va bene?
Così non hai bisogno di usare la tabella hash e soprattutto non ti serve scorrerti un'altra volta il ciclo...
Praticamente, se ho capito bene come funge la tua funzione per il calcolo verrebbe qualcosa del genere:

for (int i = 0; i < dimVectf2; i++) {
for (int j = 0; j < dimVectf1; j++) {
if (f_f_check && whoIsSottraendo.equals("funzione1")) {
double x = Math.round(larghezza / 2 + (f2[i][0] - f1[j][0]) * ripinPix) - 1;
double y = altezza / 2 - (Math.round((f2[i][1] - f1[j][1]) * ripinPix));
g.fillRect(x, y, 1,1);
if (y < xSamples[2 * i])
xSamples[2 * i] = y;
if (y > xSamples[2 * i + 1])
xSamples[2 * i + 1] = y;
}
}
}

Però dovresti ovviamente inizializzare precedentemente gli indici pari di xSamples, che avrà lunghezza 2 * dimVectf2, con +inf e quelli dispari con -inf....sempre se ho capito bene cosa rappresentano f1 e f2.. :fagiano: