主页 / coding / 问题 / 77745292
Accepted
euraad
Asked: 2024-01-02 17:55:23 +0800 CST

防止 C 中递归函数使用堆栈内存

  • 772

此 C 代码执行 DBSCAN - 对带有噪声的应用程序进行基于密度的空间聚类。它是一种聚类算法，用于将无监督（无标签）数据转变为有监督（标签，例如类号）数据。而且速度也很快。DBSCAN 的缺点是消耗大量内存，但速度非常出色！

所以我所做的是创建了一个使用递归的 DBSCAN 算法。完成此操作后，我注意到如果行参数很大，则递归会导致堆栈溢出。

问题：

  1. 我想确保 C 中的递归函数必须分配在堆上，而不是堆栈上。那怎么办呢？
  2. 有什么办法可以确保这个函数 recursion_clustering 不会增加任何内存并且只使用静态内存？我尝试使用尽可能多的指针来防止内存重复。

代码：

/* 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;
}

如果您想运行此代码，您需要这个工作示例。

#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;
}

输出变为：

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 个回答

  1. Best Answer
    1. 我想确保 C 中的递归函数必须分配在堆上，而不是堆栈上。那怎么办呢？

    这不可能。事实上，C 标准本身并没有提及事物的分配位置，除了分配的存储是一种特殊情况，仅在malloc显式使用（和朋友）时才使用。

    除此之外，参数和返回地址的存储位置由特定系统的调用约定和 ABI 决定。绝大多数计算机都使用寄存器和堆栈的组合来实现此目的。

    1. 有什么办法可以确保这个函数 recursion_clustering 不会增加任何内存并且只使用静态内存？我尝试使用尽可能多的指针来防止内存重复。

    没有完整的程序重写就不行。可以设计编译器可能内联的递归函数，这样就不会出现任何堆栈峰值使用。但为了实现这一点，递归通常必须是所谓的尾部调用，其中递归调用位于函数的最底部。还应该声明该函数static以确保内部链接。但即便如此，也不能保证编译器能够内联。

    事实证明，最佳实践是完全避免递归。

    那么如何解决呢？您可以用循环替换任何递归函数，但在这种情况下，不会自动堆叠参数。解决这个问题的一种方法是开发自己的类似堆栈的数据类型，并在侧面有一个定制的堆栈，并从循环中压入/弹出该堆栈。然后，该堆栈类型可以malloc在内部使用或任何您喜欢的内容。另一方面，那里有大量参数 - 如果您实际上不需要每个参数的本地副本，您可以将结果存储在由循环的所有迭代共享的单个变量中。

    另一种方法是将父/子或上一个/下一个系统集成到数据本身中。例如，如果递归的目的是搜索 BST，您可以为每个节点提供一个父指针，这样当您遇到左侧和右侧都有空指针的“叶子”时，您可以从家长。这种方法的缺点是它与数据一起消耗额外的空间。

    无论哪种方式，都会有相当多的额外工作。但是，一旦您完成并正确完成，根据定义，它应该比您当前的执行速度更快，或者至少不慢。由于递归会带来执行速度的开销。

    • 3

  2. 没有标准方法可以实现您的要求。该标准甚至没有指定堆栈的使用。这是一个执行决定。唯一真正的解决方案是避免递归。

    如果您仍然喜欢递归，则必须减少每次调用消耗的内存。一般来说，这是通过减少局部变量和函数参数的数量来完成的。

    据我所知，传递给函数的大多数值始终相同，例如row、、、等。epsilonmin_ptsCvisited

    如果将所有这些放入structin中dbscan并传递指向该结构的指针，则内存使用量可能会显着减少。

    ps 您甚至可以将所有这些变量或结构设为全局，即根本不需要传递它们，但一般不建议使用（许多）全局变量。

    顺便提一句：

    引用：

    我尝试使用尽可能多的指针来防止内存重复。

    嗯，这是一个误会。传递的指针像任何其他变量一样占用内存。在 64 位系统上，指向 32 位变量的指针将占用 64 位。所以这实际上不仅仅是变量。

    • 3

相关问题