计算列表的移动平均线 [英] Calculating the Moving Average of a List

问题描述

这个周末我决定尝试一些 Scala 和 Clojure.我精通面向对象编程，因此 Scala 很容易作为一门语言学习，但想尝试函数式编程.这就是它变得困难的地方.

This weekend I decided to try my hand at some Scala and Clojure. I'm proficient with object oriented programming, and so Scala was easy to pick up as a language, but wanted to try out functional programming. This is where it got hard.

我似乎无法进入编写函数的模式.作为专业的函数式程序员，您如何解决问题?

I just can't seem to get my head into a mode of writing functions. As an expert functional programmer, how do you approach a problem?

给定一个值列表和一个定义的求和周期，您将如何生成列表的简单移动平均线的新列表?

Given a list of values and a defined period of summation, how would you generate a new list of the simple moving average of the list?

例如:给定列表 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)

For example: Given the list values (2.0, 4.0, 7.0, 6.0, 3.0, 8.0, 12.0, 9.0, 4.0, 1.0), and the period 4, the function should return: (0.0, 0.0, 0.0, 4.75, 5.0, 6.0, 7.25, 8.0, 8.25, 6.5)

在花了一天的时间仔细考虑之后，我在 Scala 中能想到的最好的方法是:

After spending a day mulling it over, the best I could come up with in Scala was this:

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
}

我知道这是非常低效的，我宁愿做这样的事情:

I know this is horribly inefficient, I'd much rather do something like:

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)

现在用命令式风格很容易做到，但我一生都无法弄清楚如何用函数式表达它.

Now that would be easily done in a imperative style, but I can't for the life of me work out how to express that functionally.

推荐答案

有趣的问题.我能想到很多解决方案，效率各不相同.不得不重复添加东西并不是真正的性能问题，但让我们假设它是.此外，开头的零可以在以后添加，所以我们不用担心产生它们.如果算法自然地提供它们，那很好；如果没有，我们稍后更正.

Interesting problem. I can think of many solutions, with varying degrees of efficiency. Having to add stuff repeatedly isn't really a performance problem, but let's assume it is. Also, the zeroes at the beginning can be prepended later, so let's not worry about producing them. If the algorithm provides them naturally, fine; if not, we correct it later.

从 Scala 2.8 开始，以下将给出 n >= period 的结果，通过使用 sliding 获得列表的滑动窗口:

Starting with Scala 2.8, the following would give the result for n >= period by using sliding to get a sliding window of the List:

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

尽管如此，虽然这相当优雅，但它并没有达到最佳性能，因为它没有利用已经计算好的加法.那么，说到它们，我们如何才能得到它们?

Nevertheless, although this is rather elegant, it doesn't have the best performance possible, because it doesn't take advantage of already computed additions. So, speaking of them, how can we get them?

假设我们这样写:

values sliding 2 map sum

我们有一个每两对之和的列表.让我们尝试使用这个结果来计算 4 个元素的移动平均值.上面的公式做了如下计算:

We have a list of the sum of each two pairs. Let's try to use this result to compute the moving average of 4 elements. The above formula made the following computation:

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

因此，如果我们取每个元素并将其添加到下一个第二个元素，我们将得到 4 个元素的移动平均值:

So if we take each element and add it to the second next element, we get the moving average for 4 elements:

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

我们可以这样做:

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

然后我们可以计算 8 个元素的移动平均值，依此类推.嗯，有一个众所周知的算法来计算遵循这种模式的事物.它最出名的是用于计算数字的幂.它是这样的:

We could then compute the moving average for 8 elements, and so on. Well, there is a well known algorithm to compute things that follow such pattern. It's most known for its use on computing the power of a number. It goes like this:

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

所以，让我们在这里应用它:

So, let's apply it here:

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的滑动窗口.如果大于，可能是偶数或奇数.

So, here's the logic. Period 0 is invalid, period 1 is equal to the input, period 2 is sliding window of size 2. If greater than that, it may be even or odd.

如果是奇数，我们将每个元素添加到下一个 (odd - 1) 元素的 movingSum 中.例如，如果是 3，我们将每个元素添加到接下来的 2 个元素的 movingSum 中.

If odd, we add each element to the movingSum of the next (odd - 1) elements. For example, if 3, we add each element to the movingSum of the next 2 elements.

如果偶数，我们计算 n/2 的 movingSum，然后将每个元素添加到之后的 n/2 步.

If even, we compute the movingSum for n / 2, then add each element to the one n / 2 steps afterwards.

有了这个定义，我们就可以回到问题上来:

With that definition, we can then go back to the problem and do this:

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

:::: 的使用效率稍低，但它是 O(period)，而不是 O(values.size).使用尾递归函数可以提高效率.而且，当然，我提供的滑动"的定义在性能方面是可怕的，但在 Scala 2.8 上会有更好的定义.请注意，我们无法在 List 上创建高效的 sliding 方法，但我们可以在 Iterable 上实现.

There's a slight inefficiency with regards to the use of :::, but it's O(period), not O(values.size). It can be made more efficient with a tail recursive function. And, of course, the definition of "sliding" I provided is horrendous performance-wise, but there will be a much better definition of it on Scala 2.8. Note that we can't make an efficient sliding method on a List, but we can do it on an Iterable.

说了这么多，我会采用第一个定义，并且只有在关键路径分析指出这是一个大问题时才进行优化.

Having said all that, I'd go with the very first definition, and optimize only if a critical path analysis pinpointed this as a big deal.

最后，让我们考虑一下我是如何解决这个问题的.我们有一个移动平均问题.移动平均线是列表上移动窗口"的总和除以该窗口的大小.所以，首先，我尝试得到一个滑动窗口，将其上的所有内容相加，然后除以大小.

To conclude, let's consider how I went about the problem. We have a moving average problem. A moving average is the sum of a moving "window" on a list, divided by the size of that window. So, first, I try to get a sliding window, sum everything on it, and then divide by the size.

下一个问题是避免重复已经计算的加法.在这种情况下，我尽可能使用最小的加法，并试图找出如何重复使用这些结果来计算更大的总和.

The next problem was to avoid repetition of already computed additions. In this case, I went to the smallest addition possible, and tried to figure out how to compute bigger sums reusing such results.

最后，让我们试着用你想象的方式解决这个问题，通过增加和减去之前的结果.获得第一个平均值很容易:

Finally, let's try to solve the problem the way you figured it, by adding and subtracting from the previous result. Getting the first average is easy:

 def movingAverage(values: List[Double], period: Int): List[Double] = {
   val first = (values take period).sum / period

现在我们列出两个清单.首先，要减去的元素列表.接下来是要添加的元素列表:

Now we make two lists. First, the list of elements to be subtracted. Next, the list of elements to be added:

   val subtract = values map (_ / period)
   val add = subtract drop period

我们可以使用 zip 添加这两个列表.这种方法只会产生与较小列表一样多的元素，从而避免了 subtract 大于必要的问题:

We can add these two lists by using zip. This method will only produce as many elements as the smaller list has, which avoids the problem of subtract being bigger than necessary:

   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

这是要返回的答案.整个函数如下所示:

which is the answer to be returned. The whole function looks like this:

 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
 }

这篇关于计算列表的移动平均线的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！