Подтвердить что ты не робот

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

В эти выходные я решил попробовать свои силы в некоторых 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)

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

4b9b3361

ОТВЕТЫ

Ответ 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
 }

Ответ 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))

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

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

Ответ 3

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

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

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

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

Ответ 4

Здесь чисто функциональное решение в Clojure. Более сложные, чем те, которые уже были предоставлены, но ленивый и только корректируют среднее значение на каждом шаге, а не пересчитывают его с нуля. Это на самом деле медленнее простого решения, которое вычисляет новое среднее значение на каждом шаге, если период мал; однако в течение более длительных периодов он практически не замедляется, тогда как что-то, делающее (/ (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))))))

Ответ 5

Здесь частично point-free однострочное решение Haskell:

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

Сначала он применяет 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]]

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

Затем он отображает функцию ((/(из Integral p)). sum, возьмем 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). "хвосты" также не создают все эти отдельные списки, он просто ссылается на разные разделы исходного списка. Это еще не отличное решение, но это одна строка:)

Здесь немного более приятное, но более длинное решение, которое использует 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 - это то же самое, что и "карта", но с дополнительным параметром состояния/аккумулятора, который передается из предыдущего "сопоставления", к следующему, поскольку карта проходит через список. Мы используем аккумулятор как нашу скользящую среднюю, и поскольку наш список сформирован из элемента, который только что покинул скользящее окно и элемент, который только что ввел его (список, который мы только закрепили), наша функция скольжения принимает первое число "х", от среднего значения и добавляет второе число "y". Затем мы передаем новый 's' и возвращаем 's', деленный на 'p'. "snd" (второй) просто берет второй член пары (кортеж), который используется для получения второго возвращаемого значения mapAccumL, поскольку mapAccumL вернет как аккумулятор, так и сопоставленный список.

Для тех из вас, кто не знаком с $symbol, это "оператор приложения". Это на самом деле ничего не делает, но у него есть "низкий приоритет право-ассоциативного привязки", поэтому это означает, что вы можете оставить скобки (обратите внимание на 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] для любого решения.

О, и вам нужно будет импортировать модуль "Список" для компиляции любого из них.

Ответ 6

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

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

Ответ 7

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

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

   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. +/ обозначает суммирование (Σ) и % обозначает деление (как классический знак ÷). Вычисление суммы (количества) элементов производится с помощью #. Таким образом, общая программа представляет собой сумму значений, деленных на количество значений: +/ % #

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

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

Ответ 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 %)

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

Ответ 9

Здесь clojure версия:

Из-за ленивого 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)))

Ответ 10

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

(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 и, таким образом, позволяют, при необходимости, управлять состоянием.

Ответ 11

Это решение уже знакомо мне в Haskell:

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)

Ответ 12

Короткий 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]), а затем вычитая два числа со смещением, равным вашему периоду.

Ответ 13

Я знаю, как это сделать в 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]

Ответ 14

Похоже, вы ищете рекурсивное решение. В этом случае я бы предложил слегка изменить проблему и попытаться получить (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
  }
}

Ответ 15

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

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) заранее. Затем я генерирую сумму, чтобы начать с len-first-elements. И я генерирую первые недопустимые элементы (0.0, 0.0,...).

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

Ответ 16

В псевдокоде 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 из...)

Ответ 17

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

Итак,

[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, то мы не вычисляем среднее значение (поскольку оно undefined). В этом случае мы ничего не возвращаем. Если это так, мы делаем и завершаем его в "Just". Наконец, мы запускаем "catMaybes" в результате fmap (avg. Take n), чтобы избавиться от типа Maybe.

Ответ 18

Я был (удивлен и разочарован) тем, что мне показалось самым идиоматичным решением Clojure, @JamesCunningham lazy-seq решения.

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