scala - 计算列表的移动平均值

Question

这个周末我决定尝试一下 Scala 和 Clojure。我精通面向对象编程，因此 Scala 作为一种语言很容易上手，但我想尝试一下函数式编程。这就是困难的地方。

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

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

例如:给定列表值 (2.0, 4.0, 7.0, 6.0, 3.0, 8.0, 12.0, 9.0, 4.0, 1.0)，以及句点 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 开始，以下代码将通过使用 sliding 获取列表的滑动窗口来给出 n >= period 的结果:

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

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

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

有了这个定义，我们就可以回到问题并执行以下操作:

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 上实现。

话虽如此，我还是会采用第一个定义，并且仅当关键路径分析指出这是一个大问题时才进行优化。

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

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

最后，让我们尝试按照您的计算方式解决问题，即对先前的结果进行加法和减法。获得第一个平均值很容易:

 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
 }