|
|
|
|  |
|
| |
|
| Precedente :: Successivo |
| Autore |
Messaggio |
EvolutionCrazy
Webmaster
Registrato: 23 Apr 2003
Messaggi: 4426
Località: Vicenza
|
 Inviato: 05 Ago 2005 15:56 Oggetto: [JAVA] Dizionario ordinato su skipList a 2 riferimenti |
  |
|
Visto che qualche mese fa quando ho dovuto farlo per l'università (universitò di Padova, corso di Dati e Algoritmi) sul web non ho trovato nulla di già pronto ora lo pubblico fatto 
Il codice l'ho scritto io, io ne sono il proprietario e lo diffondo come voglio 
Qui il link per il download del pacchetto completo di sorgenti e relazione:
http://evcz.hwtweakers.net/varie/progetto_dati_e_algoritmi.zip
| Codice: | Progetto N° 9 (Dizionario Ordinato su skipList a 2 riferimenti)
***********************************************
Linee generali di utilizzo:
Il dizionario è strutturato in modo da accettare oggetti Comparable come chiavi e qualsiasi oggetto Object come "valore"
Gli oggetti restituiti dalle varie funzioni possono essere di tipo Iteratore ed Entry
Le funzionalità di questi oggetti saranno descritte in seguito.
!!! NOTE sul JDK usato/consigliato !!!
Se si compila usando il JDK 1.5.x (java5) si ottiene un warning (dovuto al fatto che java5 usa compareTo con i generics e non come oggetti Comparable che venivano usati fino all’1.4), la compilazione va comunque a buon fine e i class ottenuti sono comunque funzionanti. Per evitare tale warning basta compilare usando il parametro –nowarn)
L’uso del jdk1.4 o precedente produce comunque un applicazione funzionante, ma a livello prestazione risulta di gran lunga più lenta rispetto alla versione compilata ed eseguita su java5.
E’ quindi altamente consigliato (se si è interessati alle prestazioni e ai tempi di esecuzione) l’uso di un jdk della seria 1.5.x !!!
***********************************************
Classe principale: DizionarioOrdinato
***********************************************
DizionarioOrdinato(Comparable key_min, Comparable key_max)
Questo è il costruttore del dizionario…
min_key e max_key sono le due chiavi sentinella che l’utilizzatore deve inserire in fase di creazione del dizionario; rispettivamente rappresentano –infinito e +infinito
Le chiavi sentinella devono essere oggetti dello stesso tipo delle chiavi che verranno utilizzate nel dizionario.
Nella classe di Prova come chiavi sentinella ho usato il carattere unicode più piccolo e una sequenza del carattere unicode più grande come estremi (tale scelta è dovuta al fatto che tale prova è stata fatta usando oggetti String che java tratta come unicode)
boolean isEmpty()
restituisce true se il dizionario è vuoto
int size()
restituisce un intero che rappresenta il numero di definizioni presenti nel dizionario
Entry find(Comparable key)
Restituisce una Entry del tipo (Comparable key, Object value) contenente chiave e una definizione della chiave ricercata
Restituisce null se la chiave cercata non è presente del dizionario
Iteratore findAll(Comparable key)
restituisce un Iteratore per scorrere tutte le definizioni associate alla chiave
oppure se la chiave non esiste restituisce null
Entry insert(Comparable key, Object content)
Inserisce chiave e oggetto associato nel dizionario restituendi l’entry
restituisce null se l’inserimento fallisce (si è tentato di inserire una chiave che esce dal range key_min – key_max)
Iteratore entries()
restituisce un oggetto Iteratore che punta alla chiave più piccola e con il quale si può scorrere l’intero dizionario
Iteratore predecessors(Comparable key)
restituisce un oggetto Iteratore che punta alla chiave minore o uguale a quella passata e con il quale si può scorrere il dizionario in ordine decrescente
Iteratore successors(Comparable key)
restituisce un oggetto Iteratore che punta alla maggiore minore o uguale a quella passata e con il quale si può scorrere il dizionario in ordine crescente
Entry first()
Restituisce una Entry contenente la chiave più piccola presente nel dizionario e una definizione associata a tale chiave.
Restituisce null se il dizionario è vuoto.
Entry last()
Restituisce una Entry contenente la chiave più grande presente nel dizionario e una definizione associata a tale chiave.
Restituisce null se il dizionario è vuoto.
Entry remove (Entry entry)
Rimuove dal dizionario l’Entry passata restituendo l’Entry.
Se la rimozione fallisce(Entry non esistente nel dizionario) restituisce null
***********************************************
Classe Entry
***********************************************
E' un oggetto con due campi (ad accesso amichevole per massimizzare le prestazioni)
Comparable key
Contiene la chiave
Object value
Contiene il riferimento all'oggetto associato alla chiave
L’accesso amichevole permette all’utente la modifica dell’oggetto… per me come è concepito il dizionario tale azione non è assolutamente un problema in quanto l’oggetto Entry viene creato ogni volta da 0 e non viene mai riusato… anche se l’utente lo distrugge/altera al dizionario non succede nulla ;)
***********************************************
Classe Iteratore
***********************************************
L'iteratore è un oggetto che si posiziona esattamente sopra le Entry e permette di scorrerle e di ottenerne il contenuto, a seconda che l’Iteratore sia stato creato con predecessors() o successors() il verso di percorrenza delle chiavi sarà rispettivamente decrescente o crescente (se l’Iteratore viene creato con entries() il verso di percorrenza sarà crescente, se l’Iteratore viene creato con un findAll() non c’è alcun verso: le definizioni vengono lette così come sono memorizzate nella ValuesList di supporto)
boolean hasNext()
restituisce true se c'è una posizione successiva a quella attuale
boolean next()
sposta l'iteratore sulla posizione successiva
restituisce null se lo spostamento fallisce (per esempio quando non ci sono più posizioni successive)
Entry getdata ()
restituisce un Entry contenente chiave e valore corrispondenti alla posizione attuale in cui si trova l’iteratore
Esempio di utilizzo di un Iteratore:
String key = "0chiave";
System.out.println("\r\n > Cerco e stampo tutte le definizioni associate a " + key);
Iteratore entries = dizionario.findAll(key);
if (entries != null)
{
do
{
System.out.println("" + entries.getdata().value);
}while(entries.next());
}
else
System.out.println(key + " non trovata!!!");
***********************************************
Classe ValuesList
***********************************************
Allo scopo di diminuire ulteriormente lo spreco di memoria anziché usare una struttura dati già pronta per contenere tutti le definizioni associate ad una chiave mi sono scritto questa classe dedicata ottimizzandola al massimo in modo da usare meno memoria possibile e dotandola solo dei metodi strettamente necessari a compiere le mie operazioni.
La lista che ho creato è una LinkedList che al suo interno ha tutti i nodi pieni (non esistono nodi vuoti, così da non sprecare spazio e ovviamente la lista non può esistere se vuota!) e non ha alcun campo dedicato alla memorizzazione del numero di elementi contenuti (questa scelta incide leggermente sulle prestazioni in quanto per “misurare” la lista ogni volta viene fatta una scansione lineare… ma le specifiche di progetto si preoccupavano della memoria… quindi il mio scopo era risparmiare memoria dove possibile…)
Questa classe è a solo uso interno e l’utente non dovrà mai interagirvi.
Ulteriori informazioni nei commenti del codice.
***********************************************
Classe SkipList
***********************************************
Questa classe costituisce la struttura dati su cui si appoggia il dizionario.
L'utente finale non dovrà MAI ed in NESSUN CASO interagire con questa classe...
Questa classe è solo di supporto... una descrizione dettagliata delle scelte progettuali e della varie funzionalità che incorpora è disponibile direttamente nel sorgente della classe sotto forma di commenti.
Nelle richieste di progetto c’è il vincolo che la memoria usata sia minore possibile, in tale ottica ho provveduto ad “stringere” al massimo i nodi.
Generalmente le skipList sono costituite da nodi con 5 campi (4puntatori + 1 dato) ed il campo dati contiene a sua volta altri 2 campi: chiave e valore…
Un evidente spreco di memoria… per migliorare il tutto ho provveduto a concepire il singolo nodo con soli 3 campi:
un campo di tipo Nodo che punta al nodo di destra (.r) e che vale “null” quando ci si trova alla chiave sentinella +infinito.
un campo di tipo Object (.d) che può essere usato in due modi: puntatore al nodo sotto se il nodo è a livello > 0 oppure puntatore ad un ValuesList (che contiene tutti i valori associati alla chiave in questione) se il nodo si trova al livello 0.
un campo di tipo Comparable che contiene la chiave (.key)
Visto che il puntatore al nodo inferiore è usato anche per contenere la lista serve un “flag” che mi permetta di sapere quando sono arrivato alla lista base (livello S0) a tale scopo tra le variabili esemplare della lista è previsto un campo “h” che memorizza l’altezza attuale della lista, così da avere un riferimento per sapere se sono arrivato in fondo.
Le scelte possibili per la gestione delle chiavi doppie erano 2:
* inserire le chiavi doppie come se fossero diverse
* inserire le chiavi una sola volta e aggiungere soltanto gli elementi
ovviamente la seconda scelta è quella che più si addice al progetto in quanto diminuisce notevolmente la richiesta di spazio in memoria per contenere chiavi doppie!
Se si fossero inserite tutte le chiavi come diverse ogni nuova "definizione" associata ad una chiave già esistente avrebbe creato una nuova chiave con una nuova torre inserendo svariati nodi per nulla (in un dizionario è frequentissimo l'inserimento di chiavi doppie...)
Nei nodi appartenenti alla lista S0 (la base della SkipList) il puntatore sotto (.d) anziché puntare ad un altro Nodo punta ad una ValuesList che contiene tutti gli oggetti associati alla chiave rappresentata dal nodo in questione.
I metodi di ricerca/inserimento/rimozione sono stati realizzati seguendo gli algoritmi standard per le SkipList e adattati/ottimizzati per ottenere le massime prestazioni usando nodi con due soli riferimenti (destra, sotto)
Questo un esempio di un percorso di ricerca (ricerca della chiave 71)
Per quanto riguarda l’inserimento, anziché procedere dal basso come avviene solitamente per le liste con 4 riferimenti, in questo caso ho fatto prima il conteggio casuale per determinare l’altezza della torre, quindi creo la torre partendo dall’alto e abbassandomi di volta in volta finché non si arriva al nodo sulla lista di base.
***********************************************
Classe Nodo
***********************************************
Classe che costituisce l'elemento base della skipList
Realizzata secondo quanto descritto sopra.
Per massimizzare le prestazioni le variabili interne anche in questo caso godono tutte di accesso "amico"
Questa scelta non mette a repentaglio la robustezza della lista in quanto l'utente del dizionario non avrà MAI accesso ai nodi ;)
Esempio di output classe di Prova eseguito su di una macchina AMD Athlon Barton @ 2400mhz con jdk 1.5 su Win XP
C:\Programmi\Java\jdk1.5.0_01\bin\java.exe Prova
Working Directory - C:\Documents and Settings\EvolutionCrazy\Desktop\507375\
Class Path - c:\programmi\java\jdk1.5.0_01\lib\tools.jar;c:\programmi\java\jdk1.5.0_01\jre\lib\rt.jar
> Popolo il dizionario con 200000 definizioni completamente casuali (anche chiavi duplicate)
Inserimento di 200000 definizioni completato in 5110.0 millisecondi
> Aggiungo 3 definizioni associate a 0chiave
Aggiunte tre definizioni a 0chiave, ora il dizionario contiene 200003 definizioni
> Cerco e stampo tutte le definizioni associate a 0chiave
definizione00
definizione0000
definizione000
> test remove(find(0chiave)) + findAll(0chiave) di verifica
definizione0000
definizione000
> Faccio un find() di 100000 chiavi completamente casuali
chiave "-1638517137chiave" trovata, una definizione e' "definizione-1638517137"
chiave "788118962chiave" trovata, una definizione e' "definizione788118962"
chiave "407568933chiave" trovata, una definizione e' "definizione407568933"
Ricerca di 100000 chiavi casuali completata in 1093.0 millisecondi, 3 chiavi trovate
> Richiedo iteratore su intera lista ordinata (entries()) e faccio uno scan completo
Iteratore ottenuto, 200002 entry rilevate
> Richiedo iteratore di tutte le entry con chiave >= di 99985 e ne faccio una scansione
999859331chiave
999907432chiave
99991084chiave
999948130chiave
999979393chiave
999982300chiave
999997998chiave
Iteratore ottenuto, rilevate 7 entry con chiave >= di 99985
> Richiedo iteratore di tutte le entry con chiave <= di -1000146778chiave e ne faccio una scansione
-1000137538chiave
-1000120615chiave
-1000113578chiave
-1000077758chiave
-1000064297chiave
-1000046856chiave
-1000020068chiave
-1000017025chiave
Iteratore ottenuto, rilevate 8 entry con chiave <= di -1000146778chiave
> La chiave piu' piccola presente nel dizionario e' -1000017025chiave
> La chiave piu' grande presente nel dizionario e' 999997998chiave
Process Exit... |
DizionarioOrdinato.java
| Codice: | import java.util.*;
class DizionarioOrdinato
{
//lista che conterrà i dati
private SkipList skipList;
//costruttore
DizionarioOrdinato(Comparable min, Comparable max)
{
skipList = new SkipList(min, max);
}
//funzione che dice se il dizionario è vuoto oppure no
boolean isEmpty()
{
return skipList.size() == 0;
}
//funzione che dice quante definizioni contiene il dizionario
int size()
{
return skipList.size();
}
//funzione di inserimento
Entry insert(Comparable key, Object value)
{
return skipList.skipInsert(key, value);
}
//funzione di ricerca (restituisce un singolo elemento)
Entry find(Comparable key)
{
return skipList.find(key);
}
//funzione di ricerca di tutte le definizioni (le restituisce in una ValuesList)
Iteratore findAll(Comparable key)
{
Nodo nodo = skipList.findAll(key);
if(nodo != null)
return new Iteratore(nodo, this.skipList, 0);
else
return null;
}
//restituisce un iteratore che punta alla chiave più piccola
Iteratore entries()
{
return this.skipList.entries();
}
//funzione successors(key)
Iteratore successors(Comparable key)
{
return skipList.successors(key);
}
//funzione predecessors(key)
Iteratore predecessors(Comparable key)
{
return skipList.predecessors(key);
}
//funzione per ottenere la chiave più piccola
Entry first()
{
return skipList.first();
}
//funzione per ottenere la chiave più grande
Entry last()
{
return skipList.last();
}
Entry remove(Entry entry)
{
if(entry == null)
return null;
Nodo nodo = skipList.findAll(entry.key);
if (nodo == null)
return null;
ValuesList lista = (ValuesList)(nodo.d);
if (lista != null)
{
int posizione = lista.posizione(entry.value);
if (posizione != -1)
{
if(skipList.skipRemove(entry.key, posizione) != null)
return entry;
else
return null;
}
}
return null;
}
}
//classe per ritornare un entry coppia(chiave-value)
class Entry
{
Comparable key;
Object value;
public Entry(Comparable key, Object value)
{
this.value = value;
this.key = key;
}
}
//classe iteratore
class Iteratore
{
//variabile che contiene il riferimento al nodo puntato dall'Iteratore
private Nodo nodo;
//variabile che contiene il riferimento alla skipList su cui deve
//muoversi l'iteratore
private SkipList skiplist;
//variabile che contiene il verso di percorrenza:
//1 verso destra, -1 verso sinistra, 0 solo dentro la chiave
private int direzione;
//variabile che tiene conto del livello a cui sono nelle ValuesList
private int definizione;
//costruttore
Iteratore(Nodo nodo, SkipList skiplist, int direzione)
{
this.nodo = nodo;
this.skiplist = skiplist;
this.direzione = direzione;
if(direzione != -1)
this.definizione = 0;
else
this.definizione = ((ValuesList)(nodo.d)).size()-1;
}
//true se ci sono altre entries
boolean hasNext()
{
if (direzione != 0)
{
//verso destra
if (direzione == 1)
{
//ho ancora elementi nella lista
if(definizione < ((ValuesList)(nodo.d)).size()-1)
return true;
//finiti gli elementi nella lista, cambio nodo
else
{
if((nodo.r).r != null)
return true;
else
return false;
}
}
//verso sinistra
else
{
if(definizione > 0)
return true;
else
{
if(skiplist.prev(nodo.key) != null)
return true;
else
return false;
}
}
}
else
{
//devo muovermi solo dentro la lista
if(definizione < ((ValuesList)(nodo.d)).size()-1)
return true;
else
return false;
}
}
//sposta l'iteratore
public boolean next()
{
if (direzione != 0)
{
//verso destra
if (direzione == 1)
{
if (this.hasNext())
{
//mi sposto alla definizione successiva
if(definizione < ((ValuesList)(nodo.d)).size()-1)
definizione++;
else
{
//sposto in avanti il nodo e riparto col conteggio
definizione = 0;
nodo = nodo.r;
}
return true;
}
else
return false;
}
//verso sinistra
else
{
if (this.hasNext())
{
//mi sposto alla definizione precendente
if(definizione > 0)
definizione--;
else
{
//sposto indietro il nodo e riparto col conteggio
nodo = skiplist.prev(nodo.key);
definizione = ((ValuesList)(nodo.d)).size()-1;
}
return true;
}
else
return false;
}
}
else
{
//mi posso spostare solo dentro la lista
if (this.hasNext())
{
definizione++;
return true;
}
else
return false;
}
}
//restituisce l'Entry a cui sta puntando
public Entry getdata()
{
return new Entry(nodo.key, ((ValuesList)nodo.d).get(definizione));
}
}
//classe nodo... quella che verrà usata nella linked list e nell'iteratore
//tutte le variabili usate qui hanno accesso "friendly" in modo da ottenere
//maggiori prestazioni durante gli accessi
//questa scelta non intacca assolutamente la sicurezza della classe dizionario
//in quanto l'utente non avrà mai un oggetto Nodo da manipolare.
//una scelta diversa invece va fatta se si vuole usare la classe SkipList
//per conto suo... infatti il metodo skipSearch restituisce un nodo...
//in quel caso quindi converrebbe dichiare la classe Nodo come privata e costruirla
//internamente alla SkipList
class Nodo
{
//link al nodo di destra
Nodo r;
//link al nodo sotto / ValuesList
Object d;
//chiave associata (un oggetto Comparable)
Comparable key;
//costruttore del nodo
Nodo(Nodo r, Object d, Comparable key){this.r = r;this.d = d;this.key = key;}
}
//lista semplificata usata al posto di LinkedList per risparmiare memoria
class ValuesList
{
private class ValueListNode
{
private ValueListNode next;
private Object value;
private ValueListNode(Object value, ValueListNode next)
{
this.next = next;
this.value = value;
}
}
private ValueListNode head;
//costruttore (nasce direttamente con un elemento, no nodi vuoti)
//così da risparmiare memoria
ValuesList(Object value)
{
this.head = new ValueListNode(value,null);
}
//size
//per risparmiare memoria non viene salvato alcun contatore
//per tenere traccia della dimensione di ogni lista
//quindi è necessaria una scansione ogni volta... minori prestazioni
//ma maggiore risparmio di memoria... le specifiche di progetto parlano
//solo di memoria, quindi si presume che questa scelta sia la più
//adatta
int size()
{
ValueListNode temp = head;
int i = 1;
while (temp.next != null)
{
i++;
temp = temp.next;
}
return i;
}
//funzione di ricerca (lineare) usata per identificare la posizione
//che contiene l'oggetto passato come parametro
int posizione(Object element)
{
ValueListNode temp = head;
int i = 1;
if(temp.value == element)
return 0;
while (temp.next != null)
{
if(temp.value == element)
return (i-1);
temp = temp.next;
}
if(temp.value == element)
return (i-1);
else
return -1;
}
//restituisce un elemento a caso... la testa
//complessità O(1)
Object element()
{
return this.head.value;
}
//aggiunta elemento
//lo inserisce tra la testa e quello dopo
//(la lista non deve essere ordinata)
//complessità O(1)
void add(Object value)
{
this.head.next = new ValueListNode(value, this.head.next);
}
//remove index O(n) [n=numero di elementi nella lista]
boolean remove(int index)
{
//index non valido, esco con false
if(index < 0)
return false;
//creo nodo temporeaneo
ValueListNode temp = this.head;
int i = 0;
if (index == 0)
{
this.head = head.next;
return true;
}
else
{
//mi sposto fino al nodo prima di quello che mi interessa
while ((temp.next != null) && (i < index))
{
temp = temp.next;
i++;
}
//scollego il nodo che voglio togliere ed esco con true
if (i == index)
{
temp.next=(temp.next).next;
return true;
}
else
return false;
}
}
//get index O(n) [n=numero di elementi nella lista]
//restituisce l'oggetto associato all'elemento con indice "index"
//null se l'indice non è corretto....
Object get(int index)
{
//creo nodo temporeaneo
ValueListNode temp = head;
for(int j = 0; j<index; j++)
temp = temp.next;
//restituisco l'oggetto
return temp.value;
}
}
//il cuore di tutto
class SkipList
{
//altezza (quanti piani ha la lista)
private int h;
//nodo in alto a sinistra
private Nodo head;
//moneta
private Random moneta;
//numero elementi
private int numeroElementi;
//-infinito : uso il più piccolo carattere unicode
private final Comparable min;
//+infinito : uso il più grande carattere unicode
private final Comparable max;
//costruttore
SkipList(Comparable min, Comparable max)
{
// mi creo una lista del tipo (* rappresenta una chiave, x rappresenta "null")
//
// * - * - x S1
// | |
// * - * - x S0
// | |
// x x
this.h = 1;
this.head = new Nodo(null,null,min);
Nodo aDx = new Nodo(null,null,max);
Nodo bSx = new Nodo(null,null,min);
Nodo tail = new Nodo(null,null,max);
this.min = min;
this.max = max;
head.r = aDx;
head.d = bSx;
aDx.d = tail;
bSx.r = tail;
numeroElementi = 0;
//inizializzo moneta
moneta = new Random();
}
//ricerca di una chiave
//restituisce il riferimento al nodo la cui la chiave è <= di quella che cerco io
Nodo skipSearch(Comparable key)
{
//parto dalla testa (alto a sinistra)
Nodo temp = head;
int i = h;
//scorro fino al piano terra
while(i>0)
{
temp = (Nodo)temp.d;
i--;
//System.out.println(" <> Sono al livello " + i);
//mi sposto a destra al massimo che posso (finchè è rispettata
//la condizione chiave <= chiave cercata)
while (key.compareTo((temp.r).key) >= 0)
{
//riassegno il nodo facendolo puntare a quello a destra
temp = temp.r;
//System.out.println(" <> mi sono spostato a destra, la prossima chiave sarà " + ((Nodo)(temp.r)).key);
}
}
//System.out.println(" <> finita la ricerca di " + key + " quella prima è " + temp.key + " al piano " + i);
return temp;
}
Entry skipInsert(Comparable key, Object value)
{
//System.out.println("\r\n******** INSERIMENTO DI " + key + " ********");
//skipInsert blindato... chiavi out of range... non inserisco!!!
if(key.compareTo(min)<=0 || key.compareTo(max)>=0)
return null;
//cerco il nodo
Nodo temp = skipSearch(key);
Nodo nodoNuovo;
int i = 0;
//chiave già esistente, aggiungo la definizione alla lista
if ((temp.key).compareTo(key) == 0)
{
((ValuesList)(temp.d)).add(value);
numeroElementi++;
nodoNuovo = temp;
}
//chiave non esistente: creo una lista nuova
else
{
ValuesList lista = new ValuesList(value);
//piazzo il nodo al suo posto nella lista 0
nodoNuovo = new Nodo(temp.r, lista, key);
numeroElementi++;
temp.r = nodoNuovo;
//System.out.println("Nodo nuovo correttamente collegato al livello 0");
//generatore casuale (testa o croce)
i = 0;
while (moneta.nextBoolean())
{
i++;
if (i==h)
{
Nodo tailSopra = new Nodo(null, head.r, max);
head.d = new Nodo(head.r, head.d, min);
head.r = tailSopra;
h++;
}
}
//riparto da capo
temp = head;
int j = h;
for(j = h-1; j > i; j--)
{
temp = (Nodo)temp.d;
//System.out.println("=> mi sono spostato al piano " + (j-1));
//System.out.println("=> ora sono al piano " + j);
while ( ((temp.r).key).compareTo(key) < 0 )
{
temp = temp.r;
//System.out.println("=> mi sono spostato a destra la prossima chiave ha valore " + (((Nodo)temp.r).key));
}
}
Nodo nodoNuovo2 = new Nodo(temp.r, nodoNuovo, key);
temp.r = nodoNuovo2;
while (j > 0)
{
//mi abbasso
temp = (Nodo)temp.d;
j--;
//mi sposto tutto a destra
while ( ((temp.r).key).compareTo(key) < 0 )
{
//System.out.println("*> mi sono spostato a destra la prossima chiave ha valore " + (((Nodo)temp.r).key));
temp = temp.r;
}
//creo il nodo nuovo e lo collego orizzontalmente
//verticalmente lo collego a s0
Nodo nodoNuovoTemp = new Nodo(temp.r, nodoNuovo2.d, key);
nodoNuovo2.d = nodoNuovoTemp;
nodoNuovo2 = nodoNuovoTemp;
//collego orizzontalmente
temp.r = nodoNuovo2;
}
}
//System.out.println(key + " aggiunta con altezza " + i);
//return nodoNuovo;
return new Entry(key, value);
}
//funzione che restituisce il numero di elementi (numero di definizioni)
int size(){return this.numeroElementi;}
//funzione di rimozione
Object skipRemove(Comparable key, int definizione)
{
if(key.compareTo(min)<=0 || key.compareTo(max)>=0)
return null;
//cerco il nodo di base associato
Nodo nodo = (Nodo)skipSearch(key);
//se non ho trovato la chiave corretta esco con false
if (nodo.key.compareTo(key) != 0)
{
return null;
}
//devo rimuovere tutta la colonna senza preoccuparmi di nulla
if (definizione < 0 || ((ValuesList)(nodo.d)).size() < 2)
{
this.numeroElementi = this.numeroElementi-(((ValuesList)(nodo.d)).size());
//parto dalla testa (alto a sinistra)
Nodo temp = head;
Nodo tempPrev = head;
int i = h;
//scorro fino a trovare l'elemento in cima alla mia torre con la chiave che cerco
while(i>0)
{
temp = (Nodo)temp.d;
tempPrev = (Nodo)tempPrev.d;
i--;
//mi sposto a destra al massimo che posso (finchè è rispettata
//la condizione chiave <= chiave cercata)
while (key.compareTo((temp.r).key) >= 0)
{
//riassegno il nodo facendolo puntare a quello a destra
temp = temp.r;
}
while (key.compareTo((tempPrev.r).key) > 0)
{
//riassegno il nodo facendolo puntare a quello a destra
tempPrev = tempPrev.r;
}
if(temp.key.compareTo(key) == 0)
break;
}
//System.out.println(" >> Chiave " + key + " trovata al livello " + i );
//qua ho i che contiene l'altezza del nodo ed il riferimento al nodo "temp"
//che sta in alto sulla torre
//poi ho il riferimento al nodo "tempPrev" che è quello precedente
while (i>0)
{
//ora aggiorno i riferimenti saltando via quella che devo eliminare
//System.out.println(" >> Sono dentro, sposto i riferimenti per far saltare " + key + " dal livello " + i );
tempPrev.r = temp.r;
//mi abbasso con entrambi
temp = (Nodo)temp.d;
tempPrev = (Nodo)tempPrev.d;
i--;
//sposto a destra al massimo "tempPrev"
while (key.compareTo(((Nodo)(tempPrev.r)).key) > 0)
{
//riassegno il nodo facendolo puntare a quello a destra
tempPrev = tempPrev.r;
}
}
//System.out.println(" >> Sono fuori, sposto i riferimenti per far saltare " + key + " dal livello " + i );
tempPrev.r = temp.r;
//elimino le righe vuote (taglio la testa della skiplist)
temp = head;
while ( (((Nodo)(temp.d)).r).r == null )
{
temp.d = ((Nodo)(temp.d)).d;
(temp.r).d = (((Nodo)((temp.r).d)).d);
h--;
}
return new Entry(nodo.key, ((ValuesList)(nodo.d)).get(definizione));
}
//rimuovo solo un elemento
else
{
Object valore = ((ValuesList)(nodo.d)).get(definizione);
if (((ValuesList)(nodo.d)).remove(definizione))
{
this.numeroElementi--;
return new Entry(key, valore);
}
else
return null;
}
}
//funzione entries() completa
Iteratore entries()
{
//non ci sono chiavi che rispettano la condizione
if(this.size() == 0)
return null;
Nodo temp = this.head;
//scorro fino alla base
for(int i=this.h;i>0;i--)
temp = (Nodo)temp.d;
//mi sposto a destra di un nodo così da non leggere -infinito
temp = temp.r;
return new Iteratore(temp, this, 1);
}
//funzione successors(key)
Iteratore successors(Comparable key)
{
//non ci sono chiavi che rispettano la condizione
if(this.size() == 0)
return null;
Nodo temp = (Nodo)(this.skipSearch(key));
if(key.compareTo(temp.key) != 0)
temp = temp.r;
//non ci sono chiavi che rispettano la condizione
if(temp.r == null)
return null;
else
return new Iteratore(temp, this, 1);
}
//funzione predecessors(key)
Iteratore predecessors(Comparable key)
{
//non ci sono chiavi che rispettano la condizione
if(this.size() == 0)
return null;
Nodo temp = (Nodo)(this.skipSearch(key));
//non ci sono chiavi che rispettano la condizione
if(temp.d == null)
return null;
else
return new Iteratore(temp, this, -1);
}
Entry first()
{
if(this.size() == 0)
return null;
Nodo nodo = (this.skipSearch(this.min)).r;
Comparable key = nodo.key;
ValuesList values = (ValuesList)(nodo.d);
return new Entry(key, values.element());
}
Entry last()
{
if(this.size() == 0)
return null;
//parto dalla testa (alto a sinistra)
Nodo temp = head;
int i = h;
//scorro fino al piano terra
while(i>0)
{
temp = (Nodo)temp.d;
i--;
//mi sposto a destra al massimo che posso (finchè è rispettata
//la condizione chiave <= chiave cercata)
while (max.compareTo((temp.r).key) > 0)
{
//riassegno il nodo facendolo puntare a quello a destra
temp = temp.r;
}
}
Comparable key = temp.key;
ValuesList values = (ValuesList)(temp.d);
return new Entry(key, values.element());
}
Nodo prev(Comparable key)
{
//parto dalla testa (alto a sinistra)
Nodo temp = head;
//Nodo nodo = this.skipSearch(key);
int i = h;
//scorro fino al piano terra
while(i>0)
{
temp = (Nodo)temp.d;
i--;
//mi sposto a destra al massimo che posso (finchè è rispettata
//la condizione chiave < chiave cercata)
while (key.compareTo((temp.r).key) > 0)
{
if(key.compareTo((temp.r).key) <= 0)
break;
//riassegno il nodo facendolo puntare a quello a destra
temp = temp.r;
}
}
if(temp.d == null)
return null;
else
return temp;
}
//funzione di ricerca
Entry find(Comparable key)
{
//cerco il nodo di base associato
Nodo nodo = (Nodo)skipSearch(key);
//se ho trovato la chiave corretta mando in output una definizione a caso
if (nodo.key.compareTo(key) == 0)
{
Entry entry = new Entry(nodo.key, ((ValuesList)(nodo.d)).element());
return entry;
}
//altrimenti mando in output null
else
return null;
}
Nodo findAll(Comparable key)
{
//cerco il nodo di base associato
Nodo nodo = (Nodo)this.skipSearch(key);
//se ho trovato la chiave corretta mando in output il nodo
if (nodo.key.compareTo(key) == 0)
return nodo;
//altrimenti mando in output null
else
return null;
}
} |
Prova.java
| Codice: | import java.util.*;
class Prova
{
public static void main (String[] args)
{
//creo il dizionario
//bisogna passargli i due estremi +infinito e meno infinito...
//gli estremi devono essere dati dello stesso tipo di quelli che saranno usati per le chiavi
//e devono implementare l'interfaccia Comparable
//in questo caso faccio i test con le stringhe e quindi uso il più piccolo ed il più grande
//caratteri Unicode disponibile ;)
DizionarioOrdinato dizionario = new DizionarioOrdinato("" + (char)0x0000, "" + (char)0x10FFFD + (char)0x10FFFD + (char)0x10FFFD + (char)0x10FFFD);
//preparo una variabile per contenere le liste restituite da findAll()
ValuesList lista;
Entry entry;
Comparable key;
Iteratore entries;
//creo variabile che conterra un numero intero casuale
int rand;
//creo variabili per il timer
long start, stop;
float durata;
//inizializzo generatore casuale
Random random = new Random();
//test insert()
start = System.currentTimeMillis();
int elementiDaInserire = 200000;
System.out.println("\r\n > Popolo il dizionario con " + elementiDaInserire + " definizioni completamente casuali (anche chiavi duplicate)");
for(int i = 0; i < elementiDaInserire; i++)
{
rand = random.nextInt();
dizionario.insert(rand+"chiave", "definizione"+rand);
}
stop = System.currentTimeMillis();
durata = stop - start;
//test size() <= restituisce il numero di definizioni presenti nel dizionario
if(!dizionario.isEmpty())
System.out.println("Inserimento di " + dizionario.size() + " definizioni completato in " + durata + " millisecondi");
else
System.out.println("Qualcosa è andato storto... il dizionario risulta vuoto... le definizioni memorizzate sono " + dizionario.size() + " (il processo di inserimento è durato " + durata + " millisecondi)");
//test inserimento chiavi doppie: inseriesco altre due definizioni per la chiave 0
System.out.println("\r\n > Aggiungo 3 definizioni associate a 0chiave");
dizionario.insert("0chiave", "definizione00");
dizionario.insert("0chiave", "definizione000");
dizionario.insert("0chiave", "definizione0000");
System.out.println("Aggiunte tre definizioni a 0chiave, ora il dizionario contiene " + dizionario.size() + " definizioni");
//test findAll()
key = "0chiave";
System.out.println("\r\n > Cerco e stampo tutte le definizioni associate a " + key);
entries = dizionario.findAll(key);
if (entries != null)
{
do
{
System.out.println("" + entries.getdata().value);
}while(entries.next());
}
else
System.out.println(key + " non trovata!!!");
//test remove
key = "0chiave";
System.out.println("\r\n > test remove(find(" + key + ")) + findAll(" + key + ") di verifica");
if (dizionario.remove(dizionario.find(key)) != null)
{
entries = dizionario.findAll(key);
if (entries != null)
{
do
{
System.out.println("" + entries.getdata().value);
}while(entries.next());
}
else
System.out.println(key + " non trovata!!!");
}
else
System.out.println("Errore nella rimozione!");
//test find() di tante chiavi
random = new Random();
start = System.currentTimeMillis();
int quante = 0;
int elementiDaCercare = 100000;
System.out.println("\r\n > Faccio un find() di " + elementiDaCercare + " chiavi completamente casuali");
for(int i = 0; i < elementiDaCercare; i++)
{
rand = random.nextInt();
entry = dizionario.find(rand + "chiave");
if (entry != null)
{
quante++;
System.out.println("chiave \"" + rand + "chiave\" trovata, una definizione e' \"" + entry.value + "\"");
}
}
stop = System.currentTimeMillis();
durata = stop - start;
System.out.println("Ricerca di " + elementiDaCercare + " chiavi casuali completata in " + durata + " millisecondi, " + quante + " chiavi trovate");
//test entries() ed iteratore
System.out.println("\r\n > Richiedo iteratore su intera lista ordinata (entries()) e faccio uno scan completo");
entries = dizionario.entries();
int quanteEntry = 0;
if (entries != null)
{
do
{
//System.out.println(entries.key());
quanteEntry++;
}while(entries.next());
}
System.out.println("Iteratore ottenuto, " + quanteEntry + " entry rilevate");
//test successors(start) + iteratore
key = "99985";
System.out.println("\r\n > Richiedo iteratore di tutte le entry con chiave >= di " + key + " e ne faccio una scansione");
entries = dizionario.successors(key);
quanteEntry = 0;
if (entries != null)
{
do
{
System.out.println(entries.getdata().key);
quanteEntry++;
}while(entries.next());
System.out.println("Iteratore ottenuto, rilevate " + quanteEntry + " entry con chiave >= di " + key);
}
else
System.out.println("Iteratore ottenuto, nessuna chiave >= di " + key);
//test predecessors(start) + iteratore
key = "-1000146778chiave";
System.out.println("\r\n > Richiedo iteratore di tutte le entry con chiave <= di " + key + " e ne faccio una scansione");
entries = dizionario.predecessors(key);
quanteEntry = 0;
if (entries != null)
{
do
{
System.out.println(entries.getdata().key);
quanteEntry++;
}while(entries.next());
System.out.println("Iteratore ottenuto, rilevate " + quanteEntry + " entry con chiave <= di " + key);
}
else
System.out.println("Iteratore ottenuto, nessuna chiave <= di " + key);
//test first()
entry = dizionario.first();
if(entry != null)
System.out.println("\r\n > La chiave piu' piccola presente nel dizionario e' " + entry.key);
else
System.out.println("\r\n > Non e' stato possibile trovare la chiave più piccola, il dizionario e' vuoto!");
//test last()
entry = dizionario.last();
if(entry != null)
System.out.println("\r\n > La chiave piu' grande presente nel dizionario e' " + entry.key);
else
System.out.println("\r\n > Non e' stato possibile trovare la chiave più piccola, il dizionario e' vuoto!");
}
} |
_________________
If you can dream it, you can do it.
Always remember that this whole thing was started with a dream and a mouse.
Walt Disney
Agriturismo Vicenza Camere Alloggi Appartamenti Bed & Breakfast |
|
| Torna in cima |
|
 |
Google
Staff
Messaggi: n/a
Località: hwtweakers.net
|
|
 |
kioji
Moderatore
Registrato: 18 Apr 2004
Messaggi: 4246
Località: Sicily
|
| Inviato: 05 Ago 2005 16:06 Oggetto: |
|
|
bravo!!!!!!!!
ma cos'è?????  
_________________
[MyGallery] [Videoacquisizione] [MyWork]
GA-M56S-S3 BE-2400 Geminii 2x1GB Cell HD3650 Onkyo SE-200PCI HD 2X250 Gb
Lite-On LH-18A1H Zalman ZM-MFC1Aerocool Baydream Samtron 19” Canon LBP2900
|
|
| Torna in cima |
|
|
EvolutionCrazy
Webmaster
Registrato: 23 Apr 2003
Messaggi: 4426
Località: Vicenza
|
| Inviato: 05 Ago 2005 16:13 Oggetto: |
|
|
| kioji ha scritto: | bravo!!!!!!!!
ma cos'è????? |
una cosa che m'ha fatto perdere un bel po' di tempo a farla... e imho il prof la da ogni anno... quindi la posto qui per i disgraziati che dovranno farla l'anno prossimo
comunque è una specie di "libreria" che permette di realizzare un dizionario usando una particolare struttura dati molto veloce: un skip list...
di solito le skiplist hanno 4 indici... questa qui è a due... la velocità diminuisce di poco... ma la memoria occupata è molta meno
_________________
If you can dream it, you can do it.
Always remember that this whole thing was started with a dream and a mouse.
Walt Disney
Agriturismo Vicenza Camere Alloggi Appartamenti Bed & Breakfast |
|
| Torna in cima |
|
|
mat1
Paralizzato
Registrato: 06 Set 2004
Messaggi: 18
Località: Lido di Camaiore, near Viareggio
|
| Inviato: 31 Ago 2005 21:37 Oggetto: |
|
|
figata! sarebbe bello fare uno scriptino per il nuke per inserire delle voci nell'enciclopedia grabbandole da qualche parte!
<-- me lo faccio da solo!
_________________
technomat.net
web directory italiana |
|
| Torna in cima |
|
|
BovinoInfernale
Paralizzato
Registrato: 18 Mar 2006
Messaggi: 3
|
| Inviato: 18 Mar 2006 15:03 Oggetto: |
|
|
Ecco qui un disgraziato di qualche anno dopo... grazie della buona volontà Crazy, purtroppo però ora c'è la java 5.0 e i tipi di dati generici sono completamente cambiati (migliorati).
Fatto sta che la mia Skiplist non compila proprio a causa dei dati generici, grazie cmq. |
|
| Torna in cima |
|
|
EvolutionCrazy
Webmaster
Registrato: 23 Apr 2003
Messaggi: 4426
Località: Vicenza
|
| Inviato: 18 Mar 2006 15:08 Oggetto: |
|
|
il progetto che ho messo li sopra io l'ho compilato e testato con Java5...
è scritto anche nella relazione che tale scelta l'ho fatta per questioni di prestazioni...
non so però se nelle skiplist che vi ha spiegato in classe vi impone di fare qualcosa di diverso da come lo ha fatto fare a noi l'anno scorso...
in bocca al lupo per l'esame con Bombi
_________________
If you can dream it, you can do it.
Always remember that this whole thing was started with a dream and a mouse.
Walt Disney
Agriturismo Vicenza Camere Alloggi Appartamenti Bed & Breakfast |
|
| Torna in cima |
|
|
BovinoInfernale
Paralizzato
Registrato: 18 Mar 2006
Messaggi: 3
|
| Inviato: 18 Mar 2006 17:06 Oggetto: |
|
| < | | |
|
| | |
