递归填充动态大小向量

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 只是连接返回的向量。基本上，我对函数进行采样的方式使得两个保存的函数值之间只有很小的差异。

我对上述方式不满意，因为在每个递归步骤中似乎都有相当多的内存分配（分配两个子向量，然后连接这些子向量和另一个元素）。该代码必须在我的算法中对性能至关重要的部分中运行。一旦 upper - lower 相当小，计算 f 就不会花费大量时间。

所以我的问题是：

• 您是否看到了一种巧妙的方法，可以在所有递归调用中使用相同的数据结构并仅填充该向量的当前部分？ （请记住，预先未知所需的功能评估数量）。对此的思考：

  • 使用列表而不是向量。但我觉得内存检修不足以仅存储双精度数。
  • 在向量中保留漏洞并维护另一个向量，说明哪些条目已填充。递归调用结束时会移动条目，以便 subsample 和 newval 之间没有空洞。但现在我通过对第二个向量进行额外的工作来切换复制 - 可能是个坏主意。

• 你有没有找到一种完全摆脱递归的方法？然而，为了正确性，使用上述分而治之的模式很重要。函数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)。现在递归地重复上述逻辑。

最后，我想（两个）向量为我提供带有相应参数的函数值，如下所示：

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

我正在寻找最好的（也是性能最高的）方法来递归地构建这些向量。

希望这能澄清事情。

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

Answer 2

我建议采用以下方法：

1. 不要使用两个向量，而是使用一个带有对的向量或自定义struct来表示参数和值：

   struct eval_point {
       双参数；
       双值；
   };
   
   std::vector;评估分；
   

2. 更改您的算法以写入结果对输出迭代器的评估：

   模板<类F，类output_iterator_type>
   void 样本(F someFunctor, 双下, 双上,
               输出迭代器类型输出）{
       双 t = (下 + 上)/2;
       eval_point 点 = { t, f(t) };
   
       if (f(上) - point.value > epsilon) {
           *输出=点；
           ++输出；
           样本（f，t，上部，输出）；
       }
       if (point.value - f(下) > epsilon) {
           *输出=点；
           ++输出；
           subsample2 = 样本(f, lower, t, out);
       }
   }
   

   上面是对伪代码的修改，显示了使用输出迭代器时的样子。它没有经过测试，所以我不确定它是否正确。原则上，您可以这样称呼它：

   std::vector;结果;
   样本(someFunction, 0, 100, std::back_inserter(结果));
   

   这样您就不必为每个递归调用创建新的向量。如果您可以猜测样本数量的合理下限，您也许能够进行预分配，这样就不需要重新分配。在这种情况下，您可以这样称呼它：

   std::vector;结果（lower_bound_for_samples）；
   样本(someFunction, 0, 100, results.begin());
   

然后您必须添加一个额外的计数器来跟踪生成了多少个样本。

Answer 3

我不明白你为什么拒绝列表解决方案。
最坏的情况是您的列表大小是原始数据的 3 倍。
我认为这远远少于在每个函数调用上创建新向量时所拥有的。
您应该尝试一下，因为它不需要太多更改，因为两者的界面几乎相同。