c++ - una - odile fernandez libros

El mapa C++ más rápido?

Question

Corrígeme que estoy equivocado, pero std :: map es un mapa ordenado, por lo que cada vez que inserto un valor, el mapa usa un algoritmo para ordenar sus elementos internamente, lo que lleva algún tiempo.

Mi aplicación obtiene información sobre algunos elementos en un intervalo constante.

Esta aplicación mantiene un mapa que se define así:

::std::map<DWORD, myItem*>

Al principio, todos los artículos se consideran "nuevos" en la aplicación. Se está asignando y agregando un objeto "Artículo" a este mapa, asociando su id y un puntero a él.

Cuando no se trata de un elemento "nuevo" (solo una actualización de este objeto), mi aplicación debe encontrar el objeto en el mapa, usar la identificación proporcionada y actualizar.

La mayoría de las veces recibo actualizaciones.

Mi pregunta es:
¿Hay alguna implementación de mapa más rápida o debo seguir usando esta?
¿Es mejor usar unordered_map?

Answer 1

¿Es mejor usar unordered_map?

Posiblemente.

std:map proporciona un rendimiento consistente en O (log n) porque debe implementarse como un árbol equilibrado. Pero std:unordered_map se implementará como una tabla hash que podría darte O (1) rendimiento (buena función hash y distribución de claves en cubos hash), pero podría ser O (n) (todo en un hash bucket y devolves a una lista). Uno normalmente esperaría algo entre estos extremos.

De modo que puede tener un rendimiento razonable (O (log n)) todo el tiempo, o necesita asegurarse de que todo esté alineado para obtener un buen rendimiento con un hash.

Al igual que con cualquier pregunta de este tipo: debe medir antes de comprometerse con un enfoque. A menos que sus conjuntos de datos sean grandes, es posible que no haya una diferencia significativa.

Answer 2

Advertencia importante: a menos que haya medido (y su pregunta sugiere que no) que el rendimiento del mapa influye sustancialmente en el rendimiento de la aplicación (se dedica gran parte del tiempo a buscar y actualizar el mapa), no se moleste en hacerlo más rápido. Stick a std::map (o std::unordered_map hash_map o cualquier implementación de hash_map disponible). Acelerar su solicitud en un 1% probablemente no valga la pena. Hazlo libre de errores en su lugar.

Haciéndose eco de la respuesta de Richard: mida el rendimiento con diferentes implementaciones de mapas usando sus clases reales y datos reales.

Algunas notas adicionales:

• Comprender la diferencia entre el costo esperado (los mapas hash generalmente lo tienen más bajo), el peor de los casos (O (logn) para el árbol binario equilibrado pero mucho más alto para el hash map si insert desencadena la reasignación de matriz hash) y el costo amortizado (costo total dividido por número de operaciones o elementos, depende de elementos como la proporción de elementos nuevos y existentes). Necesita averiguar cuál es más restrictivo en su caso. Por ejemplo, la reasignación de mapas hash puede ser demasiado si necesita cumplir con un límite de latencia muy bajo.

• Averigüe dónde está el verdadero cuello de botella. Es posible que el costo de búsqueda en el mapa sea insignificante en comparación con, por ejemplo, el costo de IO.

• Pruebe con una implementación de mapa más especializada. Por ejemplo, se puede ganar mucho si sabes algo más sobre la clave del mapa. Los autores de las implementaciones de mapas genéricos no tienen ese conocimiento.

En su ejemplo (claves enteras sin signo de 32 bits que se agrupan fuertemente, p. Ej., Se asignan de forma secuencial) puede utilizar el enfoque basado en radix. Ejemplo muy simple (amenaza como ilustración, receta no lista para usar):

Item *sentinel[65536]; // sentinel page, initialized to NULLs.
Item (*pages[65536])[65536]; // list of pages,
// initialized so every element points to sentinel

Entonces la búsqueda es tan simple como:

Item *value = pages[index >> 16][index & 0xFFFF];

Cuando necesita establecer un nuevo valor:

if (pages[index >> 16] == sentinel) {
pages[index >> 16] = allocate_new_null_filled_page();
}
pages[index >> 16][index & 0xFFFF] = value;

• Ajusta la implementación de tu mapa.

  • Por ejemplo, a cada hash_map le gusta conocer el número aproximado de elementos por adelantado. Ayuda a evitar la reasignación innecesaria de la tabla hash y (posiblemente) el reajuste de todas las claves.

  • Con mi ejemplo especializado anterior seguramente probará diferentes tamaños de página o una versión de tres niveles.

  • La optimización común proporciona un asignador de memoria especializado para evitar asignaciones múltiples de objetos pequeños.