c++ - 递归填充动态大小 vector

Question

也许让我先用伪 C++ 代码陈述我的情况:

std:vector<double> sample(someFunctor f, double lower, double upper) {
    double t = (lower + upper)/2;
    double newval = f(t);

    if (f(upper) - newval > epsilon)
        subsample1 = sample(f, t, upper);
    if (newval - f(lower) > epsilon)
        subsample2 = sample(f, lower, t);

    return concat(subsample2, newval, subsample1);
}

其中 concat 只是连接返回的 vector 。基本上，我以一种方式对函数进行采样，使得两个保存的函数值之间只有很小的差异。

我对上述方式不满意，因为在每个递归步骤中似乎有相当多的内存分配(分配两个子 vector ，然后连接它们和另一个元素)。该段代码必须在我的算法的一部分中运行，该部分对性能至关重要。一次upper - lower相当小，评价f不会花很多时间。

所以我的问题:

• 您是否看到一种聪明的方法，可以在所有递归调用中使用相同的数据结构并只填充该 vector 的当前部分？ (请记住，预先不知道所需的函数评估数量)。对此的想法:

  • 使用列表而不是 vector 。但我觉得内存大修不足以仅存储 double 。
  • 保留 vector 中的空洞并维护另一个 vector ，说明哪些条目已被填充。递归调用的结尾移动条目，以便 subsample 之间没有空洞。 s 和 newval .但现在我通过转移第二个 vector 的额外工作来切换复制 - 可能是个坏主意。

• 您是否找到了完全摆脱递归的方法？但是，为了正确起见，我使用上面提到的分而治之模式很重要。函数f大量使用上限和下限，并由此获得相当大的性能。

谢谢你的想法。

---

根据 Space_C0wb0y 的要求，让我尝试重新表述我的问题。可能第一次解释的不是很清楚。

我有一些函数(在数学意义上)，我想在给定的时间间隔内对其进行采样(例如，在某些点进行评估)。

假设区间是[0,100]。我知道函数值为 0 和 100。也许那是 f(0)=0和 f(100) = 40 .现在我在间隔中点评估函数，即 50。说，我的函数返回 f(50)=10 .作为f(0)-f(50) <= 10 ，我不需要区间 [0,50] 中的更多样本。但是，我需要进一步计算区间 [50,100]。因此，在下一步(递归)中，我评估 f(75) .现在递归地重复上面的逻辑。

最后我想(两个) vector 给我函数值和相应的参数，如下所示:

parameter  = vector(0, 50, 56.25, 62.5, 75, 100)
value      = vector(0, 10, 17.21, 25    34,  40)

我正在寻找递归构建这些 vector 的最佳(也是最高效的)方法。

希望这能澄清事情。

Answer 1

由于空间不是您主要关心的问题，所以我将继续使用递归。

<强>1。使用按引用复制而不是按(返回)值复制。

<强>2。无需传入仿函数，因为它是常量。

<强>3。如果 low 和 high 是整数，它可能会更快。不过，这取决于要求。

    // Thanks to Space_C0wb0y, here we avoid using a global vector
    // by passing the vector as reference. It's efficient as there
    // is no copy overhead as well.        
    void sample(vector<double>& samples, double low, double high)
    {
       // You can use shift operator if they're integers.
       double mid = (low + high)/2;

       // Since they're double, you need prevent them from being too close.
       // Otherwise, you'll probably see stack overflow.
       // Consider this case:
       // f(x): x=1, 0<x<8;  x*x, x<=0 or x>=8
       // low = 1, high = 10, epsilon = 10
       if (high - low < 0.5)
       {
          samples.push_back(f(mid));
          return;
       }   

       // The order you write the recursive calls guarantees you
       // the sampling order is from left to right.
       if (f(mid) - f(low) > epsilon)
       {
          sample(samples, low, mid);
       }

       samples.push_back(f(mid));

       if (f(high) - f(mid) > epsilon)
       {
          sample(samples, mid, high);
       }   
    }