Вычисление скользящего среднего из списка

Question

В эти выходные я решил попробовать свои силы в Scala и Clojure. Я хорошо разбираюсь в объектно-ориентированном программировании, поэтому Scala было легко подобрать в качестве языка, но он хотел попробовать функциональное программирование. Вот где это стало трудно.

Я просто не могу погрузиться в режим написания функций. Как опытный функциональный программист, как вы подходите к проблеме?

Учитывая список значений и определенный период суммирования, как бы вы сгенерировали новый список простого скользящего среднего из списка?

Например: учитывая список values (2.0, 4.0, 7.0, 6.0, 3.0, 8.0, 12.0, 9.0, 4.0, 1.0) и period 4, функция должна вернуть: (0.0, 0.0 0,0, 4,75, 5,0, 6,0, 7,25, 8,0, 8,25, 6,5)

Потратив день на обдумывание, лучшее, что я смог придумать в Scala, это:

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
}

Я знаю, что это ужасно неэффективно, я бы предпочел сделать что-то вроде:

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)

Теперь это легко сделать в императивном стиле, но я не могу понять, как выразить это функционально.

Answer 1

В этом примере используется состояние, поскольку для меня это прагматическое решение в данном случае и замыкание для создания функции усреднения окон:

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

Он все еще функционален в смысле использования функций первого класса, хотя и не свободен от побочных эффектов. Оба упомянутых вами языка работают поверх JVM и, таким образом, оба позволяют управлять состоянием, когда это необходимо.

Answer 2

Короткая версия Clojure, преимущество которой в том, что O (длина списка) независимо от вашего периода:

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

Это использует тот факт, что вы можете вычислить сумму диапазона чисел, создав совокупную сумму последовательности (например, [1 2 3 4 5] -> [0 1 3 6 10 15]), а затем вычтя два числа со смещением, равным вашему периоду.

Answer 3

Похоже, вы ищете рекурсивное решение. В этом случае я бы предложил немного изменить проблему и попытаться получить (4.75, 5.0, 6.0, 7.25, 8.0, 8.25, 6.5, 0.0, 0.0, 0.0) в качестве решения.

В этом случае вы можете написать следующее элегантное рекурсивное решение в 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
  }
}

Answer 4

Я знаю, как бы это сделать в python (обратите внимание: первые 3 элемента со значениями 0.0 не возвращаются, поскольку это на самом деле неподходящий способ представления скользящей средней). Я предполагаю, что подобные методы будут возможны в Scala. Вот несколько способов сделать это.

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]

Answer 5

Использование 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

Ключом является функция хвостов, которая отображает список в список копий исходного списка со свойством, что в n-м элементе результата отсутствуют первые n-1 элементов.

So

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

Мы применяем fmap (avg. Take n) к результату, что означает, что мы берем префикс n-длины из подсписка и вычисляем его avg. Если длина списка, который мы отправляем, не равна n, то мы не вычисляем среднее значение (поскольку оно не определено). В этом случае мы ничего не возвращаем. Если это так, мы делаем, и завернуть его в «Просто». Наконец, мы запускаем «catMaybes» для результата fmap (avg. Take n), чтобы избавиться от типа Maybe.

Answer 6

В псевдокоде на 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))

или pointfree

runnig4avg = map avg4 . group4

(Теперь действительно нужно абстрагироваться от 4 ...)

Answer 7

Я был (удивлен и) разочарован производительностью того, что мне показалось наиболее идиоматичным решением Clojure, 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"

Итак, вот комбинация решения Джеймса и идеи @ DanielC.Sobral адаптации быстрого возведения в степень к движущимся суммам:

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

Редактировать: этот, основанный на решении @mikera - еще быстрее.

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

Answer 8

Опоздав на вечеринку, а также плохо знаком с функциональным программированием, я пришел к этому решению с внутренней функцией:

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)

Я принял идею разделить весь список на период (лен) заранее. Затем я генерирую сумму для начала для len-first-elements. И я генерирую первые недопустимые элементы (0.0, 0.0, ...).

Затем я рекурсивно вычитаю первое и добавляю последнее значение. В конце концов, я слушаю все это.