stl performance della mappa?

Question

Sto usando map<MyStruct, I*> map1;. Apparentemente il 9% del tempo totale della mia app è trascorso lì. In particolare su una riga di una delle mie principali funzioni. La mappa non è molto grande (< 1k quasi sempre, < 20 è comune).

Esiste un'implementazione alternativa che potrei voler utilizzare? Penso che non dovrei scrivere il mio ma potrei se pensassi che fosse una buona idea.

Ulteriori informazioni: Controllo sempre prima di aggiungere un elemento. Se esiste una chiave, devo segnalare un problema. Poi, dopo un punto, userò la mappa pesantemente per le ricerche e non aggiungerò altri elementi.

Answer 1

Sarebbe più veloce fare semplicemente un insert e verificare se lo pair.second è false se la chiave esiste già?

come questo

if (myMap.insert(make_pair(MyStruct, I*)).second == false) 
{ 
    //report error 
} 
else 
    // inserted new value 

piuttosto che fare un find chiamata ogni volta?

Answer 2

Nel modo in cui si utilizza la mappa, si effettuano ricerche sulla base di un'istanza MyStruct e, a seconda dell'implementazione particolare, il confronto richiesto può essere o meno costoso.

Answer 3

Potrebbe essere una soluzione lunga, ma per le piccole raccolte, a volte il fattore più critico è la prestazione cache.

Poiché std::map implementa un albero rosso-nero, che è [AFAIK] non molto efficiente in termini di cache, l'implementazione della mappa come std::vector<pair<MyStruct,I*>> potrebbe essere una buona idea e utilizzare la ricerca binaria lì [anziché le ricerche di mappe] , per lo meno dovrebbe essere efficiente una volta che si avvia solo la ricerca [smettere di inserire elementi], dal momento che lo std::vector è più probabile che si adatti alla cache rispetto allo map.

Questo fattore [cpu-cache] viene solitamente trascurato e nascosto come costante nella notazione O grande, ma per le raccolte di grandi dimensioni potrebbe avere un effetto maggiore.

Answer 4

Esiste un'implementazione alternativa che potrei voler utilizzare? Penso che non dovrei scrivere il mio ma potrei se pensassi che fosse una buona idea.

Se si capisce il problema abbastanza bene, si dovrebbe specificare come la vostra implementazione sarà superiore.

È map la struttura corretta? Se è così, allora l'implementazione della tua libreria standard sarà probabilmente di buona qualità (ben ottimizzata).

È possibile semplificare il confronto MyStruct?

Dov'è il problema - ridimensionamento? consultare?

Hai minimizzato la copia e l'assegnazione dei costi per le tue strutture?

Answer 5

Invece di map è possibile provare unordered_map che utilizza le chiavi hash, anziché un albero, per trovare gli elementi. This answer fornisce alcuni suggerimenti su quando preferire unordered_map su map.

Answer 6

Per prima cosa devi capire cos'è una mappa e quali sono le operazioni che stai facendo. A std::map è un albero binario bilanciato, la ricerca richiederà le operazioni O(log N), ognuna delle quali è un confronto delle chiavi più alcuni extra che è possibile ignorare nella maggior parte dei casi (gestione dei puntatori). L'inserimento impiega all'incirca lo stesso tempo per individuare il punto di inserimento, oltre all'assegnazione del nuovo nodo, l'effettivo inserimento nell'albero e il ribilanciamento. La complessità è ancora O(log N) sebbene le costanti nascoste siano più alte.

Quando si tenta di determinare se una chiave è presente nella mappa prima dell'inserimento, si incorre nel costo della ricerca e, se non riesce, lo stesso costo per individuare il punto di inserimento. Puoi evitare il costo aggiuntivo utilizzando std::map::insert che restituisce una coppia con un iteratore e un bool che ti dice se l'inserimento è effettivamente avvenuto o se l'elemento era già lì.

Oltre a ciò, è necessario capire quanto costoso è quello di confrontare le chiavi, che cade fuori di ciò che gli spettacoli interrogativi (MyStruct poteva contenere un solo int o mille di essi), che è qualcosa che devi prendere in account.

Infine, potrebbe essere il caso che una map non è la struttura dei dati più efficiente per le vostre esigenze, e si potrebbe prendere in considerazione utilizzando un (tabella hash) std::unordered_map che ha previsto inserimenti di tempo costanti (se la funzione di hash non è orribile) o per piccoli set di dati anche un array ordinato ordinario (o std::vector) su cui è possibile utilizzare la ricerca binaria per individuare gli elementi (questo ridurrà il numero di allocazioni, al costo di inserimenti più costosi, ma se i tipi mantenuti sono abbastanza piccoli potrebbe valerne la pena)

Come sempre con le prestazioni, misurare e quindi cercare di capire dove viene trascorso il tempo. Si noti inoltre che il 10% del tempo trascorso in una particolare funzione o struttura dati potrebbe essere molto o quasi nulla, a seconda di quale sia l'applicazione. Ad esempio, se la tua applicazione sta solo eseguendo ricerche e inserimenti in un set di dati, e che richiede solo il 10% della CPU, hai molto da ottimizzare ovunque!

Answer 7

Come indicato nei commenti, senza codice corretto, ci sono poche risposte universali da darti. Tuttavia, se MyStruct è davvero enorme, la copia dello stack potrebbe essere costosa. Forse ha senso per memorizzare i puntatori ai MyStruct e implementare il proprio meccanismo di confronto:

template <typename T> struct deref_cmp { 
    bool operator()(std::shared_ptr<T> lhs, std::shared_ptr<T> rhs) const { 
    return *lhs < *rhs; 
    } 
}; 

std::map<std::shared_ptr<MyStruct>, I*, deref_cmp<MyStruct>> mymap; 

Tuttavia, questo è qualcosa che si dovrà al profilo. È potrebbe cose di velocità.

Si potrebbe cercare un elemento come questo

template <typename T> struct NullDeleter { 
    void operator()(T const*) const {} 
}; 
// needle being a MyStruct 
mymap.find(std::shared_ptr<MyStruct>(&needle,NullDeleter())); 

Inutile dire che non v'è più possibilità di ottimizzare.