Costo de usar std :: map con std :: string keys vs int keys?

Question

Sé que las consultas de mapas individuales toman un máximo de tiempo de registro (N). Sin embargo, me preguntaba, he visto muchos ejemplos que usan cadenas como claves de mapa. ¿Cuál es el costo de rendimiento de asociar una std :: cadena como clave de un mapa en lugar de una int por ejemplo?

std::map<std::string, aClass*> someMap; vs std::map<int, aClass*> someMap;

Gracias!

Answer 1

Además de la complejidad de tiempo al comparar cadenas ya mencionadas, una clave de cadena también causará una asignación de memoria adicional cada vez que se agrega un artículo al contenedor. En ciertos casos, p. sistemas altamente paralelos, un mutex de asignador global puede ser una fuente de problemas de rendimiento.

En general, debe elegir la alternativa que tenga más sentido en su situación, y solo optimizar en función de las pruebas de rendimiento reales. Es notoriamente difícil juzgar lo que será un cuello de botella.

Answer 2

La diferencia de costo se vinculará a la diferencia de costo entre la comparación de dos puntos versus la comparación de dos cadenas.

Al comparar dos cadenas, debe desreferenciar un puntero para obtener los primeros caracteres y compararlos. Si son idénticos, debe comparar los segundos caracteres, y así sucesivamente. Si sus cadenas tienen un prefijo común largo, esto puede ralentizar el proceso un poco. Sin embargo, es muy poco probable que sea tan rápido como comparar a los ints.

Answer 3

Por supuesto, el costo se puede comparar en tiempo O (1) real, mientras que las cadenas se comparan en tiempo O (n) (n es el prefijo máximo compartido). Además, el almacenamiento de cadenas consume más espacio que el de los enteros. Aparte de estas diferencias aparentes, no hay un costo de rendimiento importante.

Answer 4

Los algoritmos de análisis para el rendimiento asintótico están trabajando en las operaciones que deben realizarse y el costo que agregan a la ecuación. Para eso, primero debe saber cuáles son las operaciones realizadas y luego evaluar sus costos.

La búsqueda de una clave en un árbol binario equilibrado (qué mapas son) requiere O(log N) operaciones complejas. Cada una de esas operaciones implica comparar la clave de una coincidencia y seguir el puntero apropiado (hijo) si la clave no coincide. Esto significa que el costo total es proporcional a log N veces el costo de esas dos operaciones. Los siguientes punteros son una operación de tiempo constante O(1), y las claves de comparación dependen de la clave. Para una clave entera, las comparaciones son rápidas O(1). La comparación de dos secuencias es otra historia, se necesita un tiempo proporcional al tamaño de las cadenas involucradas O(L) (donde he utilizado intencionadamente L como la longitud de cuerda parámetro en lugar de los más comunes N.

Al sumar todos los cuesta hasta obtener que el uso de números enteros como claves el costo total es O(log N)*(O(1) + O(1)) que es equivalente a O(log N). (O(1) se oculta en la constante de que la notación O esconde en silencio.

Si utiliza cadenas como claves, el costo total es O(log N)*(O(L) + O(1)) donde la operación de tiempo constante se oculta n por la operación lineal más costosa O(L) y se puede convertir en O(L * log N). Es decir, el costo de ubicar un elemento en un mapa marcado por cadenas es proporcional al logaritmo de la cantidad de elementos almacenados en el mapa multiplicado por la longitud promedio de las cadenas utilizadas como claves.

Tenga en cuenta que la notación de big-O es la más adecuada para utilizar como herramienta de análisis para determinar cómo se comportará el algoritmo cuando crece el problema, pero oculta muchos hechos importantes para el rendimiento en bruto.

Como el ejemplo más simple, si cambia la clave de una cadena genérica a una matriz de 1000 caracteres, puede ocultar ese costo dentro de la constante eliminada de la notación. La comparación de matrices de 1000 caracteres es una operación constante que simplemente toma bastante tiempo. Con la notación asintótica que sería simplemente una operación O(log N), como con enteros.

Lo mismo ocurre con muchos otros costos ocultos, como el costo de creación de los elementos que generalmente se considera como una operación de tiempo constante, simplemente porque no depende de los parámetros de su problema (el costo de ubicar el bloque de memoria en cada asignación no depende de su conjunto de datos, sino de la fragmentación de la memoria que está fuera del alcance del análisis de algoritmo, el costo de adquirir el bloqueo dentro de malloc para garantizar que no dos procesos intentan devolver el mismo bloque de memoria depende de la contención del bloqueo que depende del número de procesadores, procesos y la cantidad de solicitudes de memoria que realizan ..., nuevamente fuera del alcance del análisis del algoritmo). Al leer los costos en la notación de la gran O, debes ser consciente de lo que realmente significa.

Answer 5

Antes que nada, dudo que en una aplicación real, ya sea que tenga claves de cadena o teclas de entrada haga una diferencia notable. El perfil de su aplicación le dirá si es importante.

Si sí importa, podría cambiar su clave a ser algo como esto (no probado):

class Key { 
public: 
    unsigned hash; 
    std::string s; 

    int cmp(const Key& other) { 
     int diff = hash - other.hash; 
     if (diff == 0) 
      diff = strcmp(s, other.s); 
     return diff; 
} 

Ahora estamos haciendo una comparación int en los hashes de dos cadenas. Si los hashes son diferentes, las cadenas son ciertamente diferentes. Si los valores hash son iguales, igual debe comparar las cadenas debido al Pigeonhole Principle.

Answer 6

Ejemplo simple con solo acceder a los valores en dos mapas con el mismo número de claves: una clave int otras cadenas de los mismos valores int toma 8 veces más con cadenas.