c++ - 递归填充动态大小向量

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将不会花费大量时间。

所以我的问题：

您是否看到在所有递归调用中使用相同数据结构并仅填充该向量的当前部分的巧妙方法？（请记住，所需的函数评估数量是未知的）。对此的想法：
- 使用列表而不是向量。但我觉得内存大修不足以存储双打。
- 在向量中保留孔并维护另一个向量，说明哪些条目已填充。递归调用的结束移动条目，以便subsamples 和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)

我正在寻找递归构建这些向量的最佳（性能最高）方法。

希望这可以澄清事情。

score 2 · Accepted Answer

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

1. 使用按引用复制而不是按（返回）值复制。

2. 函子是常数，不需要传入。

low3. 如果和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);
       }   
    }

score 1 · Accepted Answer

我会推荐以下方法：

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

struct eval_point {
    double parameter;
    double value;
};

std::vector<eval_point> evaluated_points;

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

template<class F, class output_iterator_type>
void sample(F someFunctor, double lower, double upper,
            output_iterator_type out) {
    double t = (lower + upper)/2;
    eval_point point = { t, f(t) };

    if (f(upper) - point.value > epsilon) {
        *out = point;
        ++out;
        sample(f, t, upper, out);
    }
    if (point.value - f(lower) > epsilon) {
        *out = point;
        ++out;
        subsample2 = sample(f, lower, t, out);
    }
}

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

std::vector<eval_point> results;
sample(someFunction, 0, 100, std::back_inserter<eval_point>(results));

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

std::vector<eval_point> results(lower_bound_for_samples);
sample(someFunction, 0, 100, results.begin());

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

score 0 · Accepted Answer

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

c++ - 递归填充动态大小向量

3 回答 3

Related

Reference