1

Estoy trabajando con una estructura de datos que básicamente es una matriz en 4D (Para ello estoy utilizando vectores de la STL). La leo de un archivo y las dimensiones suelen ser distintas, por ejemplo la que estoy intentando leer ahora es de 192x256x128x96. En el siguiente fragmento de código intento rellenar con 0's hasta que la matriz sea de orden NxNxNxN siendo N el tamaño de la dimensión de mayor tamaño (en el ejemplo que he puesto sería 256).


while(matriz.size() < width)   //width es el tamaño de N
{
    vector<vector<vector<short>>> aux;
    matriz.push_back(aux);
}

for(auto i = 0; i < matriz.size(); i++)
{
    while(matriz[i].size() < width)
    {
        vector<vector<short>> aux;
        matriz[i].push_back(aux);
    }
}


for(auto i = 0; i < matriz.size(); i++)
    for(auto j = 0; j < matriz[i].size(); j++)
        while(matriz[i][j].size() < width)
        {
            vector<short> aux;
            matriz[i][j].push_back(aux);
        }   
            


for(auto i = 0; i < matriz.size(); i++) 
    for(auto j = 0; j < matriz[i].size(); j++)
        for(auto k = 0; k < matriz[i][j].size(); k++)  
            while(matriz[i][j][k].size() < width)  
            {
                matriz[i][j][k].push_back(0);
            }
                

Este código funciona sin problemas para matrices pequeñas-medianas (He probado hasta matrices de orden 200x200x200x200). Pero con la matriz que necesito analizar (la que comentaba anteriormente de 256x256x256x256) me es imposible, el ordenador se queda colgado y no responde.

Teniendo en cuenta que mi ordenador tiene 12GB de RAM y que (si mis cálculos no fallan) la estructura de datos es de 8GB ya que los short ocupan 2B, la RAM no debería ser el problema, pero debido al estado en el que se queda el ordenador al ejecutar el programa con la matriz de 256x256x256x256 es la única explicación que encuentro.

¿Alguien podría darme una solución, o sabría decirme si efectivamente el problemas es debido a la capacidad de la memoria?

He probado a ejecutar el mismo programa en un ordenador con Windows y 16 GB de RAM y el rendimiento ha sido incluso peor porque no ha llegado a funcionar si quiera con la matriz 200x200x200x200. No se si esto se debe a que Windows haga una peor gestión de la memoria o algo por el estilo.

3
  • 1
    la RAM no debería ser el problema ... si fuera toda exclusivamente para ti. La RAM se comparte entre el SO, todos los programas en ejecución, los datos de todos ellos ... + los componentes hardware que la necesiten. ¿ El proceso que has de ralizar no es posible manteniendo los datos en disco ?
    – Juanjo
    Commented el 10 feb. 2021 a las 19:06
  • Tengo que ir cogiendo submatrices de dicha matriz, ¿cómo podría coger dichas submatrices sin tener toda la estructura de datos en la RAM? Además en la última iteración compruebo la matriz al completo así que si necesitaría toda la estructura en la RAM Commented el 10 feb. 2021 a las 19:10
  • Pues no tengo ni idea, porque no se lo que es coger submatrices de una matriz. Pero la RAM y un disco es exactamente lo mismo: posiciones contiguas en las que almacenar elementos; vamos, que ambas cosas son matrices de 1 sola dimensión. Si tu algoritmo es aplicable en RAM, también lo es en disco, salvando las diferencias de velocidad.
    – Juanjo
    Commented el 10 feb. 2021 a las 19:22

1 respuesta 1

3

El problema surge de tu elección de contenedor.


El std::vector garantiza memoria anexa, pero también garantiza crecimiento dinámico. Para que este contenedor cumpla con sus garantías, tiene que hacer algunos trucos:

  • Cada vez que necesita más espacio, puede necesitar realojar datos de una posición de memoria a otra.
  • Para evitar la mayor parte de realojamientos, suele reservar más memoria de la que está realmente usando.

Así pues, cada vez que llamas a vector::push_back, el contenedor hace lo siguiente:

  1. Comprueba si tiene espacio reservado para alojar el nuevo dato.
    • Si no tiene espacio, intenta reservar más espacio anexo.
      • Si no puede reservar espacio anexo, reserva otro espacio.
        • Mueve los datos a la nueva posición.
      • Si puede reservar espacio anexo, agranda el espacio reservado.
  2. Si tiene espacio, guarda el dato.

Esto además de tremendamente impráctico te genera los problemas de memoria que describes. Si lo único que estás haciendo es guardar el mismo valor (0) en cada uno de los vectores podrías crear los vectores directamente con los datos usando uno de sus constructores (concretamente, el listado en el número tres):

constexpr vector( size_type count,
                  const T& value,
                  const Allocator& alloc = Allocator());

Este constructor recibe en primer lugar un número y en segundo lugar un valor. Guardará el valor recibido como segundo parámetro tantas veces como especifique el contador del primer parámetro. Usando ese constructor (y unos alias para facilitar la comprensión) tu código podría quedar así:

// Las filas contienen valores
using fila_t = std::vector<short>;
// Las tablas contienen filas
using tabla_t = std::vector<fila_t>;
// Las matrices contienen tablas
using matriz_t = std::vector<tabla_t>;
// Los array contienen matrices
using array4d_t = std::vector<matriz_t>;

constexpr auto x = 192;
constexpr auto y = 256;
constexpr auto z = 128;
constexpr auto t = 96;

    array4d_t matriz(t, matriz_t(z, tabla_t(y, fila_t(x, 0))));
//  ^^^^^^^^^~~~~~~~~^  ^^^^^^^^~^  ^^^^^^^~^  ^^^^^^~^  ^
//               \              \          \         \    \_____ inicializados a cero (0)
//                \              \          \         \_____ de x (192) elementos short
//                 \              \          \_____ de y (256) elementos fila_t
//                  \              \_____ de z (128) elementos tabla_t
//                   \_____ array4d de t (96) elementos matriz_t

std::cout << matriz[0][0][0][0]; // Muestra 0

Ejecutar ese código me ha llevado casi 8 segundos.

Pero si las dimensiones de tu estructura 4D son fijas, no deberías usar std::vector si no std::array:

constexpr auto x = 192;
constexpr auto y = 256;
constexpr auto z = 128;
constexpr auto t = 96;

using fila_t = std::array<short, x>;       // x (192) elementos de tipo short
using tabla_t = std::array<fila_t, y>;     // y (256) elementos de tipo fila_t
using matriz_t = std::array<tabla_t, z>;   // z (128) elementos de tipo tabla_t
using array4d_t = std::array<matriz_t, t>; // t (96) elementos de tipo matriz_t

auto matriz = std::make_unique<array4d_t>();

std::cout << (*matriz)[0][0][0][0];

Por desgracia, un objeto tan grande no cabe en la pila así que debemos usar memoria dinámica. Este código se ejecuta en algo más de dos segundos.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.