Calculating the Moving Average of a List

user_420932 0
Viewed 42126

This weekend I decided to try my hand at some Scala and Clojure. I'm proficient with object oriented programming, and so Scala was easy to pick up as a language, but wanted to try out functional programming. This is where it got hard.

I just can't seem to get my head into a mode of writing functions. As an expert functional programmer, how do you approach a problem?

Given a list of values and a defined period of summation, how would you generate a new list of the simple moving average of the list?

For example: Given the list values (2.0, 4.0, 7.0, 6.0, 3.0, 8.0, 12.0, 9.0, 4.0, 1.0), and the period 4, the function should return: (0.0, 0.0, 0.0, 4.75, 5.0, 6.0, 7.25, 8.0, 8.25, 6.5)

After spending a day mulling it over, the best I could come up with in Scala was this:

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
}

I know this is horribly inefficient, I'd much rather do something like: 

where n < period: ma(n) = 0
where n = period: ma(n) = sum(value(1) to value(n)) / period
where n > period: man(n) = ma(n -1) - (value(n-period) / period) + (value(n) / period)

Now that would be easily done in a imperative style, but I can't for the life of me work out how to express that functionally.

clojure scala functional-programming
18 Answers

Here's a purely functional solution in Clojure. More complex than those already provided, but it is lazy and only adjusts the average at each step, instead of recalculating it from scratch. It's actually slower than a simple solution which calculates a new average at each step if the period is small; for larger periods, however, it experiences virtually no slowdown, whereas something doing (/ (take period ...) period) will perform worse for longer periods.

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

Here's a clojure version:

Because of the lazy-seq, it's perfectly general and won't blow stack

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

;; To help see what it's doing:

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

;; Example

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

A short Clojure version that has the advantage of being O(list length) regardless of your period:

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

This exploits the fact that you can calculate the sum of a range of numbers by creating a cumulative sum of the sequence (e.g. [1 2 3 4 5] -> [0 1 3 6 10 15]) and then subtracting the two numbers with an offset equal to your period.

user_2140100
Related