Могу ли я рассчитать элемент без циклического прохождения всех предыдущих элементов в моем случае (см. Тело вопроса)?

Question

У меня есть 2 массива двойников одинаковой длины.Массив a заполнен некоторыми данными, массив b должен быть рассчитан.

Каждый элемент массива b равен соответствующему значению из массива a плюс взвешенная сумма всех предыдущих элементов в массиве b.

Взвешенная сумма вычисляется путем сложения всех этих элементов, каждый из которых умножается на коэффициент, равный его расстоянию от текущего элемента, который мы рассчитываем, деленный на количество элементов в предыдущем подмножестве.все предыдущее подмножество для каждого элемента, который я вычисляю.

Можно ли это оптимизировать?У меня недостаточно математических навыков, но я подозреваю, что я мог использовать только первый предыдущий элемент для вычисления каждого следующего, поскольку каждый элемент уже получен из предыдущего набора и содержит всю информацию о нем, уже взвешенном.Может быть, я могу просто скорректировать формулу веса и получить тот же результат без повторения второго уровня?

Это, кажется, пример в Scala (я не уверен, правильно ли это: -]).Поскольку реальный проект использует отрицательные индексы, обрабатывайте a (1) и a (2) как предшествующие (0) с точки зрения задачи, написанной выше.

import scala.Double.NaN
val a = Array[Double] (8.5, 3.4, 7.1, 5.12, 0.14, 5)
val b = Array[Double] (NaN, NaN, NaN, NaN, NaN, 5)
var i = b.length - 2
while (i >= 0) {
  b(i) = a(i) + {
    var succession = 0.0
    var j = 1
    while (i + j < b.length) {
      succession += b (i+j) * (1.0-j.toDouble/(b.length - i))
      j += 1
    }
    succession
  }
  i -= 1
}
b.foreach((n : Double) => println(n))

Answer 1

Я предполагаю, что расстояние - это абсолютная разница двух элементов.

Если я правильно понял, каждый элемент b должен быть:

b(i) = a(i) + sum(j = 1 to i-1) (a(j) * (abs(a(i) - a(j)) / i )

b(i) = a(i) + sum(j = 1 to i-1) ( abs(a(j)*a(j) - a(j)*a(i)) / i )

Теперь, если бы мы могли написать b(i+1) в терминах b(i), мы бы сделали это.

Проблема в том, что каждый вес зависит от a(i) и a(j) (и, что еще хуже, это абсолютная разница).

Вот почему мы больше не можем упрощать вышесказанное и не можем «извлекать» знания из каждой суммы, чтобы использовать их в следующей.

Answer 2

Это то, что вы пытаетесь сделать?

f(x_n) := g(x_0,..,x_(n-1)) + h(x_n)

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

g(x_0,..,x_(n-1)) = (x_0 + ... + x_(n-1)) / (n-1)

(сложение всех значений и деление на количество значений)

В этом случае вы можете сохранить сумму и использовать ее повторно:

a := (x_0 + ... + x_(n-2))
g(x_0,..,x_(n-1)) = (a + x_(n-1)) / (n-1)

Это устранит вложенный цикл.

В терминах Java (реализует мою идею взвешенной суммы ):

double[] x = initX();
double[] y = new double[x.length];
double sum = 0;
y[0] = h(x[0]);
for (int i = 1; i < x.length; i++) {
  sum = sum + x[i-1];    
  y[i] = sum / (i-1) + h(x[i]);
}

Answer 3

Необходимо рассмотреть три отдельных случая.

(1) Веса не меняются.

Пример / решение:

val xs = List(1,2,3,4,5)
val ws = List(3,2,5,1,4)
// Desired:
  // 1
  // 1*3 + 2
  // 1*3 + 2*2 + 3
  // 1*3 + 2*2 + 3*5 + 4
  // 1*3 + 2*2 + 3*5 + 4*1 + 5
val mul = (xs,ws).zipped.map(_ * _)   // 1*3, 2*2, 3*5, etc.
val cuml = mul.scanLeft(0)(_ + _)     // Cumulative sums of the above
val ans = (xs,cuml).zipped.map(_ + _) // Put it all together

(2) Веса меняются, но с помощью линейного масштабного коэффициента, как если бы они представляли знаковые расстояния вдоль линии.Тогда мы позволим (d1-a)*x1 + (d2-a)*x2 + ... + (dn-a)*xn = y быть нашим предыдущим ответом, предполагая, что мы находимся в a;затем, если мы перейдем к b, мы можем изменить это как (d1-b)*x1... = (d1-a+a-b)*x1+... = (d1-a)*x1+(a-b)*x1+..., что показывает, что нам просто нужны суммы значений x и расстояние single , чтобы получитьновый ответ от наших старых.Итак:

val xs = List(1,2,3,4,5)
val ds = List(3,2,5,1,4)              // Treat these as distances along a line
// Desired:
  // 1
  // (3-2)*1 + 2
  // (3-5)*1 + (2-5)*2 + 3
  // (3-1)*1 + (2-1)*2 + (5-1)*3 + 4
  // (3-4)*1 + (2-4)*2 + (5-4)*3 + (1-4)*4 + 5
val ws = ds.map(_ - ds.head)          // Distances from the first element
val mul = (xs,ws).zipped.map(_ * _)
val cuml = mul.scanLeft(0)(_ + _)
// If we used this alone we would get:
  // 1
  // (3-3)*1 + 2            <-- should be subtracting 2, not 3!
  // (3-3)*1 + (2-3)*2 + 3  <-- should be subtracting 5, not 3!
  // etc.
val cumlx = xs.scanLeft(0)(_ + _)             // Need this to fix up our sums
val fix = (cumlx,ws).zipped.map(-1 * _ * _)   // This will actually do it
val ans = (xs,cuml,fix).zipped.map(_ + _ + _)

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

(3) Вес меняется неравномерно по мере вашего продвижения.Расстояния до точек на плоскости, как правило, обладают этим свойством, поскольку нелинейность квадратного корня в основном означает, что вы должны вычислять каждое заново.Так что вам просто нужно каждый раз делать полный расчет.

Answer 4

Вы сказали:

путем добавления всех этих элементов, умноженных на коэффициент, равный его расстоянию от текущего элемента, который мы вычисляем

Скорее всего, вы не можете предсказать текущий элемент из предыдущих элементов, поэтому вам, по крайней мере, придется рассчитать эти расстояния для каждого элемента: distance(i,j) where i < n and j < i. Это означает, что цикл в два раза.

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

Answer 5

Это уравнение для b?
(из http://texify.com/?$b[k]%20=%20a[k]%20+%20\frac{\sum_{i%20=%200}^{k%20-%201}{a[i]%20/%20(k-i)}}{k%20-%201}$)