Ишю формулу (алгоритм)

Новый комментарий
 

Ищу итерационную формулу расчета коэффициента корреляции или готовый алгоритм.

Есть вот такая процедура (https://ru.wikipedia.org/wiki/Корреляция)

//+----------------------------------------------------------------------------+
//|  Автор    : Ким Игорь В. aka KimIV,  http://www.kimiv.ru                   |
//+----------------------------------------------------------------------------+
//|  Версия   : 10.05.2008                                                     |
//|  Описание : Возвращает корреляцию двух рядов.                              |
//+----------------------------------------------------------------------------+
//|  Параметры:                                                                |
//|    x - массив значений первого ряда                                        |
//|    y - массив значений второго ряда                                        |
//+----------------------------------------------------------------------------+
double Correlation(double& x[], double& y[]) {
  double co=0, sa=0, sb=0, sc=0, xs=0, ys=0;
  int    i, k=MathMin(ArraySize(x), ArraySize(y));

  if (k>0) {
    for (i=0; i<k; i++) {
      xs+=x[i]; ys+=y[i];
    }
    xs/=k; ys/=k;
    for (i=0; i<k; i++) {
      sa+=(x[i]-xs)*(y[i]-ys);
      sb+=(x[i]-xs)*(x[i]-xs);
      sc+=(y[i]-ys)*(y[i]-ys);
    }
    sb=MathSqrt(sb*sc);
    if (sb!=0) co=sa/sb;
  }
  return(co);
} 

Но при больших массивах комп тормозит. Есть ли более быстрые алгоритмы ?

Заранее Спасибо.

 
Вместо первого цикла можно использовать встроенную функцию MA on Array. Вместо вычислений sc и sb - StD on Array. Функции для ковариации, к сожалению нет, всё равно приходится считать в цикле.
 
Prival писал(а) >>

Ищу итерационную формулу расчета коэффициента корреляции или готовый алгоритм.



Ю.П. Лукашин "Адаптивные методы краткосрочного прогнозирования временных рядов" М. "Финансы и статистика", 2003.
Там кое-что есть на счет итерационного вычисления коэффициента корреляции. Правда нужно проверять, подходит ли предложенный там алгоритм под ваши нужды, т.к. он весьма необычен.

 
Пирсона можно попробовать, не сильно быстрее будет
double Pearson(double arr1[], double arr2[],int count, int startIndex=0){
   double sumXY = 0, sumX = 0, sumY = 0,sumXs = 0, sumYs = 0, res = 0;     
   
   for(int i = startIndex; i < count + startIndex; i++){
      sumXY += arr1[i] * arr2[i];
      sumX += arr1[i];
      sumY += arr2[i];
      sumXs += arr1[i] * arr1[i];
      sumYs += arr2[i] * arr2[i];     
   }    
   res = NormalizeDouble( (count * sumXY - sumX * sumY) /
                                    MathSqrt( (count * sumXs - sumX * sumX) *
                                    (count * sumYs - sumY * sumY) ),8);       
   return(res);
}
 

Здесь есть через БПФ https://www.mql5.com/go?link=http://dmilvdv.narod.ru/SpeechSynthesis/index.html?correlation.html
Вроде реализовано на mql здесь: https://www.mql5.com/ru/code/9696
void fastcorellation(double& signal[], int signallen, double& pattern[], int patternlen);

 

Спасибо за помощь, но

Avals

Использование БПФ накладывает ограничение на длину массива, должен быть кратен 2^n, но даже в этом случае он медленнее.

Keekkenen

Алгоритмов где есть вот такое sumX * sumY старайся избегать там есть подводный камень, вот тут эти грабли показаны

https://www.mql5.com/ru/forum/107476/page46#101579

https://www.mql5.com/ru/forum/107017/page5

lea

спасибо буду рыться.

timbo

спасибо за идею попробую, пусть это и не кардинальное решение, но хоть чуть быстрее будет и то лучше.

 

З.Ы. задача вроде бы проста, пришла новая котировка, в одном из массивов измениться только первый элемент, остальные сдвинуться (последний элемент ушол), и из-за этого пересчитывать КК по новой ((. Как то не эффективно, должно быть что то. более быстрое…

 

З.Ы. задача вроде бы проста, пришла новая котировка, в одном из массивов измениться только первый элемент, остальные сдвинуться (последний элемент ушол), и из-за этого пересчитывать КК по новой ((. Как то не эффективно, должно быть что то. более быстрое…


Не надо на каждом тике гонять циклы по пересчету сумм.
Надо вычитать 1-ый элемент суммы и добавлять новый последний.
Полностью суммы надо пересчитывать периодически, иначе погрешность копится.

 
Prival >>:
Использование БПФ накладывает ограничение на длину массива, должен быть кратен 2^n, но даже в этом случае он медленнее.

Это очень странно, должно быть быстрее.

Во втором цикле почему-то по три раза вычисляются x[i]-xs и y[i]-ys, их можно и нужно вычислить один раз.

Возможно можно обойтись и без второго цикла, но, как уже сказал выше PapaYozh, придётся предохраняться от накопления погрешности.

 
Prival:

Ищу итерационную формулу расчета коэффициента корреляции или готовый алгоритм.

Если использовать такую  формулу расчета ковариации, несложно вывести рекурентную формулу ковариации.

Поскольку Corr(X, Y) = Cov(X, Y) / Sqrt(Cov(X, X) * Cov(Y, Y)), то для рекурентного получения КК достаточно знать рекурентный расчет ковариации.

Для расчета КК понадобится с собой таскать только ковариационную матрицу 2x2, или 3 (Cov(X, X), Cov(Y, Y), Cov(X, Y)) значения (4-е повторяется) ковариации.

Проблем с накоплением ошибки никаких нет даже после десятков тысяч итераций. Единственный нюанс, если Cov(X, X) <= 0, присваивать ноль ковариации и КК. 

 
Если это повторяющиеся рассчеты- то можно их закэшировать в массиве.
Cache[время рассчета][параметр 1][параметр 2][ ... ] = Результат
Время на вычисления впоследствии будет равно 0.
 
В рекурентной формуле повторяющихся расчетов нет.
12
Новый комментарий