Вычисление скользящего среднего значения списка
Просто заставьте ботов конкурировать даже в земле. Зашифруйте метку времени и засуньте ее в скрытое поле формы. Когда Вы добираетесь, представление дешифруют его и видят, сколько передало время. Если это превосходит порог человеческой способности к вводу, отклоняют его. Теперь боты и люди могут только попытаться купить мешок дерьма на той же скорости.
13 ответов
Интересная задача. Я могу придумать множество решений с разной степенью эффективности. Необходимость многократно добавлять элементы на самом деле не является проблемой производительности, но давайте предположим, что это так. Кроме того, нули в начале могут быть добавлены позже, поэтому давайте не будем беспокоиться о их создании. Если алгоритм обеспечивает их естественным образом - хорошо; в противном случае мы исправим его позже.
Начиная с Scala 2.8, следующее будет давать результат для n> = период , используя скольжение для получения скользящего окна списка. :
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
У нас есть список суммы каждой пары. Позволять' s попытаться использовать этот результат для вычисления скользящего среднего 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 из следующих (нечетных - 1) элементов. Например, если 3, мы добавляем каждый элемент к movingSum следующих двух элементов.
Если даже, мы вычисляем 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 (значения.размер). Его можно сделать более эффективным с помощью хвостовой рекурсивной функции. И, конечно же, определение «скольжения», которое я дал, ужасно с точки зрения производительности, но в Scala 2.8 его будет гораздо лучше. Обратите внимание, что мы не можем создать эффективный метод скольжения в 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 . Этот метод будет генерировать ровно столько элементов, сколько имеет меньший список, что позволяет избежать проблемы того, что вычитание будет больше, чем необходимо:
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
}
В этом примере используется состояние, так как для меня это прагматическое решение в данном случае и закрытие создайте оконную функцию усреднения:
(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 и, таким образом, позволяют при необходимости управлять состоянием.
Это решение находится на 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)
Здесь 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 %)
... в этом случае не имеет значения, в каком порядке идут параметры.
Вот еще одно (функциональное) решение Clojure:
(defn avarage [coll]
(/ (reduce + coll)
(count coll)))
(defn ma [period coll]
(map avarage (partition period 1 coll)))
нули в начале последовательности все равно должны быть добавлены, если это необходимо.
Я знаю 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» для первого несколько элементов в последовательности, хотя с этим можно легко справиться (несколько искусственно).
Самый простой способ - это увидеть образец и уметь вспомнить доступную функцию, которая отвечает всем требованиям. Раздел дает ленивое представление частей последовательности, которые мы затем можем отобразить:
(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 для устранения хвостовых вызовов. con - это обобщенное cons , добавляющееся естественным для коллекции способом - начало списков и конец векторов.
Here are 2 more ways to do moving average in Scala 2.8.0(one strict and one lazy). Both assume there are at least p Doubles in 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)
Вот частично безточечное однострочное решение 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 (fx)). Обычно его использование приводит к более ясному стилю программирования.
Затем он отображает функцию ((/ (fromIntegral p)). Sum. Take p) в список. Итак, для каждого списка в списке требуется первая буква "p" элементов, суммирует их, а затем делит на 'p'. Затем мы просто переворачиваем список обратно с помощью «обратного».
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 - это то же самое, что и «карта», но с дополнительным параметром текущего состояния / аккумулятора, который передается от предыдущего «сопоставления» к следующему, когда карта проходит по списку. Мы используем аккумулятор в качестве скользящего среднего, и поскольку наш список состоит из элемента, который только что покинул скользящее окно, и элемента, который только что вошел в него (список, который мы только что заархивировали), наша скользящая функция принимает первое число 'x' от среднего и добавляет второе число «y». Затем мы передаем новые «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] для любого решения.
Да, и вам нужно будет импортировать модуль «Список» для компиляции любого решения.
Вот чисто функциональное решение на 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))))))
Вот версия clojure:
Из-за lazy-seq, это совершенно обычный метод, который не повредит 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))))
;; Чтобы увидеть, что он делает:
(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)))
Опаздывая на вечеринку и будучи новичком в функциональном программировании, я пришел к этому решению с внутренней функцией:
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, ...).
Затем я рекурсивно вычитаю первое и добавляю последнее значение. В конце концов, я все это прослушиваю.
Я знаю как бы я сделал это в 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]
Язык программирования 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. +/ обозначает суммирование (Σ), а % обозначает деление (как классический знак ÷). Вычисление количества (количества) элементов выполняется с помощью # . Таким образом, общая программа представляет собой сумму значений, деленную на сумму значений: +/ % #
Результат вычисления скользящего среднего, написанный здесь, не включает начальные нули, ожидаемые в исходном вопросе. Эти нули, возможно, не являются частью предполагаемого расчета.
Используемый здесь метод называется неявным программированием. Это почти то же самое, что и бесточечный стиль функционального программирования.