填寫動態大小的矢量遞歸

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公正，良好，concats返回的載體。基本上，我正在對一個函數進行採樣，使得兩個保存的函數值之間只有很小的差別。

我對上述方式不滿意，因爲在每個遞歸步驟中似乎都有相當多的內存分配（分配兩個子向量，然後將這些和另一個元素連接）。那段代碼必須運行在我的算法中，這對性能至關重要。一旦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

我不明白你爲什麼拒絕列表解決方案。 最糟糕的情況是您的列表比您的原始數據大3倍。 我認爲這遠不如當你在每個函數調用中創建一個新的向量時所擁有的。 你應該嘗試一下，因爲它不需要太多的改變，因爲兩者的界面幾乎相同。

Answer 3

我推薦以下方法：

1. 不要使用兩個向量，但對相當一個載體或自定義struct代表的參數和值：

   struct eval_point { 
       double parameter; 
       double value; 
   }; 
   
   std::vector<eval_point> evaluated_points; 
   

2. 變化您的算法將評估結果寫入輸出迭代器：

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

你將不得不增加一個額外的計數器來跟蹤是如何產生的許多樣品。