Лучше, чем если бы иначе, если бы еще... для линейной интерполяции

Ответ 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));
}

Ответ 2

Сохраняйте отсортированные точки:

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

Затем переходим от max к min и как только вы становитесь ниже числа, которое вы знаете, это тот, который вы хотите.

Вы хотите сказать say 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

Ответ 3

Вы можете использовать двоичное дерево поиска для хранения данных интерполяции. Это полезно, когда у вас есть большой набор 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);
}

Ответ 4

Да, я думаю, вы должны подумать о карте между этими интервалами и естественными цифрами. Я имею в виду, просто назовите интервалы и используйте переключатель:

switch(I) {

    case Int1: //whatever
        break;

      ...

    default:

}

Я не знаю, это первое, о чем я думал.

EDIT Коммутатор более эффективен, чем if-else, если ваши номера находятся в относительном небольшом интервале (что-то, что нужно учитывать при выполнении сопоставления)

Ответ 5

Как вы уже получили это, достаточно читабельны и понятны, и многое можно сказать об этом "умном" решении. Однако вы можете справиться с проверкой нижних границ и неуклюжей &&, потому что последовательность упорядочена:

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

Ответ 6

Если ваши координаты x должны располагаться нерегулярно, сохраните x-координаты в отсортированном порядке и используйте бинарный поиск, чтобы найти ближайшую координату, например, используя ответ Даниэля Флейшмана.

Однако, если ваша проблема позволяет это, рассмотрите предварительную интерполяцию на регулярные интервалы данных. Так

   5 15
   7 18
   10 22

становится

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

Затем во время выполнения вы можете интерполировать с помощью O (1), используя что-то вроде этого:

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

используя

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

Это не обязательно подходит для каждой проблемы - вы можете потерять точность (если нет хорошей сетки, содержащей все ваши x-образцы), и это может привести к плохим кэш-штрафам, если это сделает вашу таблицу намного больше. Но это хороший вариант для случаев, когда у вас есть некоторый контроль над x-координатами для начала.