2

Estoy queriendo acceder a grafos ya dados. Tengo miles de líneas de código. Pongo algunos ejemplos del antes y del después.

typedef unsigned int u32;
typedef struct GrafoSt *Grafo;
typedef struct DuplaSt *Dupla;

struct GrafoSt
{
    ...
    Dupla colorVer;

    ...
};

struct DuplaSt
{
    u32 v1;
    u32 v2;
};

// Ejemplo: 

Grafo ConstruccionGrafo() {

    g->colorVer = malloc(n*sizeof(struct DuplaSt));
    ...
    g->colorVer[0].v2 = 0;
    u32 posVer = 0;
    for(u32 i = 1; i < 2*n; i++)
    {
        if (...)
        {
            posVer++;
            g->colorVer[posVer].v2 = posVer;
        }
        else
            ...
    }

}

Lo que quiero hacer es sacar la estructura "DuplaSt".

Lo que pensé fue:

struct GrafoSt
{
    ...
    u32** colorVer;

    ...
};

// Ejemplo

Grafo ConstruccionGrafo() {
    for(u32 i = 0; i < n; i++)
        g->colorVer[i] = malloc(n*sizeof(unsigned int));

    g->colorVer[0][1] = 0;
    u32 posVer = 0;
    for(u32 i = 1; i < 2*n; i++)
    {
        if (...)
        {
            posVer++;
            g->colorVer[posVer][1] = posVer;
        }
        else
            ...

    }

Y listo.

O sea, tengo grafos muy grandes, y con la primera opción cargar el grado, correr el algoritmo de greedy muchas veces con distintos reordenamientos, etc, etc, tarda mucho menos que con la segunda técnica.

No sabría decir por qué. Porque me parece que son acciones casi muy similares pero una diferencia de optimización muy elevada.

12
  • ¿Podrías incluir en la pregunta el código que has utilizado antes y después del cambio de la estructura de datos?
    – ordago
    el 13 feb. 2020 a las 12:12
  • @ordago ahi lo mejore un poco. Tengo muchas lineas. Pero así seria un ejemplo para acceder. el 13 feb. 2020 a las 12:24
  • 3
    Pensaría que el hecho de utilizar el malloc para buscar memoria disponible incrementa el tiempo de ejecución. Además con la primera opcion, al tener una estructura definida (tamaño y offsets), creo que el compilador podría optimizar las instrucciones para acceder a los datos. En cambio con el malloc, las direcciones son variables en tiempo de ejecución, dependiendo de la memora asignada. el 13 feb. 2020 a las 12:43
  • 2
    ¿Por qué en el primer ejemplo no hace falta malloc()? tal como yo lo veo colorVer en el primer ejemplo es de tipo Dupla, es decir, puntero a DuplaSt. Como tal puntero debe ser inicializado y no veo dónde. Cuando luego usas g->colorVer[0] ¿a dónde irá? Para lo que no requiere malloc() es para el valor de cada colorVer[i], eso sí. Pero tampoco lo necesitarías en el segundo ejemplo si el puntero en vez de ser a puntero lo haces a array de dos u32.
    – abulafia
    el 13 feb. 2020 a las 12:58
  • 1
    Y si defines ColorVer como u32 ColorVer[2]; dentro de la estructura GrafoSt? el 13 feb. 2020 a las 12:58

1 respuesta 1

2

O sea, tengo grafos muy grandes, y con la primera opción cargar el grado, correr el algoritmo de greedy muchas veces con distintos reordenamientos, etc, etc, tarda mucho menos que con la segunda técnica.

La reserva de memoria dinámica es un proceso pesado. En cada petición, el Sistema Operativo tiene que localizar una porción de memoria que no esté ya reservada... si no encuentra ningún bloque dentro de la memoria de la aplicación, entonces tiene que reservar un nuevo bloque para dicha aplicación y asignar memoria de ese bloque... Es un proceso que consume su tiempo.

Dicho esto, en el primer caso tenemos una única reserva de memoria:

g->colorVer = malloc(n*sizeof(struct DuplaSt));

Mientras que en el segundo, tenemos n:

for(u32 i = 0; i < n; i++)
    g->colorVer[i] = malloc(n*sizeof(unsigned int));

Luego parece obvio pensar que el segundo algoritmo será más lento que el primero.

Tu Respuesta

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

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