second - vector c++
std:: pair<int, int> vs struct con dos int (5)
En un ejemplo de ACM, tuve que construir una tabla grande para la programación dinámica. Tuve que almacenar dos enteros en cada celda, así que decidí ir por un std::pair<int, int> . Sin embargo, la asignación de una gran variedad de ellos tomó 1.5 segundos:
std::pair<int, int> table[1001][1001];
Después, he cambiado este código a
struct Cell {
int first;
int second;
}
Cell table[1001][1001];
y la asignación tomó 0 segundos.
¿Qué explica esta enorme diferencia en el tiempo?
Estas son todas buenas suposiciones, pero como todos saben, las suposiciones no son confiables.
Yo diría que solo pause aleatoriamente dentro de esos 1,5 segundos, pero tendría que ser bastante rápido. Si aumentara cada dimensión en un factor de aproximadamente 3, podría hacer que tomara más de 10 segundos, por lo que sería más fácil pausar.
O bien, puede obtenerlo bajo un depurador, dividirlo en el código del constructor de pares y, luego, en un solo paso para ver qué está haciendo.
De cualquier manera, obtendría una respuesta firme a la pregunta, no solo una suposición.
Las respuestas hasta ahora no explican la magnitud total del problema.
Como Sharptooth ha señalado, la solución de par inicializa los valores a cero. Como señaló Lemurik, la solución de par no es solo inicializar un bloque de memoria contiguo, sino que está llamando al constructor de par para cada elemento de la tabla. Sin embargo, incluso eso no tiene en cuenta que tarda 1,5 segundos. Algo más está sucediendo.
Aquí está mi lógica:
Suponiendo que estuvieras en una máquina antigua, digamos que correr a 1.33ghz, entonces 1.5 segundos son 2e9 ciclos de reloj. Tienes 2e6 pares para construir, así que de alguna manera cada constructor de pares está tomando 1000 ciclos. No se necesitan 1000 ciclos para llamar a un constructor que solo establece dos enteros en cero. No puedo ver cómo los fallos de caché harían que tomara tanto tiempo. Me lo creería si el número fuera inferior a 100 ciclos.
Pensé que sería interesante ver a dónde van todos estos ciclos de CPU. Utilicé el compilador C ++ más antiguo que pude encontrar para ver si podía alcanzar el nivel de desperdicio requerido. Ese compilador fue VC ++ v6. En el modo de depuración, hace algo que no entiendo. Tiene un gran bucle que llama al constructor de pares para cada elemento de la tabla, lo suficientemente justo. Ese constructor establece los dos valores en cero, lo suficientemente justo. Pero justo antes de hacer eso, establece todos los bytes en una región de 68 bytes en 0xcc. Esa región está justo antes del inicio de la gran mesa. Luego sobrescribe el último elemento de esa región con 0x28F61200. Cada llamada del constructor de pares repite esto. Es de suponer que este es un tipo de contabilidad por parte del compilador, por lo que sabe qué regiones se inicializan cuando se comprueban los errores de puntero en el tiempo de ejecución. Me encantaría saber exactamente para qué es esto.
De todos modos, eso explicaría a dónde va el tiempo extra. Obviamente, otro compilador puede no ser tan malo. Y, ciertamente, una versión de lanzamiento optimizada no lo sería.
Supongo que es la forma en que se crea std :: pair. Hay más sobrecarga durante la invocación de un constructor de pares 1001x1001 veces que cuando simplemente asigna un rango de memoria.
es realmente un buen ejemplo de cómo se debe escribir C ++ y usar STL con cuidado. ¿Alguna idea?
mi proyecto está trabajando en una herramienta de prueba de referencia de nivel de código C & C ++ en la que haremos muchos ejemplos de código para descubrir qué es el código "bueno" y qué es un hábito de codificación "malo". visite http://effodevel.googlecode.com para obtener más información sobre C9B.M. planificación. Si ha experimentado muchos de estos casos, únase al proyecto para ayudarnos.
std::pair<int, int>::pair() constructor std::pair<int, int>::pair() inicializa los campos con valores predeterminados (cero en el caso de int ) y su struct Cell no (ya que solo tiene un constructor predeterminado generado automáticamente que no hace nada) .
La inicialización requiere escribir en cada campo, lo que requiere una gran cantidad de accesos a la memoria que requieren relativamente mucho tiempo. Con struct Cell no se hace nada y hacer nada es un poco más rápido.