programacion - que es un map en c++

confusión de rendimiento de vector vs mapa

Question

edición: estoy comparando específicamente las operaciones de búsqueda lineal de std::vector las operaciones de búsqueda binaria de std::map porque eso es lo que la reclamación de Herb parecía relacionar. Sé que usar una búsqueda binaria moverá el rendimiento de O (N) a O (registro N), pero eso no estaría probando la afirmación de Herb

Bjarne Stroustrup y Herb Sutter han hablado recientemente acerca de lo increíble que es std::vector en situaciones en las que uno esperaría que se usara std::list , debido al costo de las fallas de caché durante el recorrido de la lista enlazada. (vea http://channel9.msdn.com/Events/Build/2014/2-661 en la marca de 48 minutos)

Sin embargo, Herb hizo una declaración adicional de que las operaciones en un vector ordenado eran incluso más rápidas que std::map , (ver http://i.imgur.com/zX07TZR.png tomadas de la marca 51:30 del video del canal 9 anterior) que Me pareció difícil de entender. Así que creé una pequeña prueba para demostrar esto y tuve dificultades para reproducir estos resultados: https://ideone.com/MN7DYK

Este es el código de prueba:

template <typename C>
void test(std::string name, std::vector<int> shuffledInputValues, C & c)
{
   // fill container ''c'' with values from ''shuffledInputValues'' then erase them all
   {
      std::cout << "testing " << name << "..." << std::endl;
      timer t;

      for (auto val : shuffledInputValues) insert(c, val);
      for (auto val : shuffledInputValues) remove(c, val);
  }
}

// output:
// testing vector...99.189ms
// testing deque...120.848ms
// testing set...4.077ms

Observe cómo el std::vector realiza un orden de magnitud más lento que std::set . Por supuesto, este es el resultado que esperaba, pero estoy confundido acerca de la afirmación que Herb estaba tratando de hacer.

¿Qué estoy haciendo mal? ¿O estoy malinterpretando la afirmación de Herb?

Notas sobre mi aplicación de prueba:

• debe utilizar operaciones lineales: todo el objetivo del ejercicio es demostrar la magia de la memoria caché de la CPU, estas son las restricciones que Herb y Bjarne ponen en el ejercicio.
• No traté de desentrañar ningún bucle complicado para mi iteración vectorial, pero creo que la iteración no está afectando el rendimiento de ninguna manera
• Limité el bucle a 10K artículos porque ideone agota el tiempo de espera en conjuntos más grandes, pero aumentar el tamaño no cambia los resultados

edición: consulte https://ideone.com/916fVd para ver un ejemplo modificado que solo compara el rendimiento de las búsquedas. La búsqueda lineal exhibe el mismo rendimiento.

Answer 1

Encontré las slides para una referencia más fácil (no puedo ver gráficos, pero supongo que podría deberse a un formato de archivo propietario). Una diapositiva relevante es el número 39 que describe el problema que se está resolviendo:

§ Genere N enteros aleatorios e insértelos en una secuencia para que cada uno se inserte en su posición correcta en el orden numérico.

§ Eliminar elementos uno a uno seleccionando una posición aleatoria en la secuencia y eliminando el elemento allí.

Ahora, debería ser bastante obvio que una lista vinculada no es una buena opción para este problema. Aunque una lista es mucho mejor que el vector para insertar / eliminar al principio o en el medio, no es buena para insertar / eliminar en una posición aleatoria debido a la necesidad de una búsqueda lineal. Y la búsqueda lineal es mucho más rápida con los vectores debido a una mejor eficiencia de caché.

Sutter sugiere que un mapa (o un árbol en general) parecería una opción natural para este algoritmo porque obtienes una búsqueda O (log n). Y, de hecho, supera al vector con bastante facilidad para valores de N grandes en la parte de inserción.

Aquí viene el pero . Es necesario eliminar el elemento nth (para n aleatorio). Aquí es donde creo que su código está haciendo trampa. Se eliminan los elementos en el orden en que se insertaron, utilizando efectivamente el vector de entrada como una tabla de búsqueda para encontrar el valor de un elemento en una posición "aleatoria" para que pueda buscarlo en O (log n). Así que realmente estás usando una combinación de conjunto y un vector para resolver el problema.

Un árbol de búsqueda binario regular como el que se usa para std::map o std::set (que supongo que utilizó Sutter) no tiene un algoritmo rápido para encontrar el elemento nth. Aquí hay uno que se dice que es O (log n) en promedio y O (n) en el peor de los casos. Pero std::map y std::set no brindan acceso a la estructura de árbol subyacente, por lo tanto, para aquellos con los que está atrapado en el recorrido en el orden (corríjame si me equivoco), ¡es una búsqueda lineal nuevamente! De hecho, me sorprende que la versión del mapa compita con la del vector en los resultados de Sutter.

Para la complejidad de log (n), necesita una estructura como el árbol de estadísticas de orden que desafortunadamente no es proporcionada por la biblioteca estándar. Hay un STL MAP basado en políticas de GNU como se muestra here .

Aquí hay un código de prueba rápida que hice para vector vs set vs ost (vs vector con búsqueda binaria para una buena medida) https://ideone.com/DoqL4H conjunto es mucho más lento mientras que la otra estructura basada en árboles es más rápida que el vector, que no está en línea con los resultados de Sutter.

order statistics tree: 15.958ms
vector binary search: 99.661ms
vector linear search: 282.032ms
set: 2004.04ms

(N = 20000, la diferencia solo será mayor a favor de los valores más altos)

En resumen, llegué a la misma conclusión de que los resultados originales de Sutter parecen extraños, pero por una razón ligeramente diferente. Me parece que una mejor complejidad asintótica gana factores constantes más bajos esta vez.

Tenga en cuenta que la descripción del problema no excluye la posibilidad de valores aleatorios duplicados, por lo que usar map / set en lugar de multimap / multiset es engañar un poco en favor de map / set, pero asumo que tener poco significado cuando dominio de valores es mucho más grande que N Además, la reserva previa del vector no mejora significativamente el rendimiento (alrededor del 1% cuando N = 20000).

Answer 2

Por supuesto, es difícil dar una respuesta precisa en ausencia de código fuente más información sobre las opciones del compilador, el hardware, etc.

Un par de posibles diferencias:

• Creo que el hablante habla de inserciones / eliminaciones en el medio del vector cada vez (mientras que siempre agrega al final y elimina desde el principio en su ejemplo);
• El orador no menciona cómo determinar qué elementos se agregan o eliminan, pero en ese caso también podemos suponer que se hace el mínimo esfuerzo para determinar esto: usted hace un acceso vectorial cada vez, mientras que los valores de inserción pueden simplemente ser calculado (por ejemplo, usar un PNRG de bajo costo para determinar el siguiente valor para insertar) o ser siempre el mismo, y para la eliminación, el elemento central se elimina cada vez, por lo que no es necesario buscar / calcular un valor.

Sin embargo, como lo mencionó otro comentarista, eliminaría el principio general en lugar de los números / tiempos específicos. Esencialmente, el mensaje para llevar es: lo que pensaba que sabía acerca de las "operaciones de conteo" para evaluar el rendimiento / escalabilidad del algoritmo ya no es cierto en los sistemas modernos.