Calcul de la moyenne mobile d’une liste

Ce week-end, j’ai décidé d’essayer quelques Scala et Clojure. Maîsortingsant la programmation orientée object, Scala était facile à utiliser comme langage, mais je voulais essayer la functional programming. C’est là que ça a été difficile.

Je n’arrive pas à comprendre comment écrire des fonctions. En tant que programmeur fonctionnel expert, comment abordez-vous un problème?

Étant donné une liste de valeurs et une période de sommation définie, comment générer une nouvelle liste de la moyenne mobile simple de la liste?

Par exemple: Compte tenu des values liste (2.0, 4.0, 7.0, 6.0, 3.0, 8.0, 12.0, 9.0, 4.0, 1.0) et de la period 4, la fonction doit renvoyer: (0.0, 0.0, 0.0, 4.75, 5.0, 6.0, 7.25, 8.0, 8.25, 6.5)

Après avoir passé une journée à réfléchir, le mieux que je puisse trouver à Scala était la suivante:

 def simpleMovingAverage(values: List[Double], period: Int): List[Double] = { (for (i <- 1 to values.length) yield if (i < period) 0.00 else values.slice(i - period, i).reduceLeft(_ + _) / period).toList } 

Je sais que c’est terriblement inefficace, je préférerais plutôt faire quelque chose comme:

 where n  period: man(n) = ma(n -1) - (value(n-period) / period) + (value(n) / period) 

Maintenant, cela se ferait facilement dans un style impératif, mais je ne peux pas pour la vie travailler sur la manière de l’exprimer de manière fonctionnelle.

Problème intéressant Je peux penser à de nombreuses solutions, avec différents degrés d’efficacité. Avoir à append des choses à plusieurs resockets 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, alors ne vous inquiétez pas pour les produire. Si l’algorithme leur fournit naturellement, bien; sinon, nous le corrigerons plus tard.

En commençant par Scala 2.8, le résultat suivant serait le résultat pour n >= period en utilisant le sliding pour obtenir une fenêtre glissante 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 les meilleures performances possibles, car il ne tire pas parti des ajouts déjà calculés. Alors, 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 sum de deux paires. Essayons d’utiliser ce résultat pour calculer la moyenne mobile de 4 éléments. La formule ci-dessus a 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’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. Eh bien, il existe un algorithme bien connu pour calculer les choses qui suivent ce modèle. Il est surtout connu pour son utilisation sur le calcul de la puissance d’un nombre. Ça va comme ça:

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

Alors, voici la logique. La période 0 est invalide, la période 1 est égale à l’entrée, la période 2 est la fenêtre glissante de taille 2. Si elle est supérieure à cette valeur, elle peut être paire ou impaire.

Si c’est étrange, nous ajoutons chaque élément au movingSum des éléments suivants (odd - 1) . Par exemple, si 3, nous ajoutons chaque élément à la movingSum des 2 éléments suivants.

Si même, nous calculons le movingSum pour n / 2 , puis nous ajoutons chaque élément à l’un n / 2 pas après.

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 (point), pas O (values.size). Il peut être rendu plus efficace avec une fonction récursive de la queue. Et, bien sûr, la définition du “glissement” que j’ai fournie est horrible sur le plan des performances, mais la définition de Scala 2.8 sera bien meilleure. Notez que nous ne pouvons pas faire une méthode de sliding efficace sur une List , mais nous pouvons le faire sur une Iterable .

Cela dit, j’allais avec la toute première définition et je n’optimiserais que si une parsing du chemin critique identifiait cela comme une grosse affaire.

Pour conclure, réfléchissons à la manière dont j’ai abordé le problème. Nous avons un problème de moyenne mobile. Une moyenne mobile est la sum d’une “fenêtre” en mouvement sur une liste, divisée par la taille de cette fenêtre. Donc, d’abord, j’essaie d’obtenir une fenêtre glissante, de faire la sum de tous les éléments, puis de diviser par la taille.

Le problème suivant consistait à éviter la répétition d’ajouts déjà calculés. Dans ce cas, je suis allé à la plus petite addition possible, et j’ai essayé de trouver comment calculer des sums plus importantes en réutilisant de tels résultats.

