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

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

Интересная проблема. Я могу придумать много решений с различной степенью эффективности. Необходимость многократного добавления материала на самом деле не является проблемой производительности, но давайте предположим, что это так. Кроме того, нули в начале могут быть добавлены позже, поэтому давайте не будем беспокоиться о их создании. Если алгоритм обеспечивает их естественно, хорошо; если нет, мы исправим это позже.

Начиная с Scala 2.8, следующий код даст результат для n >= period, используя sliding для получения скользящего окна списка:

def simpleMovingAverage(values: List[Double], period: Int): List[Double] =
  List.fill(period - 1)(0.0) ::: (values sliding period map (_.sum) map (_ / period))

Тем не менее, хотя это довольно элегантно, оно не обладает наилучшей возможной производительностью, поскольку не использует преимущества уже вычисленных дополнений. Итак, говоря о них, как мы можем их получить?

Допустим, мы пишем это:

values sliding 2 map sum

У нас есть список суммы каждых двух пар. Давайте попробуем использовать этот результат для вычисления скользящего среднего из 4 элементов. Приведенная выше формула сделала следующие вычисления:

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

Итак, если мы возьмем каждый элемент и добавим его ко второму следующему элементу, мы получим скользящее среднее для 4 элементов:

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

Мы можем сделать это так:

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

Затем мы можем вычислить скользящее среднее для 8 элементов и так далее. Ну, есть хорошо известный алгоритм для вычисления вещей, которые следуют такой схеме. Он наиболее известен своим использованием для вычисления мощности числа. Это выглядит так:

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

Итак, давайте применим это здесь:

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

Итак, вот логика. Период 0 недействителен, период 1 равен вводу, период 2 - скользящее окно размера 2. Если оно больше, оно может быть четным или нечетным.

Если нечетно, мы добавляем каждый элемент к movingSum следующих (odd - 1) элементов. Например, если 3, мы добавляем каждый элемент к movingSum из следующих 2 элементов.

Если даже, мы вычисляем movingSum для n / 2, затем добавляем каждый элемент к одному шагу n / 2.

С этим определением мы можем вернуться к проблеме и сделать это:

def simpleMovingAverage(values: List[Double], period: Int): List[Double] =
  List.fill(period - 1)(0.0) ::: (movingSum(values, period) map (_ / period))

Существует небольшая неэффективность в отношении использования :::, но это O (точка), а не O (values.size). Это может быть сделано более эффективным с помощью хвостовой рекурсивной функции. И, конечно же, определение «скольжения», которое я дал, ужасно влияет на производительность, но в Scala 2.8 его будет гораздо лучше. Обратите внимание, что мы не можем создать эффективный метод sliding для List, но мы можем сделать это для Iterable.

Сказав все это, я бы пошел с самым первым определением и оптимизировал бы, только если анализ критического пути определил это как большое дело.

В заключение давайте рассмотрим, как я решил проблему. У нас есть проблема скользящего среднего. Скользящее среднее - это сумма движущихся «окон» в списке, деленная на размер этого окна. Итак, сначала я пытаюсь получить скользящее окно, суммировать все на нем, а затем разделить на размер.

Следующая проблема состояла в том, чтобы избежать повторения уже вычисленных дополнений. В этом случае я пошел на наименьшее возможное сложение и попытался выяснить, как вычислить большие суммы, используя такие результаты.

Наконец, давайте попробуем решить проблему так, как вы ее себе представляли, сложив и вычтя из предыдущего результата. Получить первое среднее легко:

 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

Мы можем добавить эти два списка, используя zip. Этот метод будет производить только столько элементов, сколько имеется в меньшем списке, что позволяет избежать проблемы, когда subtract больше, чем необходимо:

   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

который является ответом, который будет возвращен. Вся функция выглядит так:

 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
 }

Answer 2

Я знаю Clojure лучше, чем Scala, так что здесь. Когда я пишу это, другая запись Clojure здесь обязательна; это не совсем то, что вы ищете (и не идиоматический Clojure). Первый алгоритм, который мне приходит в голову, - это многократное извлечение запрошенного количества элементов из последовательности, удаление первого элемента и повторение.

Следующее работает для любого типа последовательности (вектор или список, ленивый или нет) и дает ленивую последовательность средних значений - что может быть полезно, если вы работаете со списком неопределенного размера. Обратите внимание, что он заботится о базовом случае, неявно возвращая nil, если в списке недостаточно элементов для потребления.

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

Выполнение этого на ваших тестовых данных дает

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)

Это не дает «0» для первых нескольких элементов в последовательности, хотя это может быть легко обработано (несколько искусственно).

Самая простая вещь - это увидеть шаблон и уметь вспомнить доступную функцию, которая отвечает всем требованиям. partition дает ленивое представление частей последовательности, которые мы затем можем отобразить:

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

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

(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 - это способ создать анонимную внутреннюю функцию (вроде как, например, схема с именем let); recur должен использоваться в Clojure для устранения концевых вызовов. conj является обобщенным cons, добавляя естественным для коллекции образом - начало списков и конец векторов.

Answer 3

Вот еще одно (функциональное) решение Clojure:

(defn avarage [coll]
  (/ (reduce + coll)
     (count coll)))

(defn ma [period coll]
  (map avarage (partition period 1 coll)))

Нули в начале последовательности должны быть добавлены, если это является требованием.

Answer 4

Вот чисто функциональное решение в Clojure. Более сложный, чем те, которые уже предоставлены, но он lazy и только корректирует среднее значение на каждом шаге, а не пересчитывает его с нуля . Это на самом деле медленнее, чем простое решение, которое вычисляет новое среднее значение на каждом шаге, если период мал; однако в более длительные периоды он практически не замедляется, в то время как что-то, что делает (/ (take period ...) period), будет работать хуже в течение более длительных периодов.

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

Answer 5

Вот частично бессмысленное однострочное решение Haskell:

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

Сначала он применяет хвосты к списку, чтобы получить списки "хвостов", поэтому:

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],[]]

