Newsgroup: it.comp.lang.c++
Titolo: consigli per struttura dati

Vorrei implementare una tabella hash contentente coppie (key, object)
 con chiave char non ripetibile all'interno dell'hash.
Visto che la chiave è di tipo char, e che mi serve la massima efficienza
vorrei implementarla senza l'uso di array.
Cioè una strutura interna del tipo
char table[256];
 vorrei evitarla perchè questo hash va instanziato migliaia e migliaia di
volte in poco tempo.
quindi pensavo di utilizzare i bit stessi no?
struct table
{
int e1;
int e2;
int e3;
int e4;
...
};
e usare gli operatori sui bit per capire se una cella è in uso ecc...
Il problema è che non mi sembra PORTABILE visto che dipende da sizeof(int)
il fatto di coprire o meno i 256 bit.
E poi è veramente efficiente operare in questo modo?

  con chiave char non ripetibile all'interno dell'hash.
mi sembra propio difficile ottenere un hashing  con chiave non ripetibile,
esiste sempre il problema delle collisioni.

 ha scritto nel messaggio
news:DHXUc.10859$B06....@news.edisontel.com...

 No. E' assicurato dal programma che non inserisco elementi con chiave
uguale nell'hash.

 E poi è veramente efficiente operare in questo modo?
Confeso che non ho capito molto cosa vuoi fare...
In una hash con una coppia (key,object) ad una chiave key dovrebbe
corrispondere un puntatore ad un oggetto (o ad una lista di oggetti, a
seconda del tipo di hash).
Vedendo il tuo codice penso che char table[256] non è nessuna hash ma solo
un array di caratteri e anche da quello che spieghi con la tua struttura,
vedo solo l'intenzione di creare 256 bit, il che fa pensare piuttosto ad una
hast (key,bool) dove key = {0,...,255} , se è così e t'interessano
portabilità ed efficienza, ti consiglio di usare std::bitset.
Bitset internamente lavora con unsigned long ed è una classe estremamente
efficiente, quindi per 256 bit ti occupa solo 32 bytes.
ciao.

 efficiente, quindi per 256 bit ti occupa solo 32 bytes.
Si ma ad ogni bit devo poter far corrispondere un puntatore a una classe. Se
questo è NULL allora l'elemento non è presente altrimenti vogli ottenere
l'elemento. Quindi mi pare che non posso usare  std::bitset.

 ottenere l'elemento. Quindi mi pare che non posso usare std::bitset.
Continua a non essere molto chiaro.  Probabilmente sarebbe utile
conoscere il problema originale e sapere a cosa ti serve questo
"hash".
Da quello che ho capito vuoi una tabella che associa ad ogni valore
nell'intervallo 0..255 un oggetto oppure "nessun oggetto".
Per esempio:
  Object * table [256];
