Le calcul de la Moyenne mobile d'une Liste

Problème intéressant. Je peux penser à de nombreuses solutions, avec des degrés variables d'efficacité. Avoir à ajouter des trucs à plusieurs reprises n'est pas vraiment un problème de performance, mais imaginons qu'il est. Aussi, l'ensemble des zéros au début peut être ajouté plus tard, afin de ne pas laisser s'inquiéter de leur production. Si l'algorithme fournit naturellement, l'amende; si non, nous corriger plus tard.

De départ avec Scala 2.8, le tableau suivant donne le résultat 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 ce soit plutôt élégant, il n'a pas la meilleure performance possible, car elle ne prend pas avantage de s'être déjà calculé ajouts. Si, en parlant d'eux, comment pouvons-nous obtenir?

Disons-nous écrire ceci:

values sliding 2 map sum

Nous avons une liste de la somme de chacune des deux paires. Nous allons essayer d'utiliser ce résultat pour calculer la moyenne mobile de 4 éléments. La formule ci-dessus fait le calcul suivant:

from d1, d2, d3, d4, d5, d6, ...
to (d1+d2), (d2+d3), (d3+d4), (d4+d5), (d5+d6), ...

Donc, si nous prenons chaque élément et l'ajouter à la deuxième élément suivant, nous obtenons la moyenne mobile de 4 éléments:

(d1+d2)+(d3+d4), (d2+d3)+(d4+d5), (d3+d4)+(d5+d6), ...

On peut faire comme ceci:

res zip (res drop 2) map Function.tupled(_+_)

On pourrait alors calculer la moyenne mobile de 8 éléments, et ainsi de suite. Eh bien, il est bien connu de l'algorithme pour calculer les choses qui suivent ce schéma. Il est plus connu pour son utilisation sur le calcul de la puissance d'un nombre. Il va comme ceci:

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)
}

Donc, nous allons appliquer 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, voilà la logique. La période 0 est nulle, la période 1 est égale à l'entrée, de la période 2 est de fenêtre glissante de taille 2. Si grand que cela, il peut être pair ou impair.

S'il est impair, nous ajoutons chaque élément de la movingSum de la prochaine (odd - 1) éléments. Par exemple, si 3, nous ajoutons chaque élément de la movingSum des 2 éléments.

Si même, on calcule la movingSum pour n /2, puis ajouter chaque élément de l'un n /2 étapes par la suite.

Avec cette définition, on peut alors revenir au problème et pour ce faire:

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 il est O(période), pas de O(valeurs.taille). Il peut être rendue plus efficace grâce à une queue de fonction récursive. Et, bien sûr, la définition de "glissement" j'ai fourni, c'est une horreur en terme de performance, mais il y en aura une bien meilleure définition sur Scala 2.8. Notez que nous ne pouvons pas faire un efficace sliding méthode sur un List, mais nous pouvons le faire sur un Iterable.

Après avoir dit tout cela, j'irais avec la première définition, et d'optimiser uniquement si une analyse du chemin critique identifié cela comme une grosse affaire.

Pour conclure, nous examinerons la façon dont je suis allé sur le problème. Nous avons une moyenne mobile de problème. Une moyenne mobile est la somme d'un mouvement de la "fenêtre" sur une liste, divisé par la taille de cette fenêtre. Alors, tout d'abord, j'essaie d'obtenir une fenêtre coulissante, la somme de tout sur elle, et puis la diviser par la taille.

Le problème suivant a été, pour éviter la répétition du déjà calculés ajouts. Dans ce cas, je suis allé à la plus petite plus possible, et essayé de comprendre comment calculer plus sommes la réutilisation de ces résultats.

Enfin, nous allons essayer de résoudre le problème de la manière dont vous avez compris, en ajoutant et en soustrayant du résultat précédent. L'obtention de la première moyenne est facile:

 def movingAverage(values: List[Double], period: Int): List[Double] = {
   val first = (values take period).sum / period

Maintenant nous faire deux listes. Tout d'abord, la liste des éléments à retrancher. Ensuite, la liste des éléments à ajouter:

   val subtract = values map (_ / period)
   val add = subtract drop period

Nous pouvons ajouter à ces deux listes à l'aide de zip. Cette méthode ne pourra produire autant d'éléments que le plus petit de la liste a, qui permet d'éviter le problème de subtract étant plus grand que nécessaire:

   val addAndSubtract = add zip subtract map Function.tupled(_ - _)

Nous avons fini par composer 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
 }

Voici un autre (fonctionnelle) Clojure solution:

(défn avarage [rec] 
(/(réduction + coll) 
(le comte coll))) 

