Un problème intéressant. Je peux penser à de nombreuses solutions, avec des degrés d'efficacité variables. Le fait de devoir ajouter des éléments à plusieurs reprises n'est pas vraiment un problème de performance, mais supposons que ce soit le cas. De plus, les zéros au début peuvent être ajoutés plus tard, donc ne nous inquiétons pas de les produire. Si l'algorithme les fournit naturellement, tant mieux ; sinon, nous corrigerons plus tard.
En commençant par Scala 2.8, le résultat suivant serait obtenu pour n >= period en utilisant sliding pour obtenir une fenêtre coulissante de la liste :
def simpleMovingAverage(values: List[Double], period: Int): List[Double] =
List.fill(period - 1)(0.0) ::: (values sliding period map (_.sum) map (_ / period))
Néanmoins, bien que cette méthode soit plutôt élégante, elle n'offre pas les meilleures performances possibles, car elle ne tire pas profit des additions déjà calculées. Donc, en parlant d'eux, comment pouvons-nous les obtenir ?
Disons que nous écrivons ceci :
values sliding 2 map sum
Nous avons une liste de la somme de chacune des deux paires. Essayons d'utiliser ce résultat pour calculer la moyenne mobile de 4 éléments. La formule ci-dessus a permis de faire le calcul suivant :
from d1, d2, d3, d4, d5, d6, ...
to (d1+d2), (d2+d3), (d3+d4), (d4+d5), (d5+d6), ...
Ainsi, si nous prenons chaque élément et l'ajoutons au deuxième élément suivant, nous obtenons la moyenne mobile pour 4 éléments :
(d1+d2)+(d3+d4), (d2+d3)+(d4+d5), (d3+d4)+(d5+d6), ...
Nous pouvons le faire comme ceci :
res zip (res drop 2) map Function.tupled(_+_)
Nous pourrions alors calculer la moyenne mobile pour 8 éléments, et ainsi de suite. Il existe un algorithme bien connu pour calculer les choses qui suivent un tel modèle. Il est surtout connu pour son utilisation dans le calcul de la puissance d'un nombre. Il se présente comme suit :
def power(n: Int, e: Int): Int = e match {
case 0 => 1
case 1 => n
case 2 => n * n
case odd if odd % 2 == 1 => power(n, (odd - 1)) * n
case even => power(power(n, even / 2), 2)
}
Alors, appliquons-le ici :
def movingSum(values: List[Double], period: Int): List[Double] = period match {
case 0 => throw new IllegalArgumentException
case 1 => values
case 2 => values sliding 2 map (_.sum)
case odd if odd % 2 == 1 =>
values zip movingSum(values drop 1, (odd - 1)) map Function.tupled(_+_)
case even =>
val half = even / 2
val partialResult = movingSum(values, half)
partialResult zip (partialResult drop half) map Function.tupled(_+_)
}
Donc, voici la logique. La période 0 est invalide, la période 1 est égale à l'entrée, la période 2 est une fenêtre glissante de taille 2. Si elle est supérieure, elle peut être paire ou impaire.
Si c'est le cas, nous ajoutons chaque élément à l'ensemble des éléments de la liste. movingSum du prochain (odd - 1) éléments. Par exemple, s'il s'agit de 3, nous ajoutons chaque élément à la liste des movingSum des 2 éléments suivants.
S'il est pair, nous calculons le movingSum para n / 2 puis ajouter chaque élément à celui n / 2 les étapes suivantes.
Avec cette définition, nous pouvons alors revenir au problème et faire ceci :
def simpleMovingAverage(values: List[Double], period: Int): List[Double] =
List.fill(period - 1)(0.0) ::: (movingSum(values, period) map (_ / period))
Il y a une légère inefficacité en ce qui concerne l'utilisation de ::: mais c'est O(period), pas O(values.size). Il peut être rendu plus efficace avec une fonction récursive de queue. Et, bien sûr, la définition de "sliding" que j'ai fournie est horrible du point de vue des performances, mais il y aura une bien meilleure définition de ce terme dans Scala 2.8. Notez que nous ne pouvons pas faire une fonction sliding sur un List mais nous pouvons le faire sur un Iterable .
Cela dit, j'opterais pour la toute première définition, et je n'optimiserais que si une analyse du chemin critique mettait en évidence l'importance du problème.
Pour conclure, voyons comment j'ai abordé le problème. Nous avons un problème de moyenne mobile. Une moyenne mobile est la somme d'une "fenêtre" mobile sur une liste, divisée par la taille de cette fenêtre. Donc, d'abord, j'essaie d'obtenir une fenêtre mobile, de faire la somme de tout ce qui s'y trouve, puis de diviser par la taille.
Le problème suivant était d'éviter la répétition d'additions déjà calculées. Dans ce cas, j'ai choisi l'addition la plus petite possible, et j'ai essayé de comprendre comment calculer des sommes plus importantes en réutilisant ces résultats.
Enfin, essayons de résoudre le problème de la manière dont vous l'avez imaginé, en ajoutant et en soustrayant au résultat précédent. Obtenir la première moyenne est facile :
def movingAverage(values: List[Double], period: Int): List[Double] = {
val first = (values take period).sum / period
Maintenant, nous faisons deux listes. D'abord, la liste des éléments à soustraire. Ensuite, la liste des éléments à ajouter :
val subtract = values map (_ / period)
val add = subtract drop period
Nous pouvons ajouter ces deux listes en utilisant zip . Cette méthode ne produira qu'autant d'éléments que la liste la plus petite a d'éléments, ce qui évite le problème des subtract être plus grand que nécessaire :
val addAndSubtract = add zip subtract map Function.tupled(_ - _)
On termine en composant le résultat avec un pli :
val res = (addAndSubtract.foldLeft(first :: List.fill(period - 1)(0.0)) {
(acc, add) => (add + acc.head) :: acc
}).reverse
qui est la réponse à renvoyer. L'ensemble de la fonction ressemble à ceci :
def movingAverage(values: List[Double], period: Int): List[Double] = {
val first = (values take period).sum / period
val subtract = values map (_ / period)
val add = subtract drop period
val addAndSubtract = add zip subtract map Function.tupled(_ - _)
val res = (addAndSubtract.foldLeft(first :: List.fill(period - 1)(0.0)) {
(acc, add) => (add + acc.head) :: acc
}).reverse
res
}