oppure qualche variante tipo boost::array o std::vector.
In questo caso non avrebbe senso usare un array di caratteri o un
array di interi trattati come insieme di bit.
Hai detto che deve essere efficiente.  Che cosa deve essere
efficiente: la creazione di nuove tabelle, la copia della tabella, il
lookup, la modifica, lo spazio occupato, ...?
Se ad ogni valore corrisponde sempre lo stesso oggetto e l'unica cosa
che cambia da una tabella all'altra e` la presenza o meno
dell'oggetto, puoi creare un'unica tabella "char -> object" e tante 
tabelle "char -> bool" (piu` piccole) per sapere se l'oggetto c'e` o
no.
        Mauro

 l'elemento. Quindi mi pare che non posso usare  std::bitset.
Allora quando hai dei problemi bisogna che ti spieghi molto meglio di come
hai fatto.
Che cosa significava allora char table[256]; ??
O quella serie di 4 int in una struttura? Che hash credi di fare o cosa
pensavi di mostrarci in questo modo?
Al massimo usa miaClasse* table[256]; e li setti tutti a
static_cast<miaClasse*>(0).
Se l'elemento i-esimo che è un unsigned char "castato" a int che hai nella
tua testa non c'è, avrà table[i]==0, mentre quando lo inserisci fai
table[i]=&miaIstanza. Così non risolvi le collisioni ma affermi d'averci già
pensato tu.
Allora secondo te, vorresti evitare l'array perchè sarebbe troppo pesante?
Pensi che il software sia fatto di aria fritta?


Certamente la creazione della tabella,  invece la copiatura e lo spazio non
mi interessano molto, poi soprattutto deve essere veloce il lookup.
Allora spiego il problema a questo punto.
Ho un albero i cui nodi hanno un puntatore al padre e una struttura dati che
contiene i Link ai figli.
Ogni link che collega i nodi porta con se un etichetta. Il modo in cui si
costruiisce l'albero assicura che non vi possano essere figli dello stesso
nodo, la cui etichetta (associata al link che collega il figlio con il nodo
padre) inizia con lo stesso carattere.
Si tratta di suffix tree, se lo conoscete.
Ecco io volevo ottimizzare la struttura che contiene i figli. Con un
std::map<char, Link*> si ottengono buone prestazioni rispetto a
std::vector<Link*>.
Devono essere molto veloci la creazione della struttura, visto che vi
possono essere migliaia di nodi da costruire in pochissimo tempo, e anche il
lookup a partire dal carattere iniziale dell'etichetta di ogni Link.
Anche l'iterazione di tutti gli elementi contenuti nella struttura è
importante.

 Pensi che il software sia fatto di aria fritta?
Evita il sarcasmo anche perché gli array  non sono tutto nella vita.
Gli operatori bit a bit possono essere molto piu' veloci per alcune cose
particolari, quindi io non generalizzerei così tanto.

 particolari, quindi io non generalizzerei così tanto.
Sono fantastici per puntare alle istanze di classe! Ma dai... parli con
gente che scrive software da decenni...
Lascia stare Ukkonen ed il sarcasmo inesistente che tu mi attribuisci.
Avevi affermato nel tuo primo post di poter escludere l'ipotesi di
collisioni! Dov'è il sarcasmo? Ti "auto-sarcasmi" da solo?
Hai affermato, testuali parole:
"Allora mi servono 256 bit.
char table[32];  può rappresentare 256 bit.
 Ecco se il bit n-esimo è a 1 allora significa che l'elemento n-esimo
esiste.
Però in effetti mi serve lo stesso un array di puntatore per memorizzare i
vari puntatori che la struttura dati mi deve restituire, quindi non è un
gran risparmio ora che ci penso."
Il fatto è che Ukkonen conosce l'informatica, tu no!
Per giunta ammetti che non ci avevi pensato, ma tu come li scrivi i
programmi? A caso?
Hai sicuramente toppato dicendo che ti servono i bit per verificare
l'esistenza in hash quando la stessa cosa la fai con un array di puntatori
(date le premesse dei tuoi primi post) ad i tuoi oggetti. Dov'è il sarcasmo?
Poi dici - "Ecco io volevo ottimizzare la struttura che contiene i figli.
Con un
std::map<char, Link*> si ottengono buone prestazioni rispetto a
std::vector<Link*>."
Non si ottimizza "a naso". Dovresti conoscere le complessità di operazioni
comuni nelle mappe e nei vettori.
Magari facevi pure una ricerca lineare fra gli elementi del vettore, vero?
Complessità O(n).
Sfido: non conosci la complessità di map nel trovare un elemento in base
alla chiave? O(log2 n).
Se tu avessi ordinato il vector e avessi fatto una ricerca binaria avresti
trovato la stessa complessità della mappa.
Sai qual'è la complessità minima ottenibile nell'implementare una tabella
hash senza collisioni dove la funzione di hash ritorna interi da 0 a 255 ?
Ti dico che è il caso ideale, è la hash che tutti vorrebbero avere. O(1). E'
un array di 256 puntatori.
Sai cos'è che non sopporto, quelli che chiedono aiuto su di un NG e poi
sanno tutto loro.

 sanno tutto loro.
Non sopporto neanche te stesso?Beh ti capisco...

http://www.marco5x.net/usenet/galateo.htm


Ciao, ti ringrazio, d'avermelo ricordato.
Per questo motivo, chiedo scusa...
La mia *ultima* risposta ad "alberto" dovrebbe essere già visibile su
it.discussioni.litigi, dove comunque (lo dico fin da ora, non continuerò a
rispondere).
Ho perso anche troppo tempo.
Io scrivo su questo NG ormai da qualche anno, lo faccio con immenso piacere
e vorrei continuare a farlo civilmente, purtroppo io ho il mio stile e le
mie convizioni e a volte qualcuno se la prende, credo però di non aver
offeso proprio nessuno.
Più che il suo programma, alberto, è riuscito piuttosto a farmi sentire
preso per i fondelli.
Spero che presto saremo impegnati per parlare di C++.
chiudo.