como es vectorial> “más pesado” que el vector>?

10 minutos de lectura

avatar de usuario
j. cierva

Durante una entrevista reciente, sugerí usar vector<pair<int,int>> sobre vector<vector<int>> ya que solo queríamos almacenar dos valores para cada entrada en el vector. Dije algo con la melodía de “deberíamos usar vector<pair<int,int>> sobre vector<vector<int>> ya que este último es más pesado que el anterior”.

Después de que terminó la sesión de codificación, dijeron que era una buena idea usar pair sobre un vector y me pidieron que explicara qué quería decir con “más pesado” antes. No pude dar más detalles, desafortunadamente. Sí, sé que podemos ingresar solo dos valores en un par, pero muchos más en un vector y ese vector se redimensiona automáticamente cuando su tamaño == capacidad, etc. pero, ¿cómo debería haber respondido a su pregunta? vector<pair<int,int>> mejor que vector<vector<int>>? ¿Qué cosas extra se hacen en este último caso?

  • Un vector tiene que lidiar con un tamaño variable y los datos van al montón. Un par tiene gastos generales cero ya que el tamaño es fijo.

    –Raymond Chen

    24 de julio a las 1:41

  • Menos indirectas, mejor localidad de caché.

    – Borglíder

    24 de julio a las 1:47

  • Si un vector es más pesado que un std::pair, entonces un vector del primero sería más pesado que un vector del segundo.

    –Jeremy Friesner

    24 de julio a las 1:50


  • Con vector<vector<int>> necesita una asignación de memoria dinámica para cada par, además de la asignación para el vector externo. La asignación de memoria dinámica generalmente no es rápida y el resultado puede tener una ubicación de memoria deficiente (los elementos consecutivos pueden no estar cerca uno del otro en la memoria). A la arquitectura informática moderna le gusta acceder a objetos que están cerca de otros objetos a los que ha accedido recientemente, y puede ejecutar órdenes de magnitud más rápido cuando ese es el caso. Con vector<pair<int,int>> todos los elementos son consecutivos, lo que ayudará cuando tenga que trabajar en todo el contenedor.

    – François Andrieux

    24 de julio a las 1:50


  • Además, por lo general incluso sizeof(std::pair<int, int>) < sizeof(std::vector<int>) también, pero esto no es tan importante en comparación con la sobrecarga de tiempo de la asignación dinámica y los problemas de localidad de memoria mencionados en los comentarios anteriores.

    – montón insuficiente

    24 de julio a las 2:00


avatar de usuario
Sam Varshavchik

Cada vector es una sola área contigua de memoria, asignada dinámicamente.

Digamos que tiene 1000 valores con los que trabajará.

std::vector<std::pair<int, int>>

Esto le da un solo bloque de memoria contiguo, para 2000 enteros.

std::vector<std::vector<int>>

Esto le da un solo bloque contiguo de memoria para 1000 vectores.

Cada uno de esos 1000 std::vectors obtiene otro bloque contiguo de memoria por solo dos enteros.

Entonces, en lugar de un solo bloque de memoria contiguo, para esta estructura de datos, consistirá en 1001 bloques de memoria dispersos por todas partes. No tiene garantías, en absoluto, de que todos esos bloques de memoria serán contiguos, uno tras otro.

Cada asignación de memoria dinámica tiene un costo. El costo es bastante pequeño pero se acumula muy, muy rápidamente. Un solo centavo se ignora fácilmente. Mil centavos deberían ser suficientes para comprarte una taza de café en Starbucks.