(défn ma [durée rec] 
(carte avarage (partition période du 1er rec))) 

Les zéros au début de la séquence doit encore être ajouté si c'est une exigence.

Voici une partie point-libre une ligne Haskell solution:

ma p = reverse . map ((/ (fromIntegral p)) . sum . take p) . (drop p) . reverse . tails

D'abord elle s'applique queues de la liste pour obtenir les "queues" des listes, donc:

Prelude List> tails [2.0, 4.0, 7.0, 6.0, 3.0]
[[2.0,4.0,7.0,6.0,3.0],[4.0,7.0,6.0,3.0],[7.0,6.0,3.0],[6.0,3.0],[3.0],[]]

L'inverse et les gouttes de la première 'p' entrées (en prenant p 2 ici):

Prelude List> (drop 2 . reverse . tails) [2.0, 4.0, 7.0, 6.0, 3.0]
[[6.0,3.0],[7.0,6.0,3.0],[4.0,7.0,6.0,3.0],[2.0,4.0,7.0,6.0,3.0]]

Dans le cas où vous n'êtes pas familier avec le (.) dot/tétine symbole, c'est l'opérateur pour le fonctionnement de la composition", ce qui signifie qu'il passe à la sortie d'une fonction, comme l'entrée d'une autre, la "composition" dans une seule fonction. (g . f) des moyens de "f run sur une valeur, puis passer la sortie à g", donc (f . g) x) est la même que (g(f x)). Généralement son utilisation conduit à une meilleure style de programmation.

Il alors des cartes de la fonction ((/(fromIntegral p)) . la somme . prendre p) sur la liste. Ainsi, pour chaque liste dans la liste, il prend le premier " p " éléments, les résume, puis divise par 'p'. Alors que nous venons de retourner la liste de retour avec "reverse".

Prelude List> map ((/ (fromIntegral 2)) . sum . take 2) [[6.0,3.0],[7.0,6.0,3.0]
,[4.0,7.0,6.0,3.0],[2.0,4.0,7.0,6.0,3.0]]
[4.5,6.5,5.5,3.0]

Tout cela semble beaucoup plus inefficace qu'il est; "inverse" n'est pas physiquement inverser l'ordre de la liste jusqu'à ce que la liste est évalué, c'est juste la pose sur la pile (good ol' lazy Haskell). les "queues" aussi ne pas créer autant de listes séparées, il vient de références différentes sections de la liste d'origine. C'est toujours pas une bonne solution, mais c'est une ligne longue 🙂

Ici est un peu plus agréable mais plus solution qui utilise mapAccum faire glisser la soustraction et l'addition:

ma p l = snd $ mapAccumL ma' a l'
    where
        (h, t) = splitAt p l
        a = sum h
        l' = (0, 0) : (zip l t)
        ma' s (x, y) = let s' = (s - x) + y in (s', s' /(fromIntegral p))

Nous avons d'abord diviser la liste en deux parties à "p", donc:

Prelude List> splitAt 2 [2.0, 4.0, 7.0, 6.0, 3.0]
([2.0,4.0],[7.0,6.0,3.0])

Somme le premier bit:

Prelude List> sum [2.0, 4.0]
6.0

Zip le deuxième bit avec l'original de la liste (ce seulement les paires d'objets dans l'ordre, les deux listes). L'original de la liste n'est évidemment plus de temps, mais nous perdons ce bit supplémentaire:

Prelude List> zip [2.0, 4.0, 7.0, 6.0, 3.0] [7.0,6.0,3.0]
[(2.0,7.0),(4.0,6.0),(7.0,3.0)]

Maintenant, nous définissons une fonction pour notre mapAccum(ulator). mapAccumL est le même que "la carte", mais avec un supplément de l'exécution de l'état/de l'accumulateur paramètre, qui est passé de la précédente "cartographie" à la suivante que la carte fonctionne par le biais de la liste. Nous utilisons l'accumulateur que notre moyenne mobile, et notre liste est constituée de l'élément qui a juste à gauche de la fenêtre coulissante et l'élément qui vient d'entrer (la liste nous venons de zippée), notre fonction coulissante prend le premier numéro de " x "à l'écart de la moyenne et ajoute le deuxième numéro de "y". On passe ensuite à la nouvelle 's' le long et le retour d'un " s "divisé par "p". "snd" (deuxième) prend juste le deuxième membre d'une paire (n-uplet), qui est utilisé pour prendre la deuxième valeur de retour de mapAccumL, comme mapAccumL sera de retour l'accumulateur ainsi que la mappé liste.

