Есть ли Polyval (функция Matlab) в C ++ STL? - PullRequest
Новая
       81

Есть ли Polyval (функция Matlab) в C ++ STL?

1 голос
/ 25 февраля 2020

Мне нужно оценить полином (1 измерение) некоторой степени (<10) в нескольких точках. Например, при расчете для полинома <code>p(x) = 4x^3 + 2*x^2 -2*x + 5, при x = 0, x= 2 результат должен быть: [5, 41]. Не удалось найти эквивалентную функцию для Matlab Polyval .

Точность результата для меня не критична (может быть округлена до целого числа), но время вычисления равно.

Мое простое решение: 

#include<iostream>
#include<vector>
#include<math.h>

std::vector<double> Polyval(std::vector<double> coeffs, std::vector<double> values)
{
  std::vector<double> results;
    for (auto const &val:values)
        {
          double result = 0;
          for (int i = 0, deg = coeffs.size() - 1; deg >= 0; deg--, i++)
            {
                result += coeffs[i] * std::pow(val, deg);
            }
          results.push_back (result);
        }
        return results;
}

int main()
{
  std::vector<double> coeffs = { 4, 2, -2, 5};
  std::vector<double> valuesToEvaluate = { 0, 2 , -4};
  std::vector<double> results = Polyval (coeffs, valuesToEvaluate);

  for (auto const &res:results)
    {
      std::cout << res << std::endl;
    }
}

Не уверен, есть ли лучший способ с точки зрения производительности.

1 Ответ

1 голос
/ 25 февраля 2020

Как предлагается в комментариях, я теперь использую метод Хорнера, основанный на реализации полиномиальной оценки в Boost. Основные различия:

  1. Порядок полиномов - в этом решении, аналогично Matlab, высшая полиномиальная степень - первая. Например: p(x) = 4x^3 + 2*x^2 -2*x + 5 представляется как vector как этот { 4, 2, -2, 5}

  2. Оценивает несколько значений. 

#include<assert.h>
#include<vector>

std::vector<double> Polyval(std::vector<double> coeffs, std::vector<double> values)
{
  assert(coeffs.size() > 0);
  std::vector<double> results;
  for (auto const &val:values)
  {
      double result = coeffs[0];
      for (int i = 1; i < coeffs.size(); i++)
        {
            result *= val;
            result += coeffs[i];
        }
        results.push_back (result);
    }
    return results;
}

Редактировать: Добавление метрик производительности двух методов (используя pow() против метод Хорнера )

Метрики

Полином: p(x) = 4*x^5 + 2*x^4 -2*x^3 + 5*x + 15

Прогоны: 10 000

Очки для оценки: {0, 2, -4, 8, 15, 1.25, 512 ,-5.3 ,12.215, 153, 23, -11}

Тип сборки: RELEASE

Продолжительность: pow - 46 576 [микросекунд] против Хорнера -6 500 [микросекунд ]

Разница в длительности: ~ в 7 раз быстрее (в пользу метода Хорнера)

Примерная измеренная продолжительность для обеих реализаций: 

#include<iostream>
#include<assert.h>
#include<vector>
#include<chrono>

    int iter = 10000;
    std::vector<double> coeffs = { 4, 2, -2, 5, 0, 15};
    std::vector<double> valuesToEvaluate = {0, 2, -4, 8, 15, 1.25, 512 ,-5.3 
    ,12.215, 153, 23, -11};
    auto start = std::chrono::high_resolution_clock::now();

    do{
    std::vector<double> results = Polyval(coeffs, valuesToEvaluate);
    }
    while(iter-->0);

    auto end = std::chrono::high_resolution_clock::now();
    long duration = std::chrono::duration_cast<std::chrono::microseconds>(end - 
    start).count();

    std::cout << duration << std::endl;
...