Enfin, essayons de résoudre le problème comme vous l’avez compris en ajoutant et en soustrayant le 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. Tout d’abord, la liste des éléments à soustraire. Ensuite, la liste des éléments à append:

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

Nous pouvons append ces deux listes en utilisant zip . Cette méthode produira seulement autant d’éléments que la plus petite liste, ce qui évite que le problème de subtract soit plus important que nécessaire:

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

Nous finissons 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 à retourner. La fonction entière 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 } 

Je connais Clojure mieux que Scala, alors voilà. En écrivant ceci, l’autre entrée de Clojure est impérative; ce n’est pas vraiment ce que vous recherchez (et n’est pas idiomatique Clojure). Le premier algorithme qui me vient à l’esprit est de prendre à plusieurs resockets le nombre d’éléments requirejs dans la séquence, en supprimant le premier élément et en le récitant.

Ce qui suit fonctionne sur tout type de séquence (vecteur ou liste, paresseux ou non) et donne une séquence de moyennes paresseuse — ce qui pourrait être utile si vous travaillez sur une liste de taille indéfinie. Notez qu’il prend en charge le cas de base en retournant implicitement Nil s’il n’y a pas suffisamment d’éléments dans la liste à consumr.

 (defn moving-average [values period] (let [first (take period values)] (if (= (count first) period) (lazy-seq (cons (/ (reduce + first) period) (moving-average (rest values) period)))))) 

