更好的方法比如果其他如果...線性插值

Question

問題很容易。 可以說，你有功能

double interpolate (double x); 

，你必須具有已知的X->ý
例如
音符的地圖的表：實表格比較大，這只是一個例子。

所以你8將返回18 +（（8-7）/（10-7））*（22-18）=我發現19.3333333

一個很酷的方式是 http://www.bnikolic.co.uk/blog/cpp-map-interp.html （長話短說它對x-> y數據對使用std :: map，key = x，value = y）。

如果有人問什麼，如果不然，如果標題 其他方式，它基本上是：

if ((x>=5) && (x<=7)) 
{ 
//interpolate 
} 
else 
    if((x>=7) && x<=10) 
    { 
     //interpolate 
    } 

那麼，有沒有一種更聰明的方法做，或地圖的方式是藝術的狀態？ :)

btw我更喜歡在C++ soutions，但顯然任何語言的解決方案，有1：1映射到C++是很好的。

Answer 1

是的，我猜你應該在這些間隔和自然數之間的映射中考慮。我的意思是，只需標記間隔並使用開關：

switch(I) { 

    case Int1: //whatever 
     break; 

     ... 

    default: 

} 

我不知道，這是我第一次想到的。

編輯交換機的效率比的if-else，如果你的號碼是一個相對較小的區間內（這件事情做映射時要考慮到）

Answer 2

存儲您的積分排序：

index X Y 
1  1 -> 3 
2  3 -> 7 
3  10-> 8 

然後從max到min循環，只要你低於一個數字，你就知道它是你想要的。

你要假設6這樣：

// pseudo 
for i = 3 to 1 
    if x[i] <= 6 
    // you found your range! 
    // interpolate between x[i] and x[i - 1] 
    break; // Do not look any further 
    end 
end 

Answer 3

如何你已經得到它是相當易於閱讀和理解，而且有很多關於這在「聰明」的解決方案可說。但是，您可以廢除下界檢查和笨拙&&因爲順序排列：

if (x < 5) 
    return 0; 
else if (x <= 7) 
    // interpolate 
else if (x <= 10) 
    // interpolate 
... 

Answer 4

可以使用二叉搜索樹來存儲插值數據。當您有大量的N個插值點時，這是有利的，因爲隨後可以在O（logN）時間內執行插值。但是，在您的示例中，似乎並不是這種情況，RedX建議的線性搜索更合適。

#include <stdio.h> 
#include <assert.h> 

#include <map> 

static double interpolate (double x, const std::map<double, double> &table) 
{ 
    assert(table.size() > 0); 

    std::map<double, double>::const_iterator it = table.lower_bound(x); 

    if (it == table.end()) { 
     return table.rbegin()->second; 
    } else { 
     if (it == table.begin()) { 
      return it->second; 
     } else { 
      double x2 = it->first; 
      double y2 = it->second; 
      --it; 
      double x1 = it->first; 
      double y1 = it->second; 
      double p = (x - x1)/(x2 - x1); 
      return (1 - p) * y1 + p * y2; 
     } 
    } 
} 

int main() 
{ 
    std::map<double, double> table; 
    table.insert(std::pair<double, double>(5, 6)); 
    table.insert(std::pair<double, double>(8, 4)); 
    table.insert(std::pair<double, double>(9, 5)); 

    double y = interpolate(5.1, table); 

    printf("%f\n", y); 
} 

Answer 5

那麼，我能想到的最簡單的方法是使用二進制搜索來找到你的觀點所在的位置。儘量避免使用地圖，因爲它們在練習中速度很慢。

這是一個簡單的方法：

const double INF = 1.e100; 
vector<pair<double, double> > table; 
double interpolate(double x) { 
    // Assumes that "table" is sorted by .first 
    // Check if x is out of bound 
    if (x > table.back().first) return INF; 
    if (x < table[0].first) return -INF; 
    vector<pair<double, double> >::iterator it, it2; 
    // INFINITY is defined in math.h in the glibc implementation 
    it = lower_bound(table.begin(), table.end(), make_pair(x, -INF)); 
    // Corner case 
    if (it == table.begin()) return it->second; 
    it2 = it; 
    --it2; 
    return it2->second + (it->second - it2->second)*(x - it2->first)/(it->first - it2->first); 
} 
int main() { 
    table.push_back(make_pair(5., 15.)); 
    table.push_back(make_pair(7., 18.)); 
    table.push_back(make_pair(10., 22.)); 
    // If you are not sure if table is sorted: 
    sort(table.begin(), table.end()); 
    printf("%f\n", interpolate(8.)); 
    printf("%f\n", interpolate(10.)); 
    printf("%f\n", interpolate(10.1)); 
} 

Answer 6

如果你的x座標必須被不規則地間隔開，然後將其存儲在有序的x座標，並使用二進制搜索找到最近的座標，例如使用Daniel Fleischman的回答。

但是，如果您的問題允許，請考慮預先插值以定期分隔數據。所以

 
    5 15 
    7 18 
    10 22 

成爲

 
    5 15 
    6 16.5 
    7 18 
    8 19.3333333 
    9 20.6666667 
    10 22 

然後在運行時，你可以：（1）使用像這樣帶O插值：使用

double y[6] = {15,16.5,18,19.3333333, 20.6666667, 22 } 
double yi = interp1(5.0 , 1.0 , y, 5, xi); 

這

double interp1(double x0, double dx, double* y, int n, double xi) 
{ 
    double f = (xi - x0)/dx; 
    if (f<0) return y[0]; 
    if (f>=(n-1)) return y[n-1]; 
    int i = (int) f; 
    double w = f-(double)i; 
    return dy[i]*(1.0-w) + dy[i+1]*w; 
} 

不一定適合每一個概率lem--你最終會失去準確性（如果沒有包含所有x-樣本的好網格），並且如果它會使你的表格變得更大，它可能會導致緩存懲罰不佳。但是，對於首先控制x座標的情況，這是一個很好的選擇。