stl map performance?

Question

Estoy usando map<MyStruct, I*> map1;. Aparentemente, el 9% de mi tiempo total de aplicación se gasta allí. Específicamente en una línea de una de mis funciones principales. El mapa no es muy grande (< 1k casi siempre, < 20 es común).

¿Existe una implementación alternativa que pueda querer usar? Creo que no debería escribir el mío, pero podría si pensase que era una buena idea.

Información adicional: Siempre compruebo antes de agregar un elemento. Si existe una clave, necesito informar un problema. Después de un punto, utilizaré el mapa en gran medida para las búsquedas y no añadiré más elementos.

Answer 1

¿Sería más rápido simplemente hacer un insert y verificar si el pair.second es false si la clave ya existe?

como esto

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

en lugar de hacer una llamada find cada vez?

Answer 2

La forma en que usa el mapa, está realizando búsquedas sobre la base de una instancia MyStruct y, dependiendo de su implementación particular, la comparación requerida puede o no ser costosa.

Answer 3

Puede ser una posibilidad remota, pero para colecciones pequeñas, a veces el factor más crítico es el rendimiento cache.

Desde std::map implementa un árbol Rojo-Negro, que es [yo sepa] no es muy caché eficientes - tal vez aplicar la hoja como std::vector<pair<MyStruct,I*>> sería una buena idea, y utilizar la búsqueda binaria allí [en lugar de un mapa look-ups] , como mínimo, debería ser eficiente una vez que empiece a buscar [detener insertando elementos], ya que std::vector es más probable que quepa en el caché que map.

Este factor [cpu-cache] generalmente se descuida y se oculta como constante en la notación O grande, pero para colecciones grandes puede tener un efecto importante.

Answer 4

¿Existe una implementación alternativa que pueda querer usar? Creo que no debería escribir el mío, pero podría si pensase que era una buena idea.

Si comprende bien el problema, debe detallar cómo su implementación será superior.

¿Es map la estructura correcta? Si es así, entonces la implementación de su biblioteca estándar probablemente será de buena calidad (bien optimizada).

Can MyStruct comparación se puede simplificar?

¿Dónde está el problema - cambio de tamaño? ¿buscar?

¿Ha minimizado la copia y asignado los costos para sus estructuras?

Answer 5

En lugar de map puede probar unordered_map que utiliza las teclas de acceso directo, en lugar de un árbol, para buscar elementos. This answer da algunas pistas sobre cuándo preferir unordered_map sobre map.

Answer 6

Primero debe comprender qué es un mapa y qué representan las operaciones que está realizando. Un std::map es un árbol binario equilibrado, la búsqueda tomará operaciones O(log N), cada una de las cuales es una comparación de las teclas más algunas adicionales que puede ignorar en la mayoría de los casos (administración de punteros). La inserción lleva más o menos el mismo tiempo para ubicar el punto de inserción, más la asignación del nuevo nodo, la inserción real en el árbol y el reequilibrio. La complejidad es nuevamente O(log N) aunque las constantes ocultas son más altas.

Cuando intenta determinar si una clave está en el mapa antes de la inserción, está incurriendo en el costo de la búsqueda y si no tiene éxito, el mismo costo para ubicar el punto de inserción. Puede evitar el costo adicional usando std::map::insert que devuelve un par con un iterador y un bool que le informa si la inserción realmente sucedió o si el elemento ya estaba allí.

Más allá de eso, es necesario entender lo costoso que es comparar sus llaves, que se cae de lo que muestra el interrogación (MyStruct pudo contener sólo una int o un millar de ellos), que es algo que hay que tener en cuenta.

Por último, podría darse el caso de que un map no es la estructura de datos más eficiente para sus necesidades, y es posible que desee considerar el uso ya sea un (tabla hash) std::unordered_map que ha esperado inserciones de tiempo constantes (si la función hash no es horrible) o para pequeños conjuntos de datos incluso un conjunto ordenado simple (o std::vector) en el que puede utilizar la búsqueda binaria para localizar los elementos (esto reducirá el número de asignaciones, al costo de inserciones más costosas, pero los tipos retenidos son lo suficientemente pequeños como para valer la pena)

Como siempre con el rendimiento, mida y luego intente comprender dónde se está gastando el tiempo. También tenga en cuenta que un 10% del tiempo dedicado a una función o estructura de datos en particular puede ser mucho o casi nada, dependiendo de cuál sea su aplicación. Por ejemplo, si su aplicación solo realiza búsquedas e inserciones en un conjunto de datos, y eso solo requiere un 10% de la CPU, ¡tiene mucho que optimizar en cualquier otro lugar!

Answer 7

Como se indica en los comentarios, sin el código adecuado, hay pocas respuestas universales para darle. Sin embargo, si MyStruct es realmente grande, la copia de la pila puede ser costosa. Tal vez tenga sentido para almacenar punteros a MyStruct e implementar su propio mecanismo de comparación:

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; 

Sin embargo, esto es algo que tendrá al perfil. Es podría acelerar las cosas.

que se vería a un elemento como este

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

hace falta decir que hay más posibilidades de optimizar.