Pour ceux d'entre vous qui ne connaissent pas le symbole $ , c'est l'application "opérateur". Il n'a pas vraiment faire quelque chose, mais il a un a "faible, associatifs droit priorité de liaison", donc, cela signifie que vous pouvez laisser de côté les crochets (prendre note LISPers), c'est à dire (f x) est le même que $ f x

En cours d'exécution (ma 4 [2.0, 4.0, 7.0, 6.0, 3.0, 8.0, 12.0, 9.0, 4.0, 1.0]) les rendements [4.75, 5.0, 6.0, 7.25, 8.0, 8.25, 6.5] pour l'une ou l'autre solution.

Oh, et vous aurez besoin d'importer le module "Liste" pour compiler une ou l'autre solution.

La J langage de programmation facilite les programmes tels que le déplacement de la moyenne. En effet, il y a moins de caractères dans (+/% #)\ que dans leur libellé, " moyenne mobile.'

Pour les valeurs spécifiées dans cette question (y compris le nom des "valeurs"), voici un moyen simple pour code ce:

   values=: 2 4 7 6 3 8 12 9 4 1
4 (+/ % #)\ values
4.75 5 6 7.25 8 8.25 6.5

On peut le décrire en utilisant des étiquettes pour les composants.

   periods=: 4
average=: +/ % #
moving=: \
periods average moving values
4.75 5 6 7.25 8 8.25 6.5

Deux exemples utilisent exactement le même programme. La seule différence est l'utilisation de plusieurs noms dans la deuxième forme. De tels noms peuvent aider les lecteurs qui ne connaissent pas la J primaires.

Regardons un peu plus loin dans ce qui se passe dans le sous-programme, average. +/ dénote de sommation (Σ) et % désigne la division (comme le classique signe ÷). Calcul de comptage (count) des éléments est effectuée par # . L'ensemble du programme, alors, est la somme des valeurs divisée par le nombre de valeurs: +/% #

Le résultat de la moyenne mobile des valeurs de calcul écrit ici ne comprennent pas les zéros non significatifs attendus dans la question d'origine. Ces zéros sont sans doute pas partie de la destinée de calcul.

La technique utilisée ici est appelé tacite de la programmation. Il est à peu près le même que le style libre de la programmation fonctionnelle.

Voici un clojure version:

En raison de la paresse-seq, il est tout à fait général et ne souffle pas de pile

(defn partialsums [start lst]
(lazy-seq
(if-let [lst (seq lst)] 
(cons start (partialsums (+ start (first lst)) (rest lst)))
(list start))))
(defn sliding-window-moving-average [window lst]
(map #(/% window)
(let [start   (apply + (take window lst))
diffseq (map   - (drop window lst) lst)]
(partialsums start diffseq))))

;; Pour vous aider à voir ce qu'il fait:

(sliding-window-moving-average 5 '(1 2 3 4 5 6 7 8 9 10 11))
start = (+ 1 2 3 4 5) = 15
diffseq = - (6 7 8 9 10 11)
(1 2 3 4  5  6 7 8 9 10 11)
=   (5 5 5 5  5  5)
(partialsums 15 '(5 5 5 5 5 5) ) = (15 20 25 30 35 40 45)
(map #(/% 5) (20 25 30 35 40 45)) = (3 4 5 6 7 8 9)

;; Exemple

(take 20 (sliding-window-moving-average 5 (iterate inc 0)))

Cette solution est en Haskell, qui est plus familier pour moi:

slidingSums :: Num t => Int -> [t] -> [t]
slidingSums n list = case (splitAt (n - 1) list) of
(window, []) -> [] -- list contains less than n elements
(window, rest) -> slidingSums' list rest (sum window)
where
slidingSums' _ [] _ = []
slidingSums' (hl : tl) (hr : tr) sumLastNm1 = sumLastN : slidingSums' tl tr (sumLastN - hl)
where sumLastN = sumLastNm1 + hr
movingAverage :: Fractional t => Int -> [t] -> [t]
movingAverage n list = map (/ (fromIntegral n)) (slidingSums n list)
paddedMovingAverage :: Fractional t => Int -> [t] -> [t]
paddedMovingAverage n list = replicate (n - 1) 0 ++ movingAverage n list

Scala de traduction:

def slidingSums1(list: List[Double], rest: List[Double], n: Int, sumLastNm1: Double): List[Double] = rest match {
case Nil => Nil
case hr :: tr => {
val sumLastN = sumLastNm1 + hr
sumLastN :: slidingSums1(list.tail, tr, n, sumLastN - list.head)
}
}
def slidingSums(list: List[Double], n: Int): List[Double] = list.splitAt(n - 1) match {
case (_, Nil) => Nil
case (firstNm1, rest) => slidingSums1(list, rest, n, firstNm1.reduceLeft(_ + _))
}
def movingAverage(list: List[Double], n: Int): List[Double] = slidingSums(list, n).map(_ / n)
def paddedMovingAverage(list: List[Double], n: Int): List[Double] = List.make(n - 1, 0.0) ++ movingAverage(list, n)

Je sais comment j'allais le faire en python (note: les 3 premiers éléments avec les valeurs 0.0 ne sont pas retournés depuis n'est en réalité pas le moyen le plus approprié pour représenter une moyenne mobile). J'imagine des techniques similaires sera possible dans Scala. Voici plusieurs façons de le faire.

data = (2.0, 4.0, 7.0, 6.0, 3.0, 8.0, 12.0, 9.0, 4.0, 1.0)
terms = 4
expected = (4.75, 5.0, 6.0, 7.25, 8.0, 8.25, 6.5)
# Method 1 : Simple. Uses slices
assert expected == \
tuple((sum(data[i:i+terms])/terms for i in range(len(data)-terms+1)))
# Method 2 : Tracks slots each of terms elements
# Note: slot, and block mean the same thing.
# Block is the internal tracking deque, slot is the final output
from collections import deque
def slots(data, terms):
block = deque()
for datum in data :
block.append(datum)
if len(block) > terms : block.popleft()
if len(block) == terms :
yield block
assert expected == \
tuple(sum(slot)/terms for slot in slots(data, terms))
# Method 3 : Reads value one at a time, computes the sums and throws away read values
def moving_average((avgs, sums),val):
sums = tuple((sum + val) for sum in sums)
return (avgs + ((sums[0] / terms),), sums[1:] + (val,))
assert expected == reduce(
moving_average,
tuple(data[terms-1:]),
((),tuple(sum(data[i:terms-1]) for i in range(terms-1))))[0]
# Method 4 : Semantically same as method 3, intentionally obfuscates just to fit in a lambda
assert expected == \
reduce(
lambda (avgs, sums),val: tuple((avgs + ((nsum[0] / terms),), nsum[1:] + (val,)) \
for nsum in (tuple((sum + val) for sum in sums),))[0], \
tuple(data[terms-1:]),
((),tuple(sum(data[i:terms-1]) for i in range(terms-1))))[0]

Être en retard sur la partie, et de nouveau à la programmation fonctionnelle aussi, j'en suis venu à cette solution avec un intérieur fonction:

def slidingAvg (ixs: List [Double], len: Int) = {
val dxs = ixs.map (_ / len) 
val start = (0.0 /: dxs.take (len)) (_ + _)
val head = List.make (len - 1, 0.0)
def addAndSub (sofar: Double, from: Int, to: Int) : List [Double] =  
if (to >= dxs.length) Nil else {
val current = sofar - dxs (from) + dxs (to) 
current :: addAndSub (current, from + 1, to + 1) 
}
head ::: start :: addAndSub (start, 0, len)
}
val xs = List(2, 4, 7, 6, 3, 8, 12, 9, 4, 1)
slidingAvg (xs.map (1.0 * _), 4)

J'ai adopté l'idée de diviser l'ensemble de la liste par la période (len) à l'avance.
Puis-je générer la somme de commencer avec le len-premier-éléments.
Et je générer le premier, les éléments invalides (0.0, 0.0, ...) .

Puis-je de manière récursive, il suffit de soustraire la première et ajouter la dernière valeur.
À la fin, je listify l'ensemble de la chose.

À L'Aide De Haskell:

movingAverage :: Int -> [Double] -> [Double]
movingAverage n xs = catMaybes . (fmap avg . take n) . tails $ xs
where avg list = case (length list == n) -> Just . (/ (fromIntegral n)) . (foldl (+) 0) $ list
_                  -> Nothing

La clé est la queue de la fonction, qui correspond à une liste d'une liste de copies de la liste d'origine, avec la propriété que le n-ième élément de la suite est à côté de la première à n-1 éléments.

Donc

[1,2,3,4,5] -> [[1,2,3,4,5], [2,3,4,5], [3,4,5], [4,5], [5], []]

Nous appliquons fmap (avg . prendre la n) pour le résultat, ce qui signifie que nous prenons la n-longueur du préfixe de la sous-liste, et de calculer sa moyenne. Si la longueur de la liste nous sommes avg require n'est pas n, alors nous n'avons pas à calculer la moyenne (car il n'est pas défini). Dans ce cas, nous ne retournent Rien. Si c'est, nous le faisons, et l'envelopper dans de la "Juste". Enfin, nous courons "catMaybes" sur le résultat de fmap (avg . prendre la n), pour se débarrasser de la Peut-être de type.