Обращает его и удаляет первые записи 'p' (принимая p за 2 здесь):

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

Если вы не знакомы с символом (.) Точка / ниппель , это оператор для «функциональной композиции», то есть он передает выходные данные одной функции как входные данные другой, «составляя» их в одну функцию. (g. f) означает «запустить f на значении, а затем передать результат в g», поэтому ((f. g) x) совпадает с (g (f x)). Обычно его использование приводит к более ясному стилю программирования.

Затем он отображает функцию ((/ (fromIntegral p)). Sum. Take p) в список. Таким образом, для каждого списка в списке он берет первые элементы 'p', суммирует их, а затем делит их на 'p'. Затем мы просто переворачиваем список обратно с помощью «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]

Все это выглядит гораздо более неэффективно, чем есть; «reverse» физически не меняет порядок списка до тех пор, пока список не будет оценен, он просто размещает его в стеке (добрый ленивый Haskell). "tails" также не создает все эти отдельные списки, он просто ссылается на различные разделы исходного списка. Это все еще не очень хорошее решение, но оно длиной в одну строку:)

Вот немного более приятное, но более длинное решение, использующее mapAccum для скользящего вычитания и сложения:

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

Сначала мы разбиваем список на две части в «p», поэтому:

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

Суммируйте первый бит:

Prelude List> sum [2.0, 4.0]
6.0

Сжать второй бит с исходным списком (это просто объединяет элементы в порядке из двух списков). Оригинальный список явно длиннее, но мы теряем этот дополнительный бит:

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

Теперь мы определим функцию для нашего mapAccum (ulator). mapAccumL - это то же самое, что и «map», но с дополнительным параметром состояния / накопителя, который передается от предыдущего «отображения» к следующему при прохождении карты по списку. Мы используем аккумулятор в качестве нашей скользящей средней, и поскольку наш список состоит из элемента, который только что покинул скользящее окно, и элемента, который только что вошел в него (список, который мы только что заархивировали), наша скользящая функция принимает первое число «x» от среднего и добавляет второе число «у». Затем мы передаем новые 's' и возвращаем 's', разделенные на 'p'. «snd» (second) просто берет второй член пары (кортеж), который используется для получения второго возвращаемого значения mapAccumL, поскольку mapAccumL будет возвращать как аккумулятор, так и отображенный список.

Для тех из вас, кто не знаком с символом $ , это «оператор приложения». Он на самом деле ничего не делает, но у него есть «низкий приоритет связывания справа», так что это означает, что вы можете опустить скобки (обратите внимание на LISPers), то есть (fx) совпадает с f $ x

Запуск (ma 4 [2.0, 4.0, 7.0, 6.0, 3.0, 8.0, 12.0, 9.0, 4.0, 1.0]) дает [4.75, 5.0, 6.0, 7.25, 8.0, 8.25, 6.5] для любого решения.

Да, и вам нужно будет импортировать модуль "Список", чтобы скомпилировать любое решение.

Answer 6

Вот еще 2 способа сделать скользящее среднее в Scala 2.8.0 (один строгий и один ленивый). Оба предполагают, что есть как минимум p Удвоения в против .

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

Answer 7

Язык программирования J облегчает такие программы, как скользящее среднее. В самом деле, в (+/ % #)\ меньше символов, чем в их ярлыке «скользящее среднее».

Для значений, указанных в этом вопросе (включая имя 'values'), есть простой способ кодирования этого:

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

Мы можем описать это, используя метки для компонентов.

   periods=: 4
   average=: +/ % #
   moving=: \

   periods average moving values
4.75 5 6 7.25 8 8.25 6.5

В обоих примерах используется одна и та же программа. Единственное отличие - использование большего количества имен во второй форме. Такие имена могут помочь читателям, которые не знают праймериз J. *

Давайте посмотрим немного дальше, что происходит в подпрограмме, average. +/ обозначает суммирование (Σ), а % обозначает деление (как классический знак ÷). Подсчет количества предметов производится с помощью #. Общая программа, таким образом, представляет собой сумму значений, деленную на количество значений: +/ % #

Результат вычисления скользящего среднего, записанный здесь, не включает начальные нули, ожидаемые в исходном вопросе. Эти нули, возможно, не являются частью предполагаемого расчета.

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

Answer 8

Здесь Clojure притворяется более функциональным языком. Это полностью хвостовая рекурсия, кстати, и включает ведущие нули.

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

Обычно я добавляю параметр коллекции или списка последним, чтобы сделать функцию проще для карри. Но в Clojure ...

(partial moving-average 4)

... это так громоздко, я обычно заканчиваю этим ...

#(moving-average 4 %)

... в этом случае не имеет значения, в каком порядке идут параметры.

Answer 9

Вот закрытая версия:

Из-за lazy-seq, он совершенно универсален и не взорвёт стек

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

;; Чтобы понять, что он делает:

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

;; Пример

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

Answer 10

Это решение на Хаскелле, которое мне более знакомо:

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:

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)