es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

La serialización de Boost con estructuras de datos recursivas acaba en desbordamiento de pila.

Problema

Tengo problemas al usar la biblioteca de serialización Boost con una estructura recursiva de datos. Más concretamente, quiero serializar una matriz que está representada por nodos que contienen un valor, y donde cada nodo tiene acceso a sus vecinos (arriba, abajo, izquierda, derecha). Para acceder a un nodo, se almacena cada punto de entrada en un vector (que es el primer y último nodo de cada fila y columna). Aquí está la clase Node:

class Node
{
private:
    int v;
    Node* left; 
    Node* right;
    Node* top;
    Node* bottom;

public:
    Node() : v(rand() % 100), left(NULL), right(NULL), top(NULL), bottom(NULL)
    {

    }

    //Posible fugas de memoria, pero ese no es el tema
    void setLeft(Node* toSet) { left = toSet; }
    void setRight(Node* toSet) { right = toSet; }
    void setTop(Node* toSet) { top = toSet; }
    void setBottom(Node* toSet) { bottom = toSet; }

    Node* gLeft() { return left; }
    Node* gRight() { return right; }
    Node* gTop() { return top; }
    Node* gBottom() { return bottom; }

    int gValue() { return v; }

    template<class Archive>
    void serialize(Archive& ar, const unsigned int version)
    {
        ar& v;
        ar& left;
        ar& right;
        ar& top;
        ar& bottom;
    }
};

Aquí está la clase Matrix, con una función generateValues() para este ejemplo:

class Matrix
{
private:
    int m, n;
    std::vector<Node*> firstNodesPerRow;
    std::vector<Node*> lastNodesPerRow;
    std::vector<Node*> firstNodesPerCol;
    std::vector<Node*> lastNodesPerCol;
public:
    Matrix(int m, int n) : 
        m(m), n(n),
        firstNodesPerRow(m, NULL), lastNodesPerRow(m,NULL),
        firstNodesPerCol(n, NULL),lastNodesPerCol(n, NULL)
    {

    }

    void generateValues()
    {
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                Node* toWrite = new Node();
                if (i > 0)
                {
                    toWrite->setTop(lastNodesPerCol.at(j));
                    lastNodesPerCol.at(j)->setBottom(toWrite);
                    lastNodesPerCol.at(j) = toWrite;
                }
                else
                {
                    firstNodesPerCol.at(j) = toWrite;
                    lastNodesPerCol.at(j) = toWrite;
                }
                if (j > 0)
                {
                    toWrite->setLeft(lastNodesPerRow.at(i));
                    lastNodesPerRow.at(i)->setRight(toWrite);
                    lastNodesPerRow.at(i) = toWrite;
                }
                else
                {
                    firstNodesPerRow.at(i) = toWrite;
                    lastNodesPerRow.at(i) = toWrite;
                }
            }
        }
    }

    template<class Archive>
    void serialize(Archive& ar, const unsigned int version)
    {
        ar& m;
        ar& n;
        ar& firstNodesPerRow;
        ar& firstNodesPerCol;
        ar& lastNodesPerRow;
        ar& lastNodesPerCol;
    }
};

Entonces, lo que quiero lograr es la serialización y deserialización de una matriz. Aquí está mi función main:

#include <cstdlib>
#include <sstream>
#include <vector>
#include <boost/archive/text_oarchive.hpp>
#include <boost/archive/text_iarchive.hpp>
#include <boost/serialization/vector.hpp>

int main(int argc, char* argv[])
{
    int m = 10; int n = 10;
    Matrix toSerialize(m,n);
    toSerialize.generateValues();

    /*
        1) Serialize
    */
    std::ostringstream oss;
    boost::archive::text_oarchive oa(oss);
    oa << toSerialize;

    std::string serialiazedData = oss.str();

    /*
        2) Deserialize
    */
    Matrix result(m,n);
    std::stringstream serializedDataStream(serialiazedData);
    boost::archive::text_iarchive ia(serializedDataStream);
    ia >> result;

    return EXIT_SUCCESS;
}

