比其他方式更好的方法...线性插值 [英] Better way than if else if else... for linear interpolation

问题描述

问题很容易. 可以说你有功能

question is easy. Lets say you have function

double interpolate (double x);

，您有一个表，该表具有已知x-> y
的映射 例如
5 15
7 18
10 22
注意:实际表更大，这只是示例.

and you have a table that has map of known x-> y
for example
5 15
7 18
10 22
note: real tables are bigger ofc, this is just example.

因此，对于8，您将返回18 +((8-7)/(10-7))*(22-18)= 19.3333333

so for 8 you would return 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).

One cool way I found is http://www.bnikolic.co.uk/blog/cpp-map-interp.html (long story short it uses std::map, key= x, value = y for x->y data pairs).

如果有人问标题是否为if if else else 基本上是:

If somebody asks what is the if else if else way in title it is basically:

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

那么，有没有更聪明的方法可以做到这一点呢? :)

So is there a more clever way to do it or map way is the state of the art? :)

顺便说一句，我更喜欢C ++中的Soutions，但是显然任何将1:1映射到C ++的语言解决方案都是不错的.

Btw I prefer soutions in C++ but obviously any language solution that has 1:1 mapping to C++ is nice.

推荐答案

好吧，我能想到的最简单的方法就是使用二进制搜索来找到您要点所在的点.如果可以的话，请尽量避免使用地图，因为它们在实践中非常慢.

Well, the easiest way I can think of would be using a binary search to find the point where your point lies. Try to avoid maps if you can, as they are very slow in practice.

这是一种简单的方法:

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

这篇关于比其他方式更好的方法...线性插值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！