Início / coding / Perguntas / 77745292
Accepted
euraad
Asked: 2024-01-02 17:55:23 +0800 CST

Impedir o uso de memória de pilha para funções recursivas em C

  • 772

Este código C faz DBSCAN - cluster espacial de aplicativos com ruído baseado em densidade. É um algoritmo de cluster para transformar dados não supervisionados (sem rótulos) em dados supervisionados (rótulos, por exemplo, número de classe). E também é rápido. A desvantagem do DBSCAN é que ele consome muita memória, mas sua velocidade é excelente!

Então o que fiz foi criar um algoritmo DBSCAN que usa recursão. Depois de terminar isso, noto que a recusa causou um estouro de pilha se o argumento da linha fosse grande.

Questões:

  1. Quero ter certeza de que as funções de recursão em C devem ser alocadas no heap, não na pilha. Como isso pode ser feito?
  2. Existe alguma maneira de garantir que esta função recursion_clustering não aumente nenhuma memória e use apenas memória estática? Tentei usar o máximo possível de ponteiros para evitar duplicação de memória.

Código:

/* Private function */
static bool recursion_clustering(const int32_t i, const size_t* row, const float* epsilon, const size_t* min_pts, const float C[], bool visited[], size_t idx[], int32_t* id, int32_t* count);

 /*
  * Create ID's of clusters
  * X[m*n]
  * idx[m] = Contains cluster ID. Noise ID is 0
  * epsilon = Raduis of the clusters
  * min_pts = Minimum points of a valid cluster
  */
void dbscan(const float X[], size_t idx[], const float epsilon, const size_t min_pts, const size_t row, const size_t column) {
    /* Create idx */
    memset(idx, 0, row * sizeof(size_t));

    /* Create pdist2 C */
    float* C = (float*)malloc(row * row * sizeof(float));
    pdist2(X, X, C, row, column, row, PDIST2_METRIC_EUCLIDEAN);

    /* Flags */
    bool* visited = (bool*)malloc(row * sizeof(bool));
    memset(visited, false, row * sizeof(bool));
    
    /* Iterate */
    int32_t i, count, id = 1;
    for (i = 0; i < row; i++) {
        if (recursion_clustering(i, &row, &epsilon, &min_pts, C, visited, idx, &id, &count)) {
            /* Set ID value */
            idx[i] = id;
            id++;
        }
    }

    /* Free */
    free(C);
    free(visited);
}

static bool recursion_clustering(const int32_t i, const size_t* row, const float* epsilon, const size_t* min_pts, const float C[], bool visited[], size_t idx[], int32_t* id, int32_t* count) {
    /* Declare variables */
    int32_t j;

    /* Check if already visited - else mark as visited */
    if (visited[i]) {
        return false;
    }
    else {
        visited[i] = true;
    }

    /* Begin first with the row of C */
    *count = 0;
    for (j = 0; j < *row; j++) {
        /* Check how many index exceeds min_pts */
        if (C[i * (*row) + j] <= *epsilon) {
            (*count)++;
        }
    }

    /* Check if count is less than min_pts */
    if (*count < *min_pts) {
        return false;
    }

    /* Iterate forward */
    for (j = i + 1; j < *row; j++) {
        if (!visited[j] && C[i * (*row) + j] <= *epsilon) {
            /* Recursion */
            if (recursion_clustering(j, row, epsilon, min_pts, C, visited, idx, id, count)){
                /* Set ID value */
                idx[j] = *id;
            }
        }
    }

    /* Iterate backward */
    for (j = i - 1; j >= 0; j--) {
        if (!visited[j]) {
            /* Recursion */
            if (recursion_clustering(j, row, epsilon, min_pts, C, visited, idx, id, count)) {
                /* Set ID value */
                idx[j] = *id;
            }
        }
    }

    /* Return true */
    return true;
}

Se quiser executar este código, você precisará deste exemplo prático.

#define row 65
#define column 3

int main() {
    /* Define X, idx, epsilon and min_pts */
    float X[row * column] = { -0.251521, 1.045117, -1.281658,
        -1.974109, 0.278170, -1.023392,
        -0.957729, -0.977450, 0.477872,
        -0.449159, -1.016680, 0.095610,
        -1.785787, -1.403543, 0.483454,
        1.366889, -0.762590, -1.162454,
        2.129839, 0.358568, -2.118250,
        0.751071, -1.766582, 0.178434,
        -1.980847, -1.320933, -0.457778,
        -0.478030, 0.606917, -1.630624,
        3.674916, 0.088957, 0.877373,
        0.637213, 0.079176, 0.342038,
        1.142329, 0.629997, 0.311134,
        -0.878974, 0.042527, 0.736522,
        1.751637, -1.434299, -1.325140,
        1.110682, 1.091970, 1.434869,
        -0.504482, -2.504821, -1.245315,
        -0.102915, -0.203266, -0.849767,
        -0.822834, 1.158801, -0.405579,
        -1.278287, 0.391306, 0.857077,

        /* Outliers */
         45, 43, 0,
         23, -3, 2,

        10.6772, 10.7365, 9.9264,
        8.7785, 11.1680, 9.5915,
        8.6872, 9.6464, 10.3801,
        10.0142, 8.8311, 9.2021,
        8.4179, 9.8572, 11.6356,
        9.8487, 10.4979, 10.8620,
        10.0957, 9.7878, 12.2653,
        11.4528, 11.5186, 10.3050,
        10.9284, 9.9654, 10.4562,
        8.5272, 10.7451, 9.8355,
        10.1508, 10.2318, 10.2417,
        10.7342, 10.0689, 9.9918,
        10.4784, 9.2032, 10.6060,
        10.1309, 9.4392, 10.9674,
        10.6971, 10.3347, 11.0447,
        7.9489, 9.4566, 9.5258,
        10.4827, 10.3030, 10.5582,
        10.4496, 10.3880, 11.1661,
        11.0291, 10.0233, 9.9280,
        9.0638, 9.3650, 9.3670,

        /* Outliers */
         32, 54, 23,
         23, 51, 77,


    -34.233,  -30.841,  -31.720,
     -32.629,  -31.786,  -31.290,
     -31.466,  -31.984,  -33.254,
     -31.878,  -33.052,  -31.761,
     -33.528,  -30.921,  -32.836,
     -31.793,  -32.082,  -30.453,
     -31.812,  -32.417,  -31.874,
     -32.127,  -32.599,  -32.806,
     -32.979,  -32.096,  -31.754,
     -31.759,  -31.925,  -31.313,
     -30.531,  -31.838,  -31.179,
     -32.168,  -31.928,  -30.649,
     -31.049,  -32.092,  -31.408,
     -33.006,  -31.753,  -31.961,
     -32.092,  -32.391,  -31.501,
     -31.184,  -31.634,  -32.802,
     -30.658,  -31.616,  -31.493,
     -31.958,  -31.694,  -31.425,
     -33.114,  -32.029,  -31.459,
     -31.081,  -34.486,  -32.020,

        /* Outlier */
        -22, -34, 53 };

    size_t idx[row] = { 0 };
    float epsilon = 10;
    size_t min_pts = 3;

    /* Compute dbscan */
    dbscan(X, idx, epsilon, min_pts, row, column);

    /* Print idx */
    size_t i;
    for (i = 0; i < row; i++) {
        printf("%i\n", idx[i]);
    }

    return 0;
}

