7

我有 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))
4

5 回答 5

2

我假设距离是两个元素的绝对差。

如果我理解正确，每个元素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)（更糟糕的是，它是绝对差异）。

这就是为什么我们不能再简化上述内容，也不能从每个总和中“提取”知识以在下一个总和中使用它。

于 2010-11-03T08:56:19.347 回答
1

这就是你想要做的？

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

只有找到一个等价的函数来替换，才能优化嵌套循环g。实际上，我不知道weighted sum的确切含义。估计是

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]);
}
于 2010-11-03T08:43:22.467 回答
0

这是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}$)

替代文字

于 2010-11-03T08:49:00.963 回答
0

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

(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值的总和和一个距离即可从旧的值中获得新的答案。所以：

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

于 2010-11-03T14:46:24.923 回答
0

你说：

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

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

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

于 2010-11-03T12:56:18.723 回答