Exécuter ceci sur vos données de test produit

 user> (moving-average '(2.0, 4.0, 7.0, 6.0, 3.0, 8.0, 12.0, 9.0, 4.0, 1.0) 4) (4.75 5.0 6.0 7.25 8.0 8.25 6.5) 

Il ne donne pas “0” pour les premiers éléments de la séquence, bien que cela puisse facilement être traité (de manière quelque peu artificielle).

Le plus simple est de voir le modèle et de penser à une fonction disponible qui correspond à la facture. partition donne une vue paresseuse de parties d’une séquence, que nous pouvons ensuite mapper:

 (defn moving-average [values period] (map #(/ (reduce + %) period) (partition period 1 values)) 

Quelqu’un a demandé une version récursive de la queue; la récursion de la queue par rapport à la paresse est un compromis. Lorsque votre travail est en train de construire une liste, il est généralement assez simple de récurer votre fonction en arrière, ce qui ne fait pas exception – construisez simplement la liste comme argument d’une sous-fonction. Nous allons accumuler dans un vecteur au lieu d’une liste car sinon la liste sera construite à rebours et devra être inversée à la fin.

 (defn moving-average [values period] (loop [values values, period period, acc []] (let [first (take period values)] (if (= (count first) period) (recur (rest values) period (conj acc (/ (reduce + first) period))) acc)))) 

loop est un moyen de créer une fonction interne anonyme (un peu comme un nom nommé Scheme); recur doit être utilisé dans Clojure pour éliminer les appels de queue. conj est un cons , s’ajoutant de la manière naturelle à la collection – le début des listes et la fin des vecteurs.

Voici une autre solution Clojure (fonctionnelle):

 (defn avarage [coll]
   (/ (réduire + coll)
      (compter coll)))

 (defn ma [period coll]
   (carte avarage (période de partition 1 coll)))

Les zéros au début de la séquence doivent encore être ajoutés si cela est nécessaire.

Voici une solution purement fonctionnelle dans Clojure. Plus complexe que ceux déjà fournis, mais il est paresseux et ne règle que la moyenne à chaque étape, au lieu de la recalculer à partir de zéro . C’est en fait plus lent qu’une solution simple qui calcule une nouvelle moyenne à chaque étape si la période est petite; pour les périodes plus longues, cependant, il ne subit quasiment aucun ralentissement, alors que quelque chose qui se passe (/ (take period ...) period) aura un rendement plus long pendant de longues périodes.

 (defn moving-average "Calculates the moving average of values with the given period. Returns a lazy seq, works with infinite input sequences. Does not include initial zeros in the output." [period values] (let [gen (fn gen [last-sum values-old values-new] (if (empty? values-new) nil (let [num-out (first values-old) num-in (first values-new) new-sum (+ last-sum (- num-out) num-in)] (lazy-seq (cons new-sum (gen new-sum (next values-old) (next values-new)))))))] (if (< (count (take period values)) period) nil (map #(/ % period) (gen (apply + (take (dec period) values)) (cons 0 values) (drop (dec period) values)))))) 

Voici une solution Haskell en une ligne partiellement gratuite :

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

D’abord, il applique les queues à la liste pour obtenir les listes “queues”, 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 laisse tomber les premières entrées “p” (en prenant p comme 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]] 

Si vous n’êtes pas familier avec le symbole (.) Point / nipple , il s’agit de l’opérateur de la «composition fonctionnelle», ce qui signifie qu’il passe la sortie d’une fonction à la saisie d’une autre. (g. f) signifie “exécuter f sur une valeur puis passer la sortie à g”, donc ((f. g) x) est le même que (g (fx)). En général, son utilisation conduit à un style de programmation plus clair.

Il mappe ensuite la fonction ((/ (fromIntegral p)). Sum. Prend p) dans la liste. Donc, pour chaque liste de la liste, il prend les premiers éléments «p», les additionne, puis les divise par «p». Ensuite, nous retournons simplement la liste 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 que ça; “reverse” n’inverse pas physiquement l’ordre d’une liste jusqu’à ce que la liste soit évaluée, elle la dépose simplement dans la stack (bon vieux Haskell). “Tails” ne crée pas non plus toutes ces listes séparées, il ne fait que référencer différentes sections de la liste originale. Ce n’est toujours pas une bonne solution, mais c’est une longue ligne 🙂

Voici une solution légèrement plus agréable mais plus longue qui utilise mapAccum pour effectuer une soustraction et une addition glissantes:

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

Nous avons d’abord divisé 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 la liste d’origine (cela ne fait qu’associer des éléments dans l’ordre des deux listes). La liste originale est évidemment plus longue, 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 identique à “map”, mais avec un paramètre supplémentaire state / accumulator, qui est transmis du précédent “mapping” au suivant lorsque la carte parcourt la liste. Nous utilisons l’accumulateur comme moyenne mobile, et comme notre liste est formée de l’élément qui vient de sortir de la fenêtre glissante et de l’élément qui vient d’y entrer (la liste que nous venons de compresser), notre fonction glisse loin de la moyenne et ajoute le deuxième chiffre «y». Nous passons ensuite les nouveaux ‘s’ et retournons ‘s’ divisé par ‘p’. “snd” (second) prend juste le deuxième membre d’une paire (tuple), qui est utilisé pour prendre la deuxième valeur de retour de mapAccumL, car mapAccumL renverra l’accumulateur ainsi que la liste mappée.

Pour ceux qui ne sont pas familiers avec le symbole $ , il s’agit de “l’opérateur d’application”. Il ne fait rien, mais il a une priorité de liaison faible, associative à droite, ce qui signifie que vous pouvez laisser de côté les crochets (prendre note LISPers), c.-à-d.

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 chaque solution.

Oh, vous devrez importer le module “List” pour comstackr l’une ou l’autre solution.

Voici deux autres façons de faire la moyenne mobile dans Scala 2.8.0 (une ssortingcte et une paresseuse). Les deux supposent qu’il y a au moins p Double dans vs.

 // ssortingct moving average def sma(vs: List[Double], p: Int): List[Double] = ((vs.take(p).sum / p :: List.fill(p - 1)(0.0), vs) /: vs.drop(p)) {(a, v) => ((a._1.head - a._2.head / p + v / p) :: a._1, a._2.tail) }._1.reverse // lazy moving average def lma(vs: Stream[Double], p: Int): Stream[Double] = { def _lma(a: => Double, vs1: Stream[Double], vs2: Stream[Double]): Stream[Double] = { val _a = a // caches value of a _a #:: _lma(_a - vs2.head / p + vs1.head / p, vs1.tail, vs2.tail) } Stream.fill(p - 1)(0.0) #::: _lma(vs.take(p).sum / p, vs.drop(p), vs) } scala> sma(List(2.0, 4.0, 7.0, 6.0, 3.0, 8.0, 12.0, 9.0, 4.0, 1.0), 4) res29: List[Double] = List(0.0, 0.0, 0.0, 4.75, 5.0, 6.0, 7.25, 8.0, 8.25, 6.5) scala> lma(Stream(2.0, 4.0, 7.0, 6.0, 3.0, 8.0, 12.0, 9.0, 4.0, 1.0), 4).take(10).force res30: scala.collection.immutable.Stream[Double] = Stream(0.0, 0.0, 0.0, 4.75, 5.0, 6.0, 7.25, 8.0, 8.25, 6.5) 

Le langage de programmation J facilite les programmes tels que la moyenne mobile. En effet, il y a moins de caractères dans (+/ % #)\ que dans leur étiquette, «moyenne mobile».

Pour les valeurs spécifiées dans cette question (y compris le nom ‘values’), voici un moyen simple de coder ceci:

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

Nous pouvons décrire cela 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 

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

Examinons un peu plus ce qui se passe dans le sous-programme, la average . +/ dénote la sommation (Σ) et % désigne la division (comme le signe classique ÷). Le calcul d’un décompte (nombre) d’éléments est effectué par # . Le programme global est donc la sum des valeurs divisées par le nombre de valeurs: +/ % #

Le résultat du calcul de la moyenne mobile écrit ici n’inclut pas les zéros en tête attendus dans la question d’origine. Ces zéros ne font sans doute pas partie du calcul prévu.

La technique utilisée ici s’appelle la programmation tacite. C’est à peu près la même chose que le style de functional programming sans points.

Clojure prétend être un langage plus fonctionnel. Ceci est complètement récursif, btw, et inclut des zéros en tête.

 (defn moving-average [period values] (loop [[x & xs] values window [] ys []] (if (and (nil? x) (nil? xs)) ;; base case ys ;; inductive case (if (< (count window) (dec period)) (recur xs (conj window x) (conj ys 0.0)) (recur xs (conj (vec (rest window)) x) (conj ys (/ (reduce + x window) period))))))) (deftest test-moving-average (is (= [0.0 0.0 0.0 4.75 5.0 6.0 7.25 8.0 8.25 6.5] (moving-average 4 [2.0 4.0 7.0 6.0 3.0 8.0 12.0 9.0 4.0 1.0])))) 

En général, je mets le paramètre collection ou list en dernier pour que la fonction soit plus facile à curry. Mais à Clojure ...

 (partial moving-average 4) 

... est tellement encombrant que je finis généralement par le faire ...

 #(moving-average 4 %) 

... dans quel cas l'ordre des parameters n'a pas d'importance.

Voici une version clojure:

A cause de la paresse-seq, c’est parfaitement général et ne soufflera pas

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

Cet exemple utilise l’état, car pour moi, c’est une solution pragmatique dans ce cas, et une fermeture pour créer la fonction de calcul de la moyenne des fenêtres:

 (defn make-averager [#^Integer period] (let [buff (atom (vec (repeat period nil))) pos (atom 0)] (fn [nextval] (reset! buff (assoc @buff @pos nextval)) (reset! pos (mod (+ 1 @pos) period)) (if (some nil? @buff) 0 (/ (reduce + @buff) (count @buff)))))) (map (make-averager 4) [2.0, 4.0, 7.0, 6.0, 3.0, 8.0, 12.0, 9.0, 4.0, 1.0]) ;; yields => (0 0 0 4.75 5.0 6.0 7.25 8.0 8.25 6.5) 

Il est toujours fonctionnel dans le sens où il utilise des fonctions de première classe, même s’il n’est pas exempt d’effets secondaires. Les deux langues que vous avez mentionnées s’exécutent toutes deux au-dessus de la JVM et permettent toutes les deux de gérer l’état si nécessaire.

Cette solution est dans Haskell, ce qui m’est plus familier:

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

Une version courte de Clojure qui a l’avantage d’être O (longueur de liste) quelle que soit votre période:

 (defn moving-average [list period] (let [accums (let [acc (atom 0)] (map #(do (reset! acc (+ @acc %1 ))) (cons 0 list))) zeros (repeat (dec period) 0)] (concat zeros (map #(/ (- %1 %2) period) (drop period accums) accums)))) 

Cela exploite le fait que vous pouvez calculer la sum d’une plage de nombres en créant une sum cumulative de la séquence (par exemple [1 2 3 4 5] -> [0 1 3 6 10 15]) puis en soustrayant les deux nombres avec un décalage égal à votre période.

Je sais comment je le ferais en python (note: les 3 premiers éléments avec les valeurs 0.0 ne sont pas retournés car ce n’est en fait pas la manière appropriée de représenter une moyenne mobile). J’imagine que des techniques similaires seront réalisables à 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] 

Il semble que vous cherchiez une solution récursive. Dans ce cas, je suggérerais de modifier légèrement le problème et d’essayer d’obtenir (4.75, 5.0, 6.0, 7.25, 8.0, 8.25, 6.5, 0.0, 0.0, 0.0) une solution.

Dans ce cas, vous pouvez écrire la solution récursive élégante ci-dessous dans Scala:

 def mavg(values: List[Double], period: Int): List[Double] = { if (values.size < period) List.fill(values.size)(0.0) else if (values.size == period) (values.sum / values.size) :: List.fill(period - 1)(0.0) else { val rest: List[Double] = mavg(values.tail, period) (rest.head + ((values.head - values(period))/period)):: rest } } 

Étant en retard sur la fête et nouveau dans la functional programming, je suis arrivé à cette solution avec une fonction interne:

 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, diviser la liste entière par la période (len) à l’avance. Ensuite, je génère la sum pour commencer pour les len-first-elements. Et je génère les premiers éléments non valides (0.0, 0.0, …).

Ensuite, je soustrais récursivement le premier et ajoute la dernière valeur. En fin de compte, je écoute tout.

Dans le pseudocode de Haskell:

 group4 (a:b:c:d:xs) = [a,b,c,d] : group4 (b:c:d:xs) group4 _ = [] avg4 xs = sum xs / 4 running4avg nums = (map avg4 (group4 nums)) 

ou pointfree

 runnig4avg = map avg4 . group4 

(Maintenant, il faut vraiment faire abstraction du 4 out ….)

En utilisant 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 fonction des queues, qui mappe une liste à une liste de copies de la liste d’origine, avec la propriété que le n-ième élément du résultat manque les premiers n-1 éléments.

Alors

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

Nous appliquons fmap (avg. Take n) au résultat, ce qui signifie que nous prenons le préfixe n-length de la sous-liste et calculons sa valeur moyenne. Si la longueur de la liste que nous envisageons n’est pas n, alors nous ne calculons pas la moyenne (car elle n’est pas définie). Dans ce cas, nous retournons Rien. Si c’est le cas, on le fait et on l’enveloppe dans “Just”. Enfin, on lance “catMaybes” sur le résultat de fmap (avg. Take n), pour se débarrasser du type Maybe.

J’ai été (surpris et) déçu par la performance de ce qui m’a semblé être les solutions Clojure les plus idiomatiques, les solutions lazy-seq @JamesCunningham.

 (def integers (iterate inc 0)) (def coll (take 10000 integers)) (def n 1000) (time (doall (moving-average-james-1 coll n))) # "Elapsed time: 3022.862 msecs" (time (doall (moving-average-james-2 coll n))) # "Elapsed time: 3433.988 msecs" 

Donc, voici une combinaison de la solution de James avec l’ idée de @ DanielC.Sobral d’adapter une exponentiation rapide à des sums en mouvement:

 (defn moving-average [coll n] (letfn [(moving-sum [coll n] (lazy-seq (cond (= n 1) coll (= n 2) (map + coll (rest coll)) (odd? n) (map + coll (moving-sum (rest coll) (dec n))) :else (let [half (quot n 2) hcol (moving-sum coll half)] (map + hcol (drop half hcol))))))] (cond (< n 1) nil (= n 1) coll :else (map #(/ % n) (moving-sum coll n))))) (time (doall (moving-average coll n))) # "Elapsed time: 42.034 msecs" 

Edit: celle-ci basée sur la solution de @mikera - est encore plus rapide.

 (defn moving-average [coll n] (cond (< n 1) nil (= n 1) coll :else (let [sums (reductions + 0 coll)] (map #(/ (- %1 %2) n) (drop n sums) sums)))) (time (doall (moving-average coll n))) # "Elapsed time: 9.184 msecs"