Puis-je calculer un élément sans boucler tous les éléments précédents dans mon cas (voir le corps de la question)?

Question

J'ai 2 tableaux de doubles de la même longueur. Le tableau a est rempli de certaines données, le tableau b doit être calculé.

Chaque élément du tableau b est égal à une valeur correspondante du tableau a plus une somme pondérée de tous les éléments précédents dans le tableau b.

Une somme pondérée est calculée en additionnant tous les éléments multipliés par un coefficient égal à sa distance de l'élément courant que nous calculons divisé par le nombre d'éléments du sous-ensemble précédent.

Pour implémenter cela, je boucle tout le sous-ensemble précédent pour chaque élément que je calcule.

Est-ce que cela peut être optimisé? Je n'ai pas assez de compétences en maths, mais je suppose que je ne pourrais utiliser que le premier élément précédent pour calculer chaque prochain car chaque élément est déjà dérivé de l'ensemble précédent et contient toutes les informations déjà pondérées. Peut-être que je peux juste ajuster la formule de poids et obtenir le même résultat sans boucle de deuxième niveau?

Cela semble être un exemple dans Scala (je ne suis pas sûr si c'est correct: -]). Comme le projet réel utilise des indices négatifs, traitez un (1) et un (2) comme un précédent (0) en fonction de la tâche écrite ci-dessus.

 

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

C'est ce que vous essayez de faire?

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

La boucle imbriquée ne peut être optimisée si l'on peut trouver une fonction équivalente pour remplacer g. En fait, je ne connais pas la signification exacte de somme pondérée. Je suppose, il est

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

(ajout de toutes les valeurs et en divisant par le nombre de valeurs)

Dans ce cas, vous pouvez stocker la somme et le réutiliser:

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

Cela éliminerait la boucle imbriquée.

En termes de Java (outils ma idée d'une somme pondérée ):

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 2

Est-ce l'équation de b?
(à partir de http://texify.com/? $ B [k]% 20 =% 20a [k]% 20 +% 20 \ frac {\ somme_ {i% 20 =% 200}^{k% 20-% 201} {a [i ]% 20 /% 20 (ki)}} {k% 20-% 201} $)

Answer 3

Je ne sais pas comment écrire les types mathématiques ici, mais je vais essayer. Je suppose que la distance est la différence absolue de deux éléments.

Si je bien compris chaque élément de b doit être:

b (i) = a (i) + somme (j = 1 à i-1) (a (j) * (abs (a (i) - a (j))/i)

b (i) = a (i) + somme (j = 1 à i-1) (abs (a (j) * a (j) - un (j) * a (i))/i)

maintenant, si nous pouvions écrire b (i + 1) en termes de b (i) nous aurait fait.

Le problème est que chaque poids dépend des deux, un (i) et un (j) (et pire encore, c'est le absolu différence). C'est pourquoi nous ne pouvons plus simplifier ce qui précède et ne pouvons pas "extraire" des connaissances de chaque somme pour l'utiliser dans la suivante.

Je vais vérifier cela plus tard, après avoir vérifié un livre, peut-être que je me trompe quelque part.

Answer 4

Vous avez dit:

en ajoutant tous ces éléments chaque multiplié par un coefficient qui est égal à la distance de l'élément courant on calcule

vous ne pouvez pas prédire très probablement l'élément courant de les éléments précédents de sorte que vous devrez au moins calculer ces distances pour chaque élément: distance(i,j) where i < n and j < i. Cela signifie faire une boucle deux fois.

Je pense que cela pourrait être optimisé si la distance était une fonction linéaire, mais classiquement, la distance est non linéaire (de sorte qu'elle est positive). Donc, je suppose que vous devrez faire une boucle deux fois.

Answer 5

Il existe trois cas distincts à prendre en compte.

(1) Les poids ne changent pas.

Exemple/solution:

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) Les poids changent, mais par un facteur d'échelle linéaire comme si elles représentent des distances signées le long d'une ligne. Ensuite, nous laissons (d1-a)*x1 + (d2-a)*x2 + ... + (dn-a)*xn = y être notre réponse précédente, en supposant que nous sommes à a; alors, si nous passons à b, nous pouvons modifier cela comme (d1-b)*x1... = (d1-a+a-b)*x1+... = (d1-a)*x1+(a-b)*x1+... qui montre que nous avons juste besoin de la somme des valeurs x et distance unique pour obtenir la nouvelle réponse de nos anciens. Alors:

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(_ + _ + _) 

La meilleure façon de comprendre comment cela fonctionne est de le prendre à part la déclaration par la déclaration et écrire des choses à la main pour vérifier qu'il est en fait ce que nous calculait voulons calculer.

(3) Les poids changent de manière non uniforme à mesure que vous avancez. Les distances aux points dans un plan ont tendance à avoir cette propriété, puisque la non-linéarité de la racine carrée signifie que vous devez les calculer de nouveau. Il suffit donc de faire le calcul entier à chaque fois.