我可以释放在 C 递归的每一步中生成的 mallocs 吗？

Question

我正在用 C（为了性能）进行模拟，它（当前）使用递归和 mallocs（在递归的每一步中生成）。问题是我无法在代码中的任何地方释放 malloc，而不会出现错误的最终输出。该代码由两个函数和主要函数组成：

evolution(double initial_energy)

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

double * evolution(double initial_energy){
    
    double * energy_vec = malloc(sizeof(double)*50);
    for(int i = 0; i <= 50; i++){

        energy_vec[i] = 0;

    }

    int i = 0;

    while(initial_energy > 1){

        initial_energy /= 2;
        energy_vec[i] = initial_energy;
        i++;
    }
    return energy_vec;
}

这里是生成 mallocs 的地方。然后我定义recursion(double initial_energy)即return事件总数，即initial_energy除以2直到其值小于1的事件。

double recursion(double initial_energy){

    int event_counter = 0;
    int j = 0;
    double * Energy;

    Energy = evolution(initial_energy);

    while(Energy[j] > 0.0){

        event_counter++;
        event_counter += recursion(Energy[j]);
        j++;
    }
    return event_counter;
}

最后是 main 函数，这里有它并没有太大区别，但为了完整起见，这里是

int main(){

    int trials = 20000;
    int events;
    double initial_energy = 70;

    for(int i = 0; i <= trials; i++){

        events = recursion(initial_energy);
        printf("%i) events = %i\n",i, events);
        usleep(200);
    }
    return events;
}

那么，这段代码是否有可能在任何地方释放 malloc 并在最后得到正确的结果？（正确的结果应该是 2**N - 1，其中 N 是连续将 initial_energy 除以 2 可以得到大于 1 的值的次数。例如，对于这段代码，正确的答案是127 在程序结束时）。我已经尝试在主函数的 for 循环中定义 malloc，并在调用递归后立即释放它，但它没有保存正确的结果。

我只是偶尔使用 C（当 python 性能对于某些计算来说太慢时），所以我对我想要的语言没有技术上的理解。所以我愿意接受任何必要的代码更改。

提前致谢！

Answer 1

您应该在最后一次使用内存后立即释放内存。在你的程序中，在 recursion 中的 while 循环之后，Energy 不再被使用，所以你应该在那之后立即释放它（即，就在 return event_counter; 之前）。

Answer 2

Joseph Sible-Reinstate Monica 关于您提出的问题是正确的。但是您的代码可以在许多方面进行改进。如果您想查看最终版本，您应该一直滚动到我对 run_simulation 的回答的底部，这是 recursion 函数的一个明显更好的版本。

让我们从您的初始函数开始，evolution。如果你想分配内存并将所有字节初始化为0，你应该使用calloc函数而不是malloc。而不是

double * energy_vec = malloc(sizeof(double)*50);
for(int i = 0; i < 50; i++){ // your original i <= 50 was wrong
    energy_vec[i] = 0;
}

你应该这样做

double * energy_vec = calloc(50 * sizeof(double));

这通常比 malloc + 手动将所有内容都设置为 0 更有效，并且更具可读性。

其次，没有理由recursion到return一个double除外。 recursion 到 return 最合乎逻辑的是 unsigned int，因为它总是 return 一个非负整数。这实际上是一个替代品；只需将 return 类型和 event_counter 的类型更改为 unsigned int，您的代码就可以正常工作，而无需毫无意义地 returning a double。我将进行此切换 - 暂时。

第三，一个double可以大于2^50。如果发生这种情况，您的 energy 数组将不够大。这是一个严重的问题，但可以通过动态调整数组大小来避免。像 Rust 或 C++ 这样的更高级别的高性能语言会为您提供可调整大小的数组作为标准库的一部分，但在 C 中，您必须手动完成。

第四，你实际上根本不需要动态内存分配，因为你的代码可以用数学来完成。你实际上可以完全没有循环！但是，为了避免使用“浮点黑魔法”，我将在我的回答中使用循环。我们先定义

unsigned int count_divisions(double d) {
    unsigned int count;
    for (count = 0; d > 1.0; d /= 2, count++);
    return count;
}

注意count_divisions(d)正好等于evolution(d)的概念长度。

现在，我们应该注意到，我们真正关心的双打属性只有 count_divisions 值。这是我们唯一使用的东西。因此，无论我在哪里看到 double，我都会用它的 count_divisions 值替换它。生成的代码如下所示：

unsigned int * evolution(unsigned int divisions){
    unsigned int * Energy = malloc(divisions * sizeof(*Energy));
    for(unsigned int i = 0; i < divisions; i++) {
        Energy[i] = divisions - i - 1;
    }
    return Energy;
}

unsigned int recursion(unsigned int divisions) {
    unsigned int* energy_vec = evolution(divisions);
    unsigned int count = divisions;
    for (unsigned int j = 0; j < divisions; j++) {
        count += recursion(energy_vec[j]);
    }
    free(energy_vec);
    return count;
}

现在，我们开始接近答案。但是请注意，我们实际上已经知道每个 j 的 energy_vec[j] 是什么；它将是 divisions - j - 1。所以我们可以完全消除energy_vec向量，得到如下代码：

unsigned int recursion(unsigned int divisions) {
    unsigned int* energy_vec = evolution(divisions);
    unsigned int count = divisions;
    for (unsigned int j = 0; j < divisions; j++) {
        count += recursion(divisions - j - 1);
    }
    return count;
}

我们可以简单地重写为

unsigned int recursion(unsigned int divisions) {
    unsigned int* energy_vec = evolution(divisions);
    unsigned int count = 0;
    for (unsigned int j = 0; j < divisions; j++) {
        count += recursion(j);
    }
    return count + divisions;
}

现在，我们必须使用一点小聪明来为recursion推导出一个更好的递归关系。事实证明，可以证明 recursion(0) = 0 和 recursion(k + 1) = 2 * recursion(k) + 1。这是因为

recursion(k + 1) 
= recursion(0) + recursion(1) + ... + recursion(k) + k + 1
= (recursion(0) + recursion(1) + ... + recursion(k - 1) + k) + recursion(k) + 1
= recursion(k) + recursion(k) + 1
= 2 * recursion(k) + 1

因此，我们很容易通过归纳法证明recursion(k) = 2^k - 1.

所以实际上，您正在接受值 initial_energy 和 returning 2^(ceil(log(initial_energy))) - 1。

最终的解决方案可能是

double run_simulation(double initial_energy) {
    double power_of_two = 1;
    while (initial_energy > 1) {
        power_of_two *= 2;
        initial_energy /= 2;
    }
    return power_of_two - 1;
}

以更低的成本取代您原来的 recursion 功能。

我可以释放在 C 递归的每一步中生成的 mallocs 吗？

Can I free mallocs that are being generated in every step of a recursion in C?

c

recursion

malloc

free