撤销递归树

Question

SHORT 我应该如何在我的代码中减少（优化）所需的操作数量？

LONGER 为了研究，我编写了一组方程式在C++中输出序列，如果符合模型。在代码的内部是这个函数，它在运行时被多次调用：

int Weight(int i, int q, int d){
    int j, sum = 0;
    if (i <= 0)
        return 0;
    else if (i == 1)
        return 1;
    for (j = 1; j <= d; j++){
        sum += Weight((i - j), q, d);
    }
    sum = 1 + ((q - 1) * sum);
    return sum;
}

根据变量 d 的大小、索引 i 的大小以及此函数在代码的其余部分中被调用的次数，会进行许多冗余计算。如何减少计算次数？

理想情况下，例如在计算 Weight(5, 3, 1) 后，我应该如何告诉计算机在调用 Weight(6, 3, 1) 时替换它的值而不是重新计算它的值，考虑到该函数是递归定义的？

在这种情况下，多维向量是否可用于存储值？或者我应该将这些值打印到文件中以供读取？尽管我还没有遇到输入大小溢出的情况，但尾递归是否有助于优化它？

注意：我仍在学习编程，我很惊讶我甚至能够在第一次就正确地建立模型。

- Jeff

---

你熟悉动态规划或备忘录技术吗？ - templatetypedef

@templatetypedef 我听说过动态规划很多次，但仍不确定它的含义。从外表看来，记忆化似乎是一个流行的答案，可以只是一个查找表，所以这是我要尝试的第一步。 - Jeff

Answer 1

您可以使用记忆化技术

int WeightImpl(int i, int q, int d); // forward declaration

// Use memoization and use `WeightImpl` for the real computation
int Weight(int i, int q, int d){
    static std::map<std::tuple<int, int, int>, int> memo;

    auto it = memo.find(std::make_tuple(i, q, d));
    if (it != memo.end()) {
        return it->second;
    }
    const int res = WeightImpl(i, q, d);
    memo[std::make_tuple(i, q, d)] = res;
    return res;
}

// Do the real computation
int WeightImpl(int i, int q, int d){
    int j, sum = 0;
    if (i <= 0)
        return 0;
    else if (i == 1)
        return 1;
    for (j = 1; j <= d; j++){
        sum += Weight((i - j), q, d); // Call the memoize version to save intermediate result
    }
    sum = 1 + ((q - 1) * sum);
    return sum;
}

演示

注意：由于您使用了递归调用，因此必须谨慎选择哪个版本来调用以真正地记忆每个中间计算。我的意思是，递归函数应该被修改为不调用自身，而是调用函数的记忆化版本。对于非递归函数，可以在不修改真实函数的情况下进行记忆化。

- Jarod42

---

需要注意的是，根据问题的不同，std::map 可能会被更高效的数据结构所替代。但它确实是一种简单有效的方法，可以确定是否值得花时间去尝试这种方法。 - stefan

@stefan 我复制并粘贴了你的代码，但出现了一些错误。特别是，“memo未定义”，“在初始化之前不能使用‘it’”，以及“‘.end’的左侧必须具有类/结构/联合体。”非常感谢你所做的努力来帮助我！在复制和粘贴之前，我尝试过备忘录技术，只是将权重存储在全局数组中，这提高了计算速度约10%。 - Jeff

Answer 2

你可以使用数组来存储中间值。例如，对于某些d和q，有一个包含Weight(i, q, d)值的数组，在索引i处。

如果你将数组项初始化为-1，那么你可以在函数中执行以下操作。

if(sum_array[i] != -1){    // if the value is pre-calculated
    sum += sum_array[i];
}
else{
    sum += Weight((i - j), q, d);
}

- pthomaid