Además, las CPU modernas son muy, muy buenas para acceder a bloques de memoria contiguos. Iterando sobre un solo bloque contiguo de memoria para sumar dos mil intSerá mucho, mucho más rápido que hacer lo mismo en mil secciones inconexas de la memoria.

  • Una nota sobre los costos. Si ya lo estás haciendo 99 lugares, agregar uno más cuesta relativamente poco. (¡De lo contrario, nadie programaría en Python!) Pero obtener de 3 a 2 errores de rendimiento tiene un gran impacto, y pasar de 2 a 1 es más grande. Y eso último, bueno…

    – btilly

    24 de julio a las 2:07

  • Además de eso, tienes 1000 bloques de control para vector<int> objetos, cada uno de los cuales tiene el tamaño de 3 punteros (en implementaciones normales), apuntando a esas 1000 asignaciones dispersas. En un sistema típico de 64 bits, son 24 bytes de sobrecarga por cada 8 bytes de datos, además de los datos de contabilidad de asignación dinámica, que probablemente sean al menos 8 bytes por asignación. Probablemente más, especialmente en sistemas donde alignof(max_align_t) es 16, por lo que cada asignación está alineada en 16 bytes. Y sí, toda esta indirección es mala para la optimización SIMD en tiempo de compilación, y para las CPU si están realmente dispersas.

    – Peter Cordes

    24 de julio a las 23:41

avatar de usuario
Chepner

Puede responder esto sin hacer referencia a ningún idioma en particular. los problema llamado para almacenar una secuencia de 2 tuplas. Su tipo elegido debe ser capaz de almacenar 2 tuplas, por supuesto, pero también ser incapaz de almacenar tuplas de otros tamaños. Entonces, dados dos tipos que son capaces de almacenar los valores deseados, prefiera el que es menos capaz de almacenar valores no deseados.

vector<int> le permitiría almacenar vectores de 2 elementos, pero también vectores vacíos, vectores singleton, vectores de 3 elementos, vectores de 4 elementos, etc. pair<int,int> es más precisoya que solo puede almacenar exactamente dos valores

(Sin descartar los beneficios de rendimiento mencionados en la respuesta aceptada, solo para proporcionar un argumento puramente semántico para usar tipos precisos).

  • Exactamente. El rendimiento es mejor porque los tipos son más precisos, por lo que podemos usar algoritmos y estructuras de datos más específicos en lugar de otros de uso más general (por ejemplo, simplemente almacenar dos números enteros en lugar de almacenar un puntero a una matriz de números enteros arbitrarios). El uso de tipos más precisos también expresa mejor la intención.

    – Smiley1000

    24 de julio a las 13:29

  • std::array<int,2> también habría estado totalmente bien y realizado lo mismo, ya que contiene los valores dentro del array objeto en sí mismo, no punteros a ellos. (La misma representación de objeto que std::pair<int,int>). Su argumento se aplica igualmente a él; la ,2 el tamaño es parte del tipo, no de datos variables en tiempo de ejecución. Así que aunque std::array en general puede contener cualquier número de enteros, esa instanciación de la plantilla puede contener exactamente dos, igual que un pair. (Y ambos tienen que ser del mismo tipo, mientras que un pair admite diferentes tipos. Pero pair<int,int> no.)

    – Peter Cordes

    24 de julio a las 23:52


Como otros mencionaron, std::vector<int> añade por ejemplo un contador del número de elementos.

Pero un aspecto interesante que podrías haber sugerido en la entrevista sería usar std::array<int, 2>. debe tener un costo similar std::pair<int, int> ya que almacenará los números en una matriz de tamaño fijo. Una ventaja sería la API, que permite utilizar a[0] en vez de a.first y también es más fácil generalizar cuando es posible que necesite almacenar, por ejemplo, tres valores por entrada después de agregar algunas características nuevas.

  • Sí, y una implementación normal tendrá la misma representación de objeto que std::pair<int,int>, y debe compilarse exactamente con el mismo asm. Use el que sea semánticamente más significativo para su caso de uso; foo[i][0] y foo[i][1] es bueno si los dos enteros tienen significados similares; foo[i].first / .second es tal vez bueno si son diferentes. O podría usar una clase enum o wrapper para dar nombres significativos a los índices de la matriz. (O probablemente solo use una estructura personalizada en lugar de pair<> o array<> si quieres tener nombres de miembros significativos!)

    – Peter Cordes

    24 de julio a las 23:57


  • La ventaja de foo.second y std::get<1>(foo) sobre foo[1] es que el primero se comprueba en busca de oob en tiempo de compilación, mientras que foo[1] puede ser oob en tiempo de ejecución. También puedes simplemente usar std::tuple si desea extender más tarde.

    – ÁTOMO

    el dia de ayer

