计算列表的移动平均值

Question

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

我似乎无法进入编写函数的模式.作为一名专业的功能程序员,您如何解决问题？

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

例如:给定列表values(2.0,4.0,7.0,6.0,3.0,8.0,12.0,9.0,4.0,1.0)和period4,函数应该返回:(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开始,以下将n >= period通过使用sliding获取List的滑动窗口来给出结果:

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个元素中.

如果是偶数,我们计算movingSumfor 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在a上创建有效的方法List,但我们可以在a 上进行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
 }

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

有人要求尾递归版; 尾递归与懒惰是一种权衡.当你的工作正在建立一个列表然后使你的函数尾递归通常很简单,这也不例外 - 只是将列表构建为子函数的参数.我们将累积到向量而不是列表,否则列表将向后构建,并且需要在结尾处反转.

(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的名为let); recur必须在Clojure中使用以消除尾调用.conj是一个广义的cons,以收集的自然方式附加 - 列表的开头和向量的结尾.

Answer 3

这是另一个(功能)Clojure解决方案:

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

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

如果需要,仍必须添加序列开头的零.

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

Answer 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.取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)."tails"也不会创建所有这些单独的列表,它只是引用原始列表的不同部分.它仍然不是一个很好的解决方案,但它只有一行:)

这是一个稍好但更长的解决方案,它使用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与"map"相同,但具有额外的运行状态/累加器参数,当参数通过列表时,该参数从先前的"映射"传递到下一个"映射".我们使用累加器作为移动平均值,并且由于我们的列表由刚刚离开滑动窗口的元素和刚刚输入的元素(我们刚刚压缩的列表)组成,我们的滑动函数采用第一个数字'x'远离平均值并添加第二个数字'y'.然后我们传递新的's'并返回's'除以'p'."snd"(第二个)只取一对(元组)的第二个成员,用于获取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].

哦,你需要导入模块"List"来编译任一解决方案.

Answer 6

这里有两种方法可以在Scala 2.8.0中进行移动平均(一个严格和一个懒惰).两者都假设vs中至少有p双打.

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

Answer 7

J编程语言有助于移动平均等程序.实际上,人物中的字符数(+/ % #)\比"移动平均数"少.

对于此问题中指定的值(包括名称'values'),这里是一种直接的编码方式:

   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.+/表示求和(Σ)并%表示除法(如经典符号÷).计算项目的计数(计数)是通过#.那么整个程序是值之和除以值的总和:+/ % #

此处写入的移动平均值计算的结果不包括原始问题中预期的前导零.那些零可以说不是预期计算的一部分.

这里使用的技术称为默认编程.它与函数式编程的无点式风格几乎相同.

Answer 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]))))

通常我会将collection或list参数放在最后,以使函数更容易理解.但在Clojure ......

(partial moving-average 4)

......太麻烦了,我通常最终这样做......

#(moving-average 4 %)

......在这种情况下,参数的顺序并不重要.