¿Por qué el vector es más rápido que el mapa en una prueba, pero no en la otra?

Question

Siempre me han dicho que los vectores son rápidos, y en mis años de experiencia en programación, nunca he visto nada para contraer eso. Decidí (optimizar prematuramente y escribir) una clase asociativa que era un contenedor delgado alrededor de un contenedor secuencial (es decir, ::std::vector y proporcionaba la misma interfaz que ::std::map. La mayoría del código era realmente fácil, y lo conseguí trabajando con poca dificultad.

Sin embargo, en mis pruebas de varios tipos de tamaño de POD (de 4 a 64 bytes), y std::strings, con recuentos que varían de ocho a dos mil, ::std::map::find era más rápido que mi ::associative::find, generalmente alrededor de 15% más rápido, para casi todas las pruebas Hice un Short, Self Contained, Correct (Compilable), Example que muestra claramente esto at ideone Comprobé la implementación de MSVC9 de ::std::map::find y confirmé que coincide con mi código vecfind y ::std::lower_bound bastante de cerca, y no puedo explicar por qué el ::std::map::find funciona más rápido, excepto por una discusión sobre Stack Overflow donde las personas especulaban que el método de búsqueda binario no se beneficia en absoluto de la localidad del vector hasta la última comparación (lo que hace que no sea más rápido), y que requiere punteros aritméticos que ::std::map nodos no requiere, por lo que es más lento.

Hoy alguien me desafió en esto, y proporcionó this code at ideone, que cuando probé, mostró que el vector era más de dos veces más rápido.

¿Los codificadores de StackOverflow quieren aclararme sobre esta aparente discrepancia? Revisé ambos conjuntos de códigos y me parecen euqivalentes, pero tal vez estoy ciego por jugar tanto con los dos.

(Nota: esto es muy cerca a one of my previous questions, pero mi código tenido varios errores que fueron abordadas Debido a la nueva información/código, me pareció que era lo suficientemente diferentes como para justificar una pregunta separada Si no, I'.. . ll trabajo en la fusión de ellos)

Answer 1

Veo algunos problemas con el código (http://ideone.com/41iKt) que ha publicado en ideone.com. (ideone en realidad muestra vector como más rápido, pero una compilación local con Visual Studio 11 Developer Preview muestra map más rápido).

En primer lugar me movía la variable mapa y lo utilizó para inicializar el vector para obtener la misma ordenación de elementos y uniquing, y entonces me di lower_bound un comparador personalizado que sólo compara first, ya que eso es lo que va a hacer un mapa. Después de estos cambios Visual Studio 11 muestra el vector como más rápido para los mismos 100.000 elementos (aunque el tiempo ideone no cambia significativamente). http://ideone.com/b3OnH

Con test_size reducido a 8, el mapa es aún más rápido. Esto no es sorprendente porque esta es la forma en que funciona la complejidad del algoritmo, todas las constantes en la función que realmente describen el tiempo de ejecución con N pequeña. Tengo que elevar test_size a aproximadamente 2700 para que el vector lo saque y luego delante del mapa en este sistema.

Answer 2

Un ordenadas std :: vector tiene dos ventajas sobre std :: mapa:

• mejores datos localidad: tiendas de todos los datos vectoriales contigua en memoria
• más pequeña huella de memoria: vector no necesita mucha contabilidad da ta (p. ej., no hay objetos de nodo de árbol)

Si estos dos efectos importan dependen del escenario. Hay dos factores que pueden tener un gran impacto:

Tipo de datos

Es una ventaja para el std :: vector si los elementos son tipos primitivos como enteros. En ese caso, la localidad realmente ayuda porque todos los datos necesarios para la búsqueda se encuentran en una ubicación contigua en la memoria.

Si los elementos son say strings, entonces la localidad no ayuda mucho. La memoria vectorial contigua ahora solo almacena objetos de punteros que están potencialmente en todo el montón.

Tamaño de los datos

Si el std :: vector encaja en un nivel de caché particular, pero el std :: mapa no lo hace, el std :: vector tendrá una ventaja. Esto es especialmente el caso si repite la prueba con los mismos datos.

Answer 3

¿Qué te parece que mapfind() es más rápido que vecfind()?

La salida de ideone para su código informa aproximadamente un 50% más de tics para mapfind() que para vecfind(). Ejecutar el código aquí (x86_64 linux, g ++ - 4.5.1), mapfind() tarda aproximadamente el doble que vecfind().

Haciendo el mapa/vector más grande por un factor de 10, la diferencia aumenta a aproximadamente 3 ×.

Sin embargo, tenga en cuenta que la suma de los segundos componentes es diferente. El mapa contiene solo un par con cualquier primer componente dado (con mi PRNG local, que crea un mapa con dos elementos cortos), mientras que el vector puede contener múltiples pares de este tipo.

Answer 4

El número de elementos que está colocando en su contenedor de prueba es más que el número de resultados posibles de rand() en Microsoft, por lo que obtendrá números repetidos. El vector ordenado contendrá todos ellos, mientras que el map arrojará los duplicados. Verifique los tamaños después de llenarlos: el vector tendrá 100000 elementos, el mapa 32768. Como el mapa es mucho más corto, tendrá un mejor rendimiento.

Pruebe multimap para una comparación de manzanas a manzanas.