在我的案例中，我可以计算一个元素而不循环遍历所有前面的元素（请参阅问题正文）吗？

Question

我有 2 个相同长度的双精度数组。数组a填充了一些数据，数组b要进行计算。

数组 b 的每个元素等于数组 a 中的相应值加上数组 b 中所有先前元素的加权和。

加权和的计算方法是将所有这些元素相加，每个元素乘以一个系数，该系数等于其与我们计算的当前元素的距离除以前一个子集中的元素数量。

为了实现这一点，我循环遍历我计算的每个元素的整个前面的子集。

这个可以优化吗？我没有足够的数学技能，但我怀疑我只能使用第一个前面的元素来计算下一个元素，因为每个元素都已经从前面的集合中派生出来，并且包含它已经加权的所有信息。也许我可以调整权重公式并获得相同的结果，而无需第二级循环？

这似乎是 Scala 中的一个例子（我不确定它是否正确:-]​​）。由于实际项目使用负索引，因此根据上面所写的任务，将 a(1) 和 a(2) 视为 a(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)< 来写 b(i+1) /code> 我们会做到的。

问题是每个权重都取决于 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

这是 b 的方程吗？
（来自 http://texify.com/?$b[k]%20=%20a[k]% 20+%20\frac{\sum_{i%20=%200}^{k%20-%201}{a[i]%20/%20(ki)}}{k%20-%201}$ )

Answer 4

你说：

通过添加所有这些元素，每个元素乘以一个系数，该系数等于我们计算的与当前元素的距离

很可能您无法从先前的元素预测当前元素，因此您至少必须计算每个元素的这些距离：距离(i,j)，其中i < n和j＜我。这意味着循环两次。

我认为如果距离是线性函数，那么这可以优化，但通常距离是非线性的（因此它是正的）。所以我的猜测是你必须循环两次。

Answer 5

需要考虑三种不同的情况。

(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+ab)*x1+.. . = (d1-a)*x1+(ab)*x1+... 这表明我们只需要 x 值和 <距离从旧答案中得到新答案。所以：

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) 随着您的前进，权重的变化并不一致。到平面上点的距离往往具有该属性，因为平方根的非线性基本上意味着您必须重新计算每个点。所以你每次只需要进行整个计算。