7

同じ長さの Double の配列が 2 つあります。配列 a にはいくつかのデータが入り、配列 b は計算されます。

配列 b の各要素は、配列 a の対応する値に、配列 b の先行するすべての要素の加重合計を加えた値に等しくなります。

重み付けされた合計は、すべての要素に係数を掛けて加算することによって計算されます。この係数は、計算した現在の要素からの距離を前のサブセットの要素数で割った値に等しくなります。

これを実装するために、計算する要素ごとに前のサブセット全体をループします。

これは最適化できますか？私は十分な数学のスキルを持っていませんが、すべての要素がすでに前のセットから派生しており、すでに重み付けされたすべての情報を含んでいるため、最初の前の要素を使用して次のすべてを計算することしかできないと思います。たぶん、重みの式を調整するだけで、第 2 レベルのループなしで同じ結果を得ることができますか?

これは 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

距離は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。実際、加重合計の正確な意味はわかりません。たぶん、それは

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

あなたが言った：

これらのすべての要素を追加して、計算した現在の要素からの距離に等しい係数をそれぞれ掛けます

ほとんどの場合、前の要素から現在の要素を予測することはできないため、少なくとも各要素の距離を計算する必要があります: distance(i,j) where i < n and j < i. これは、2 回ループすることを意味します。

距離が線形関数である場合、これは最適化できると思いますが、従来、距離は非線形です（正になるように）。したがって、2 回ループする必要があると思います。

于 2010-11-03T12:56:18.723 に答える
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

考慮すべき 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

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 に答える