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

47

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

Начиная с 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 из следующих двух элементов.

Если даже, мы вычисляем 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 будет намного лучше определено его определение. Обратите внимание, что мы не можем сделать эффективный метод 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 
}

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

ответ

Смежные вопросы