El problema es el siguiente: dado un valor suficientemente grande de m o n, main termina con una excepción de stack-overflow. Sé que proviene del método de serialize de Node, porque para serializar un nodo, necesita serializar los vecinos y así sucesivamente… Encontré este tema que parece que es exactamente la misma pregunta. La respuesta es interesante como punto de partida, pero tengo problemas para implementarla porque no es suficientemente precisa. Lo que entiendo es que para resolver mi problema, necesito:

  1. serializar los nodos de manera iterativa, de modo que cuando se trate de los vecinos, los objetos ya estén serializados y no haya un stack-overflow;
  2. serializar la topología, que está representada en mi caso a través de los punteros top, bottom, right, left de Node.

Tengo problemas para implementar esta solución, porque la única forma en que puedo imaginar hacer el punto 1 implica eliminar la serialización de top, bottom, right, left en el método serialize de Node, pero ¿cómo logro el punto 2?

Edit: Hice un diagrama de una matriz para ayudar a leer. Tenga en cuenta que no necesariamente hay m

Tags:  , , , ,

Answer

  1. Avatar for davy.ai

    Solución para Boost Serialization con estructuras de datos recursivas

    El problema se debe a la naturaleza recursiva de la estructura de datos, donde un nodo necesita serializar a sus vecinos, y esos vecinos a su vez necesitan serializar a sus vecinos, y así sucesivamente. Esto crea un desbordamiento de pila cuando la recursividad se vuelve demasiado profunda debido a un gran número de nodos.

    Una posible solución a este problema implica dividir la serialización en dos partes: una para los nodos en sí mismos y otra para la topología, que incluye los punteros a los nodos vecinos. De esta manera, puedes serializar los nodos primero, sin incluir la topología, y luego serializar la topología por separado, una vez que todos los nodos hayan sido serializados.

    Para implementar esta solución, puedes modificar el código de serialización de la siguiente manera:

    Paso 1: Define una estructura de buffer

    Define una estructura de buffer que contenga los punteros a los vecinos, que se utilizarán durante la serialización para guardar la topología.

    “`c++
    struct Neighbors
    {
    Node* top;
    Node* bottom;
    Node* left;
    Node* right;

    template <typename archive="">
    void serialize(Archive& ar, const unsigned int version)
    {
        ar& top;
        ar& bottom;
        ar& left;
        ar& right;
    }
    

    };


    ## Paso 2: Serializa los nodos y la topología por separado Modifica el método `serialize` de la clase `Matrix` para guardar la topología por separado de los nodos. Primero, debes serializar los nodos sin incluir la topología, y guardar los vecinos de cada nodo en un buffer. Luego, puedes serializar la topología, que incluye el buffer, y restaurar los vínculos entre los nodos. ```c++ template<class archive=""> void save(Archive& ar, const unsigned int version) const { std::map<node*, neighbors=""> neighborsPerNode; for (int i = 0; i < m; i++) { Node* current = firstNodesPerRow.at(i); while (1) { if (current == NULL) { break; } neighborsPerNode[current] = { current->gTop(), current->gBottom(), current->gLeft(), current->gRight(), }; ar& *current; current = current->gRight(); } } ar& neighborsPerNode; ar& m; ar& n; ar& firstNodesPerRow; ar& firstNodesPerCol; ar& lastNodesPerRow; ar& lastNodesPerCol; } template<class archive=""> void load(Archive& ar, const unsigned int version) { std::map<node*, neighbors=""> neighborsPerNode; ar& neighborsPerNode; ar& m; ar& n; ar& firstNodesPerRow; ar& firstNodesPerCol; ar& lastNodesPerRow; ar& lastNodesPerCol; for (int i = 0; i < m; i++) { Node* current = firstNodesPerRow.at(i); while (1) { if (current == NULL) { break; } Neighbors myNeighbors = neighborsPerNode.at(current); current->setTop(myNeighbors.top); current->setBottom(myNeighbors.bottom); current->setLeft(myNeighbors.left); current->setRight(myNeighbors.right); ar& *current; // deserializa el contenido del nodo current = current->gRight(); } } } BOOST_SERIALIZATION_SPLIT_MEMBER()

    Conclusión

    Con esta modificación, la serialización de la matriz ya no debería causar un desbordamiento de pila incluso para matrices grandes. La idea es serializar los nodos primero sin los punteros a los vecinos y luego serializar los punteros por separado de manera bufferizada.</node,></node,>

Comments are closed.