计算列表的移动平均值 [英] Calculating the Moving Average of a List
问题描述
这个周末，我决定在一些Scala和Clojure尝试我的手。我精通面向对象的编程，所以Scala很容易拾起作为一种语言，但想尝试功能编程。这是它的困难。
我只是不能让我的头变成写作功能的模式。作为专家函数式程序员，你如何处理一个问题？
给定一个值列表和一个定义的求和周期，你将如何生成一个简单的列表列表的移动平均值？
例如：给定列表 values （2.0，4.0，7.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）
花了一天时间仔细考虑后，我能在Scala找到的最好的是：
def simpleMovingAverage（values：List [Double]，period：Int）：List [Double] = {
（for（i < values.length）
yield
if（i
}
我知道这是非常低效的，我宁愿做一些类似： p>
其中n <周期：ma（n）= 0
其中n =周期：ma（n）= sum（值（1）到值（n））/周期
其中n> period：man（n）= ma（n-1） - （value（n-period）/ period）+（value（n）/ period）
现在这将很容易做一个命令式的风格，但我不能为我的生活如何表达的功能。
有趣的问题。我可以想到很多解决方案，具有不同程度的效率。不得不重复添加东西不是真的是性能问题，但让我们假设它。此外，开头的零可以在以后加入，所以让我们不用担心生成它们。如果算法提供它们自然，精细;
从Scala 2.8开始，以下将给出结果 n> = period 使用滑动以获取列表的滑动窗口：
def simpleMovingAverage（values：List [Double]，period：Int）：List [Double] =
List.fill（period - 1）（0.0） map（_ / period））
然而，虽然这是相当优雅，最佳性能可能，因为它不利用已经计算的加法。
我们这样写：
values sliding 2 map sum
我们有一个两对。让我们尝试使用这个结果来计算4个元素的移动平均值。上述公式进行了以下计算：
从d1，d2，d3，d4，d5，d6，...
到（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 {
情况0 => 1
case 1 => n
case 2 => n * n
情况奇数如果奇数％2 == 1 =>功率（n，（奇数-1））* n
case even =所以，让我们来看一下这个例子，我们可以看到这个例子。应用它： def movingSum（values：List [Double]，period：Int）：List [Double] = period match {
case 0 => throw new IllegalArgumentException
case 1 =>值
case 2 =>值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 。
我们计算 movingSum 为 n / 2 ，然后将每个元素添加到 n /
根据这个定义，我们可以回到问题，然后执行：
def simpleMovingAverage（values：List [Double]，period：Int）：List [Double] =
List.fill（period - 1） ）:::（movingSum（values，period）map（_ / period））
关于使用 ::: 的低效率，但它是O（周期），而不是O（values.size）。使用尾递归函数可以使其更高效。当然，我提供的滑动的定义是可怕的性能，但在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 =减去掉期
我们可以使用 code>。这个方法只会产生与较小列表一样多的元素，这避免了减去大于必要的问题：
val addAndSubtract = add zip subtract map Function.tupled（_ - _）
b $ b
我们使用折叠来完成结果：
val res =（addAndSubtract.foldLeft ：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减法映射Function.tupled（_ - _）
val res =（addAndSubtract.foldLeft（first :: List.fill（period - 1）（0.0））{
（acc，add）=> ;（add + acc.head）:: acc
}）reverse
res
}
$ b b
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?
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)
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.
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?
Let's say we write this:
values sliding 2 map sum
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), ...
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), ...
We may do it like this:
res zip (res drop 2) map Function.tupled(_+_)
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(_+_)
}
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.
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.
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))
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
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(_ - _)
We finish by composing the result with a fold:
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屋！
