比其他更好的方法if else else ...用于线性插值

Question

问题很简单.让我们说你有功能

double interpolate (double x);

并且你有一张表有已知x-> y的地图,
例如
5 15
7 18
10 22
注意:真实表格更大,这只是一个例子.

所以对于8你将返回18 +((8-7)/(10-7))*(22-18)= 19.3333333

我发现的一个很酷的方法是 http://www.bnikolic.co.uk/blog/cpp-map-interp.html (长话短说它使用std :: map,key = x,value = y代表x-> y数据对).

如果有人问起标题中的if else else方式是什么,它基本上是:

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

那么有更聪明的方法来做到这一点,还是地图方式是最先进的？:)

顺便说一下,我更喜欢C++中的源代码,但显然任何具有1:1映射到C++的语言解决方案都很好.

Answer 1

好吧,我能想到的最简单的方法就是使用二分搜索找到你的观点所在.如果可以,尽量避免地图,因为它们在实践中非常慢.

这是一个简单的方法:

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 2

您可以使用二叉搜索树来存储插值数据。当您有大量 N 个插值点时，这非常有用，因为插值可以在 O(log N) 时间内执行。然而，在你的例子中，情况似乎并非如此，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 3

是的，我想你应该在这些间隔和自然数之间的映射中思考。我的意思是，只需标记间隔并使用开关：

switch(I) {

    case Int1: //whatever
        break;

      ...

    default:

}

我不知道，这是我第一个想到的。

如果您的数字在相对较小的区间内（这是进行映射时需要考虑的事情），则EDIT Switch 比 if-else 更有效