punteros - ¿Por qué deque usa mucha más memoria RAM que vector en C++?

matrices en c (5)

Deque puede tener una sobrecarga de memoria adicional sobre el vector porque está compuesta de unos pocos bloques en lugar de uno contiguo.

Desde en.cppreference.com/w/cpp/container/deque :

A diferencia de std::vector , los elementos de un deque no se almacenan contiguamente: las implementaciones típicas utilizan una secuencia de matrices de tamaño fijo asignadas individualmente.

Tengo un problema en el que estoy trabajando donde necesito usar algún tipo de matriz bidimensional. La matriz es de ancho fijo (cuatro columnas), pero necesito crear filas adicionales sobre la marcha.

Para hacer esto, he estado usando vectores de vectores, y he estado usando algunos bucles anidados que contienen esto:

array.push_back(vector<float>(4)); array[n][0] = a; array[n][1] = b; array[n][2] = c; array[n][3] = d; n++

para agregar las filas y sus contenidos. El problema es que parece que me estoy quedando sin memoria con la cantidad de elementos que estaba intentando crear, así que reduje el número que estaba usando. Pero luego comencé a leer acerca de deque, y pensé que me permitiría usar más memoria porque no tiene que ser contigua. Cambié todas las menciones de "vector" a "deque", en este ciclo, así como a todas las declaraciones. Pero luego me pareció que se me había agotado la memoria nuevamente, esta vez incluso con la cantidad reducida de filas.

Miré cuánta memoria está usando mi código, y cuando estoy usando deque, la memoria aumenta continuamente a más de 2GB, y el programa se cierra poco después, incluso cuando se usa la menor cantidad de filas. No estoy seguro exactamente en qué punto de este ciclo se queda cuando se queda sin memoria.

Cuando uso vectores, el uso de la memoria (para el mismo número de filas) aún está por debajo de 1 GB, incluso cuando el ciclo sale. Luego pasa a un bucle similar donde se agregan más filas, y solo alcanza alrededor de 1,4 GB.

Entonces mi pregunta es ¿Es normal que deque use más del doble de la memoria del vector, o estoy asumiendo erróneamente que puedo reemplazar la palabra "vector" por "deque" en las declaraciones / inicializaciones y el código anterior?

Gracias por adelantado.

Estoy usando: MS Visual C ++ 2010 (32 bits) Windows 7 (64 bits)

El problema principal es que se está quedando sin memoria.

Entonces, ¿necesitas todos los datos en la memoria a la vez?
Quizás nunca puedas lograr esto.

Procesamiento parcial

Es posible que desee considerar el procesamiento de los datos en "trozos" o submatrices más pequeñas. Por ejemplo, usando la grilla rectangular estándar:

Lee los datos del primer cuadrante.
Procesar los datos del primer quandrant.
Almacenar los resultados (en un archivo) del primer quandrant.
Repita para los quandrants restantes.

buscando

Si está buscando una partícula o un conjunto de datos, puede hacerlo sin leer todo el conjunto de datos en la memoria.

Asignar un bloque (matriz) de memoria.
Lea una porción de los datos en este bloque de memoria.
Busque el bloque de datos.
Repita los pasos 2 y 3 hasta que se encuentren los datos.

Transmisión de datos

Si su aplicación recibe los datos brutos de una fuente de entrada (que no sea un archivo), querrá almacenar los datos para su posterior procesamiento.

Esto requerirá más de un buffer y es más eficiente usando al menos dos hilos de ejecución.

El hilo de lectura leerá datos en un búfer hasta que el búfer esté lleno. Cuando el buffer está lleno, leerá los datos en otro vacío.

El hilo de escritura inicialmente esperará hasta que el primer buffer de lectura esté lleno o la operación de lectura haya finalizado. A continuación, el subproceso de escritura retira los datos del búfer de lectura y los escribe en un archivo. El hilo de escritura luego comienza a escribir desde el siguiente buffer de lectura.

Esta técnica se llama Doble Buffering o Multiple Buffering.

Escasa información

Si hay una gran cantidad de datos cero o no utilizados en la matriz, debe intentar usar Matrices dispersas. Básicamente, esta es una lista de estructuras que contienen las coordenadas de los datos y el valor. Esto también funciona cuando la mayoría de los datos es un valor común distinto de cero. Esto ahorra mucho espacio de memoria; pero cuesta un poco más de tiempo de ejecución.

Compresión de datos

También puede cambiar sus algoritmos para usar la compresión de datos. La idea aquí es almacenar la ubicación de datos, el valor y el número o valores iguales contiguos (también conocidos como ejecuciones). Por lo tanto, en lugar de almacenar 100 puntos de datos consecutivos del mismo valor, almacenaría la posición de inicio (de la ejecución), el valor y 100 como la cantidad. Esto ahorra mucho espacio, pero requiere más tiempo de procesamiento al acceder a los datos.

Archivo de memoria asignada

Hay bibliotecas que pueden tratar un archivo como memoria. Esencialmente, leen en una "página" del archivo en la memoria. Cuando las solicitudes salen de la "página", leen en otra página. Todo esto se realiza "detrás de escena". Todo lo que necesita hacer es tratar el archivo como la memoria.

Resumen