A saída se torna:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
0
0
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
3
0
c

2 respostas

  1. Best Answer
    1. Quero ter certeza de que as funções de recursão em C devem ser alocadas no heap, não na pilha. Como isso pode ser feito?

    Isso é impossível. O próprio padrão C não menciona onde as coisas são alocadas, exceto que o armazenamento alocado é um caso especial utilizado apenas quando malloc(e amigos) é usado explicitamente.

    Fora isso, o local onde os parâmetros e endereços de retorno são armazenados é determinado pela convenção de chamada e pela ABI do seu sistema específico. A grande maioria de todos os computadores existentes usa uma combinação de registros e empilhamento para isso.

    1. Existe alguma maneira de garantir que esta função recursion_clustering não aumente nenhuma memória e use apenas memória estática? Tentei usar o máximo possível de ponteiros para evitar duplicação de memória.

    Não sem uma reescrita completa do programa. É possível projetar funções recursivas que o compilador possa incorporar, que então não resultam em nenhum pico de uso da pilha. Mas para que isso seja possível, a recursão normalmente deve ser a chamada chamada final , onde a chamada recursiva está na parte inferior da função. A função também deve ser declarada staticpara garantir a ligação interna. Mas mesmo assim não há garantia de que o compilador seja capaz de inline.

    Acontece que a melhor prática é evitar totalmente a recursão.

    Então, como resolver isso? Você pode substituir qualquer função recursiva por um loop, mas nesse caso não há empilhamento automático de parâmetros. Uma maneira de resolver isso é desenvolver seu próprio tipo de dados semelhante a uma pilha e ter uma pilha personalizada ao lado e inserir/empurrar aquela do loop. Esse tipo de pilha pode então usar mallocou o que você quiser internamente. Por outro lado, você tem vários parâmetros - caso você realmente não precise de uma cópia local de cada um deles, basta armazenar o resultado em uma única variável compartilhada por todas as iterações do loop.

    Outra maneira é integrar um sistema pai/filho ou anterior/próximo nos próprios dados. Por exemplo, se o propósito da recursão fosse pesquisar através de um BST, você poderia dar a cada nó um ponteiro pai, de modo que quando você encontrar uma "folha" com um ponteiro nulo tanto para a esquerda quanto para a direita, você possa continuar a execução de o pai. A desvantagem deste método é que ele consome espaço extra junto com os dados.

    De qualquer forma, um pouco de trabalho extra. Mas uma vez que você tenha feito isso corretamente, ele deverá, por definição, ser executado mais rápido, ou pelo menos não mais lento, do que o que você tem atualmente. Como a recursão vem com sobrecarga na velocidade de execução.

    • 3

  2. Não existe uma maneira padrão de conseguir o que você está pedindo. O padrão nem especifica o uso de uma pilha. Essa é uma decisão de implementação. A única solução real é evitar a recursão.

    Se você ainda preferir a recursão, deverá reduzir a memória consumida por cada chamada. Em geral, isso é feito reduzindo o número de variáveis ​​locais e parâmetros de função.

    Pelo que posso ver, a maioria dos valores passados ​​​​para a função são os mesmos o tempo todo, por exemplo row, epsilon, min_pts, C, visitede muito mais.

    Se você colocar tudo isso em um structin dbscane, em vez disso, passar um ponteiro para essa estrutura, o uso de memória poderá ser reduzido significativamente.

    ps Você pode até tornar todas essas variáveis ​​ou a estrutura globais, ou seja, não há necessidade de passá-las, mas em geral o uso de (muitas) variáveis ​​globais não é recomendado.

    POR FALAR NISSO:

    Citar:

    Tentei usar o máximo possível de ponteiros para evitar duplicação de memória.

    Bem, isso é um mal-entendido. Um ponteiro passado ocupa memória como qualquer outra variável. Em um sistema de 64 bits, um ponteiro para uma variável de 32 bits ocupará 64 bits. Então isso é realmente mais do que a variável.

    • 3

relate perguntas