Newsgroup: it.comp.lang.c++
Titolo: Consiglio struttura dati

Devo implementare una struttura dati in cui ogni elemento č composto da due 
campi:
int id;
int crediti;
In tutta la struttura esiste al piů un solo elemento avente un certo valore 
del campo id.
Su questa struttura devo poter eseguire *velocemente* due operazioni:
1) localizzazione di un elemento avente un certo id (eventuale inserzione se 
non presente)
2) localizzazione ed eliminazione dell'elemento avente il campo crediti piů 
alto
Cosa mi consigliate di usare ? Possibilmente usando la STL...
Grazie !!
-- 
LF

 Cosa mi consigliate di usare ? Possibilmente usando la STL...
Dunque. Il problema sembra risiedere che le due operazioni "veloci"
devono usare ciascuno una chiave diversa.
Ora non ho tempo per pensare una soluzione verament furba (oppure
sono solo stupido). Pero' io se avessi solo 3 minuti farei cosi':
visto che i dati occupano veramente poca memoria non mi preoccuperei
di replicarli. Allora farei uso di due strutture ciascuna che contiene
tutti i dati.
La prima sarebbe una map<int,int> in cui usi id come chiave.
A questo punto puoi velocemente procedere a tutte le operazioni
basate sulla chiave id. (quindi localizzazione ed inserzione).
La seconda sarebbe una priority_queue<Rec>  dove Rec e' sempre
il tuo record, ma con un operatore di confronto basato sul campo
crediti.
La priority_queue serve proprio per poter localizzare ed eliminare
l'elemento con il campo piu' grande (o piccolo, a seconda di come hai
definito l'operazione di confronto).
A questo punto se devi localizzare un elemento dato l'id, usi la map.
se devi inserirlo lo inserisci velocemente in entrambe le strutture dati.
Se vuoi trovare velocemente quello col credito piu' alto usi la 
priority_queue.
Se vuoi CANCELLARE quello con credito piu' alto, lo trovi e lo cancelli
dalla priority_queue e poi, siccome lo hai trovato e quindi hai 
recuperato l'id, con quell'id lo puoi cancellare velocemente anche dalla 
  map.
Ciao,
g.

   map.
Ottima idea, non avevo pensato ad usare due strutture al posto di una. 
L'unica cosa che forse necessita di un ulteriore riflessione è il fatto che 
(non l'avevo specificato) la prima operazione, la localizzazione di un 
elemento con un dato id, può prevedere la successiva modifica del campo 
crediti. In questo caso l'accesso casuale alla priority_queue che 
complessità ha ?
Grazie !!
-- 
LF

 complessità ha ?
Dunque, se devi modificare il valore sono cavoli perche'
penso che la priority_queue (che la morte sua sarebbe essere 
implementata con un heap) non dovrebbe mantenere ordinati gli
elementi (a parte il primo) quindi non e' banale trovarne uno
in mezzo per modificarlo (in ogni caso si invaliderebbe la struttura !)
Insomma: la priority queue non va bene.
Io ti direi cosi' su due piedi di usare invece
di una priority_queue un altro contenitore che mantenga sempre
le cose ordinate, ma con accesso per mezzo di chiave.
Per esempio puoi mettere il tutto
in un set che sia ordinato sulla coppia di valori (credito, id).
Siccome l'id e' unico questo garantisce alla funzione di confronto
che la coppia e' unica.
Devi solo ordinarle (nella funzione che definirai tu) rispetto a 
credito. E se credito e' uguale rispetto a id.
A questo punto MiaStruttura.begin()  puntera' all'elemento
con credito piu' alto o basso a seconda del confronto.
Invece se vuoi modificare un record allora prima lo elimini
grazie al fatto che conosci la coppia (credito,id) , e poi
lo reiserisci corretto.
ciao, ora vado a casa, caso mai ci si risente lunedi...
g.

 ciao, ora vado a casa, caso mai ci si risente lunedi...
Grazie mille e buon weekend !! :)
-- 
LF

 in un set che sia ordinato sulla coppia di valori (credito, id).
Scusa se ti disturbo ancora...:)
Ho implementato la soluzione che mi hai suggerito (usando std::set), e 
funziona molto bene.
Tuttavia mi sono accorto che, tra le due operazioni sull'oggetto, 
l'inserimento/modifica di un elemento è più frequente dell'estrazione 
dell'elemento a credito più alto.
Attualmente la prima operazione (se non sbaglio) è n*log(n), mentre la 
seconda è a tempo costante: credo sarebbe più efficiente la situazione 
opposta, ovvero inserimento in tempo costante ed estrazione "primo" 
elemento a complessità logaritmica.
Non so però se è possibile una cosa del genere...
Grazie ancora,
-- 
LF


((Posso chiederti per curiosita' quanti valori in media
ti aspetti di avere nella struttura (ordine di grandezza).))
Penso che modificare (ovvero cancellare+inserire) un elemento
dal set<> abbia un costo dell'ordine di log(n), non di n*log(n)
(considera che con n*log(n) tipicamente ci ordini tutta la struttura
dati).
Quindi non ci sono molti margini per il miglioramento,
perche' quando inserisci devi prima trovare e trovare ti
costa comunque log(n).
In linea di principio se tu avessi veramente tanti inserimenti
e pochissime ricerche/modifiche, allora
potresti usare un banale vettore (con inserimento in coda),
e una banale scansione lineare di tanto in tanto per reperire/modificare
l'informazione desiderata.
Chiaramente dipende molto anche dalle grandezze in gioco.
Ma non sarebbe una soluzione che risponde bene ad eventuali
differenze nella distribuzione della frequenza delle operazioni.
Ciao,
g.

 differenze nella distribuzione della frequenza delle operazioni.
Infatti, mi sa che sono io che mi faccio prendere da troppe manie di 
efficienza...:)
Grazie di tutto !!
-- 
LF

 supposizione...
Volevo aggiungere un esempio di utilizzo (in effetti è il problema 
principale che ha dato "origine" allo sviluppo del componente):
C'è una cache associativa (int->string) che deve occupare al massimo un 
certo quantitativo di memoria. Quindi è necessario tener traccia, con 
qualche criterio, del suo utilizzo, per poi liberare spazio quando il 
limite di memoria viene raggiunto.
In questo caso ad ogni lettura si aggiornano i crediti dell'elemento in 
cache, ad ogni nuovo inserimento si controlla se il limite è stato 
raggiunto, e se sì si fa spazio.
Ovviamente in questo caso la frequenza delle due operazioni di cui parlavamo 
è sbilanciata nella direzione che avevo detto.
-- 
LF