Las matrices y deques no son su principal problema, la cantidad de datos es. Su problema principal se puede resolver procesando pequeños datos a la vez, comprimiendo el almacenamiento de datos o tratando los datos en el archivo como memoria. Si está tratando de procesar datos de transmisión, no lo haga. Idealmente, los datos de transmisión deberían colocarse en un archivo y luego procesarse más tarde. Un propósito histórico de un archivo es contener datos que no se ajustan a la memoria.

La respuesta real aquí tiene poco que ver con la estructura de datos básicos. La respuesta es que la implementación de MSDC de std :: deque es especialmente horrible y degenera en una serie de punteros a elementos individuales, en lugar de la matriz de matrices que debería ser. Francamente, solo dos veces el uso de la memoria del vector es sorprendente. Si tuvieras una mejor implementación de deque obtendrías mejores resultados.

Todo depende de la implementación interna de deque (no hablaré de vector ya que es relativamente sencillo).

El hecho es que deque tiene garantías completamente diferentes que el vector (la más importante es que admite la inserción de O (1) en ambos extremos mientras que el vector solo admite la inserción de O (1) en la parte posterior). Esto a su vez significa que las estructuras internas manejadas por deque tienen que ser más complejas que vector .

Para permitir eso, una implementación deque típica dividirá su memoria en varios bloques no contiguos. Pero cada bloque de memoria individual tiene una sobrecarga fija para permitir que la administración de la memoria funcione (por ejemplo, cualquiera que sea el tamaño del bloque, el sistema puede necesitar otros 16 o 32 bytes o lo que sea, además, solo para la contabilidad). Dado que, a diferencia de un vector , un deque requiere muchos bloques pequeños e independientes, las acumulaciones de arriba pueden explicar la diferencia que se ve. También tenga en cuenta que esos bloques de memoria individuales necesitan ser administrados (¿tal vez en estructuras separadas?), Lo que probablemente también significa una (o mucha) sobrecarga adicional.

En cuanto a una forma de resolver su problema, puede intentar lo que @BasileStarynkevitch sugirió en los comentarios, esto de hecho reducirá el uso de su memoria, pero le llevará solo hasta cierto punto porque en algún punto aún se quedará sin memoria. ¿Y qué pasa si intenta ejecutar su programa en una máquina que solo tiene 256 MB de RAM? Cualquier otra solución cuyo objetivo sea reducir la huella de su memoria mientras se intenta mantener todos sus datos en la memoria sufrirá los mismos problemas.

Una solución adecuada al manejar conjuntos de datos grandes como el suyo sería adaptar sus algoritmos y estructuras de datos para poder manejar particiones pequeñas en un momento de su conjunto de datos completo, y cargar / guardar esas particiones según sea necesario para hacer espacio para el otras particiones. Desafortunadamente, dado que probablemente significa acceso al disco, también significa una gran caída en el rendimiento, pero bueno, no puedes comer el pastel y tenerlo también.

Teoría

Existen dos formas comunes de implementar eficientemente una deque: ya sea con una matriz dinámica modificada o con una lista doblemente vinculada .

La matriz dinámica modificada que se utiliza es básicamente una matriz dinámica que puede crecer desde ambos extremos, a veces llamados deques de matriz . Estos deques de matriz tienen todas las propiedades de una matriz dinámica, como acceso aleatorio de tiempo constante , buena ubicación de referencia e inserción / eliminación ineficiente en el medio, con la adición de inserción / eliminación de tiempo constante amortizada en ambos extremos, en lugar de de solo un extremo.

Hay varias implementaciones de matriz dinámica modificada:

Asignando contenido deque desde el centro de la matriz subyacente y redimensionando la matriz subyacente cuando se llega a cualquiera de los extremos. Este enfoque puede requerir redimensionamientos más frecuentes y perder más espacio , especialmente cuando los elementos solo se insertan en un extremo .
Almacenar contenido deque en un buffer circular, y solo cambiar el tamaño cuando el buffer se llena. Esto disminuye la frecuencia de los redimensionamientos.
Almacenar contenidos en múltiples matrices más pequeñas, asignando matrices adicionales al principio o al final según sea necesario. La indexación se implementa manteniendo una matriz dinámica que contiene punteros a cada una de las matrices más pequeñas.

Conclusión

Diferentes bibliotecas pueden implementar deques de diferentes maneras, pero generalmente como una matriz dinámica modificada . Lo más probable es que su biblioteca estándar utilice el enfoque n. ° 1 para implementar std::deque , y como usted agrega elementos solo desde un extremo , en última instancia, perderá mucho espacio . Por esa razón, es una ilusión que std::deque ocupe más espacio de lo habitual std::vector .

Además, si std::deque se implementara como una lista doblemente enlazada, eso daría como resultado un desperdicio de espacio también, ya que cada elemento necesitaría acomodar 2 punteros además de sus datos personalizados.

La implementación con el enfoque n. ° 3 (enfoque de matriz dinámica modificada también) daría como resultado una pérdida de espacio para acomodar metadatos adicionales, como punteros a todas esas matrices pequeñas.

En cualquier caso, std::deque es menos eficiente en términos de almacenamiento que simple std::vector . Sin saber qué es lo que quiere lograr, no puedo sugerir con confianza qué estructura de datos necesita. Sin embargo, parece que ni siquiera sabes para qué son los deques, por lo tanto, lo que realmente quieres en tu situación es std::vector . Deques, en general, tienen diferentes aplicaciones.