avatar de usuario
nutax

Para simplificar la explicación, digamos que

  • A[ a | b ] B[ c ] medio: a y b están en trozo A y c en trozo b
  • Los fragmentos aquí son piezas continuas de memoria, por lo que a está cerca de b

Con eso en mente, veamos un ejemplo: el uso de memoria de { { 1, 1 } , { 2, 2 }, ... }

Para std::vector<<std::vector<int>>

  • A[ size info | ptr to B ]
  • B[ [ size info | ptr to C ] | [ size info | ptr to D ] | ... ]
  • C[ 1 | 1 ]
  • D[ 2 | 2 ]

Para std::vector<std::pair<int, int>>

  • A[ size info | ptr to B ]
  • B[ [ 1 | 1 ] | [ 2 | 2 ] | ... ]

Creo que el ejemplo es muy claro: hay una capa de indirección menos al hacer std::vector<std::pair<int, int>>. Sentido

  1. Hay menos memoria consumo (no necesita variables adicionales para el tamaño y un puntero a un fragmento para cada elemento).
  2. Para obtener un valor deseado que haría menos pasos (de lo contrario, primero tendría que cargar y leer el puntero y luego con esa dirección cargar el valor deseado).

Un vector es una matriz de cambio de tamaño dinámico. Sacrifica algo de rendimiento para obtener la capacidad de cambiar el tamaño dinámicamente.

Un vector de vectores (vector<vector<int>>) tiene esa sobrecarga de rendimiento tanto para el vector externo como para cada uno de sus elementos. Con un vector de pares (vector<pair<int, int>>), no tienes este último. Un par siempre tiene un tamaño fijo, por lo que no debe preocuparse por tener que cambiar su tamaño según sea necesario (y reubicarlo en otra posición en la memoria si es necesario).

avatar de usuario
CaronteX

Mi respuesta “simple” / “ingenua” sería:

A vector<pair<int, int>> sabe que siempre serán pares enteros, por lo que puede asignar memoria en consecuencia (por ejemplo, cuando el vector cambia de tamaño), posible en un fragmento continuo. Además, solo necesita realizar un seguimiento de que almacena X pares de enteros, lo que permite un acceso rápido a esos enteros y mantiene la sobrecarga al mínimo. Finalmente, con esa información disponible en tiempo de compilación, el compilador puede (posiblemente) optimizar mejor el código.

A vector<vector<int>> necesita poder almacenar X veces * cualquier número de int. Es probable que el vector externo solo almacene las direcciones del vector interno (para facilitar el acceso rápido), lo que significa que es probable que sus datos estén dispersos por toda la memoria. Además, los vectores internos deben realizar un seguimiento de la cantidad de enteros que contienen (aunque este número siempre debe ser dos), lo que agrega una sobrecarga innecesaria tanto para almacenar como para acceder a los enteros. Finalmente, el compilador puede hacer menos suposiciones sobre la estructura de sus datos, lo que reduce el potencial de optimizaciones.

avatar de usuario
bill weinmann

Puedes usar un pair si necesita alguna de sus funciones u operadores miembros. De lo contrario, un simple struct podría ser incluso encendedor:

struct payload {
    int a {};
    int b {};
};

std::vector<payload> x { {1, 2}, {3, 4} };

Al usar STL, puede ser fácil olvidar que aún podemos usar primitivas y que a menudo son más eficientes.

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad