Newsgroup: it.comp.lang.c++
Titolo: Re: Bilanciamento albero in STL map

 ordinamento?
Se sai a priori quanti sono gli elementi puoi dimensionare in anticipo 
il vettore, e visto che sono quasi ordinati potresti usare un algoritmo 
di ordinamento adatto. Di solito il std::sort della libreria a corredo 
del gcc e del msvc, per valori non troppo piccoli di elementi da 
ordinare, mi pare, usi shell sort come algoritmo. Non mi ricordo 
minimamente che complessità ha nell'ordinamento di serie di dati già 
ordinati.
Questo se prima carichi il vettore, e poi lo usi. Se devi mettere o 
togliere elementi in continuazione è probabile che non sia il 
contenitore adatto.
-- 
Articolo 33 della Costituzione italiana: L'arte e la scienza sono 
libere e libero ne è l'insegnamento.
Se siete tosti: 
http://www.rexresearch.com/kervran/kervran.htm

 a tutte le idee.
Questo capita a fissarsi sui dettagli *sbagliati*. Il punto non e' il
fatto che map e' implementato con un albero, il punto e' che lo
standard ti garantisce un comportamento asintotico, ovvero come
peggiorano le prestazioni al crescere del numero dei nodi, e le tue
preoccupazioni sono mal riposte. Se hai un problema di prestazioni
*effettivamente misurato* direi che ti conviene guardare altrove e non
nell'implementazione di std::map.
Ciao,
Nicola
P.S. In genere std::map e' implementata tramite un'albero rosso-nero:
http://it.wikipedia.org/wiki/Albero_rosso-nero

 contenitore adatto.
Giusto.
Ciao,
Nicola

 massimo tre-quattro volte.
Tutto giusto quel che dici. Ho quotato questo solo per dire che io 
pensavo ai pericoli di sballare in eccesso la stima. Dimensionare un 
vettore per 10 milioni di elementi per poi mettercene un milione 
potrebbe non essere il massimo. Potrebbe, 10 milioni per un byte fa 
9.54 MB, e su un PC può essere una richiesta ridicola di memoria.
Come dicevi tu: prima bisogna *misurare* le prestioni del sistema, 
*poi* preoccuparsi di togliere i colli di bottiglia.
Invertire le cose lo lascerei fare solo ai professionisti che si 
occupano stabilmente di certi problemi. Gente che passato ha fatto 
decine di misurazioni per sistemi simili a quelli che andranno a 
sviluppare, e che sa in anticipo quali sono i problemi e gli effetti di 
certe soluzioni.


 9.54 MB, e su un PC può essere una richiesta ridicola di memoria.
Un altro aspetto da non trascurare e' se gli oggetti dell'OP stanno
fisicamente nel contenitore o sono gestiti tramite puntatore. In
questo caso il numero di allocazioni resterebbe dello stesso ordine di
grandezza, ma l'utilizzo del vector potrebbe essere particolarmente
vantaggioso, visto l'esiguo costo dello scambio di elementi e
l'importanza che potrebbe assumere la localita' di accesso.
Ciao,
Nicola

 Apx.

 l'importanza che potrebbe assumere la localita' di accesso.
Con località di accesso cosa si deve intendere? Se si deve intendere 
come _vicinanza_ in memoria, beh no, in questo caso l'accesso è locale 
solo per i puntatori. Gli oggetti puntati, salvo politiche sofisticate 
di allocazione, sarebbero "sparsi". Comunque rischiano di essere 
dettagli esoterici non per tutti. Per esempio se l'accesso al vettore è 
casuale non ci sarebbe comunque _vicinanza_ in memoria nella pratica. E 
comunque non è detto che il collo di bottiglia _vero_ sia lì. Oppure se 
è lì potrebbe essere ovviato con implementazione terra terra di una 
cache.
Insomma, oggi non ho proprio voglia di lavorare, e sono contento di 
fare due chiacchere su usenet.


 (semplicemente o peggio doppiamente linkate).
No. std::map deve soddisfare a requisiti prestazionali precisi, se non
sbaglio inserimento e cancellazione O(1) e ricerca O(log n), per cui
e' difficile che sia implementata con qualcosa di diverso da un albero
con un meccanismo di bilanciamento; la tecnica usata di solito si basa
sugli alberi "rosso-neri".
Ciao,
Nicola

 cache.
soprattutto poco controllabili, dal momento che dipendono da come il
compilatore "disegna" il layout della memoria e da come opera il
gestore della memoria dinamica.
Ciao,
Nicola

 gestore della memoria dinamica.
Sia con GCC che con il MSVC puoi in realtà "parzialmente" controllare 
la località in memoria del codice linkato, e avere la località delle 
routine più usate. Avere il codice molto usato nella cache di primo 
livello di un processore ha un suo perché. Poi uno si può sempre fare 
il suo allocatore.
I secoli di onorata (?) carriera, con la barba ormai bianca, me ne sono 
sempre fregato di spingermi a tali livelli. Di solito, per quel che ho 
visto, c'è sempre molto da limare lavorando in altre direzioni.
Oppure è semplicemente inutile. Gestisco un server che processa mail, e 
con i test interni sono arrivato al massimo a 50 mila mail al giorno 
processabili. Nessun nostro cliente arriva a tali valori, e se mai ci 
arrivasse basterebbe forse comprare un computer più potente. Credo che 
il nostro cliente con più contatti con il pubblico arrivi a qualche 
milione di mail l'anno, e se dividi per 365 il numero diventa 
piccolino. Questo non per vantarmi, ma solo per dire che il tempo speso 
per ottimizzare deve essere anche ben valutato aziendalmente. Più di 
tanto può non avere senso spingersi. Magari è meglio "perdere" tempo 
per avere codice meglio mantenibile invece che codice più veloce.
Anche perché altrimenti su processori Intel useremmo tutti il 
compilatore Intel, e useremo tutti il C/C++ come linguaggio, e così non 
succede.
Detto ciò ci tengo a rimarcare ancora quello che hai detto. Prima si 
*misurano* le prestazioni del sistema, magari di un prototipo. *Poi*, 
con i valori su pezzo di carta, si ci preoccupa se usare una mappa o un 
vettore, oppure se è meglio dedicare il proprio tempo ad altro. Senza 
numeri si rischiano di fare considerazioni senza costrutto.
Mettere al primo posto le prestazioni in un progetto, per quelche che 
ho visto, non porta mai a nulla di buono. Un buon design pulito, quello 
si che rende. C'è sempre tempo per complicare.


 sugli alberi "rosso-neri".
Segnalo questo per chi fosse interessato (un po' vecchiotto ma è
sempre il buon vecchio DDJ):
http://www.ddj.com/184410531

ho visto, non porta mai a nulla di buono.
Sono d'accordo, in linea di massima. Il problema č quando i vincoli
prestazionali sono requisiti rigidi del progetto e scalare fisicamente
non risulta cosě facile. Ho partecipato allo sviluppo di un
middle-ware, cui veniva richiesta l'elaborazione di un tot di
transazioni entro un certo tempo e c'era poco da fare.... Nonostante
questo, vale ugualmente quanto dici: si puň sempre creare prototipi e
poi fare tuning dove serve (e difatti č come abbiamo proceduto).