Scala: Calculating the Moving Sum of a List with a fixed window

Question

I am new to Scala and I want to calculate a moving sum with a fixed window for a list.

For example: Given the list values (1.0, 2.0, 3.0, 6.0, 7.0, 8.0, 12.0, 9.0, 4.0, 1.0), and the period 4, the function should return: (1.0, 3.0, 6.0, 12.0, 18.0, 24.0, 33.0, 36.0, 33.0, 26.0)

If list.size < period then just return cumulative sum.

I have made some attempts

def mavg(values: List[Double], period: Int): List[Double] = {
  if (values.size <= period) (values.sum ) :: List.fill(period -1)(values.sum ) else {
      val rest: List[Double] = mavg(values.tail, period)
      (rest.head + ((values.head - values(period)))):: rest
  }
}

However, I got

List(12.0, 18.0, 24.0, 33.0, 36.0, 33.0, 26.0, 26.0, 26.0, 26.0

which is not correct. I dont want to use Pyspark to get the results. Can someone help?

Many thanks.

I notice that the window grows (1st element, 1st 2 elements, 1st 3 elements, etc.) but it doesn't shrink (last 4 elements, last 3 elements, last 2 elements, etc.). Is that intentional? — jwvh, Apr 29 '20 at 22:07

User9123 · Answer 1 · 2020-04-30T10:13:51.603

6

  def mavg(values: Seq[Double], period: Int): Seq[Double] = {
    (Seq.fill(math.min(period - 1, values.length))(0.0) ++ values) // padding zeros
      .sliding(period)                  
      .map(_.sum)
      .toSeq
  }

edited Apr 30 '20 at 10:13

answered Apr 29 '20 at 22:39

User9123

1,643
1
8
21

2

be aware that this returns `List(0.0)` when `values = Seq()` and `period > 1` – CervEd Apr 30 '20 at 09:52
@User9123, there might be more. Had to do some acrobatics myself in my answer – CervEd Apr 30 '20 at 11:23

score 3 · Answer 2 · answered Apr 29 '20 at 22:14

Here's one way to tackle it.

def mavg(values: List[Double], period: Int): List[Double] =
  values.inits    //shrinking list of inits
        .toList   //result type
        .reverse  //growing list of inits
        .tail     //drop the empty one
        .map(_.takeRight(period).sum) //sum the window

testing:

mavg(List(1.0, 2.0, 3.0, 6.0, 7.0, 8.0, 12.0, 9.0, 4.0, 1.0), 4)
//res0: List[Double] = List(1.0, 3.0, 6.0, 12.0, 18.0, 24.0, 33.0, 36.0, 33.0, 26.0)

score 2 · Answer 3 · answered Apr 29 '20 at 22:59

This is another way you can do this:

  val l = List(1.0, 2.0, 3.0, 6.0, 7.0, 8.0, 12.0, 9.0, 4.0, 1.0,5.0,1.0,2.0)
  def mavg(step: Int, list: List[Double], ans: List[Double] = List.empty[Double], splitCount: Int = 0): List[Double] = {
    if (list.length > 1) {
      mavg(step - 1, list.take(step), list.sliding(step, 1).toList.map(_.sum) ::: ans, splitCount + 1)
    } else {
      ans.splitAt(splitCount + 2)._1.sliding(1, 2).toList.flatten ::: ans.drop(splitCount + 2)
    }
  }

  val ans = mavg(4, l)
  println(ans)

CervEd · Answer 4 · 2020-04-30T20:10:49.597

Another approach, similar to the answer by @User9123

The difference is it doesn't calculate the sum of all elements in the sliding window, rather it subtracts the value of the last windows head from its sum and adds the value of the next windows head to yield the next rolling sum. This should be more efficient for large windows.

def rollingSum[N](values: Seq[N], period: Int)(
    implicit num: Numeric[N]
): Seq[N] = {
  import num._
  values match {
    case values if period == 1 => values // Can't slide on period 1
    case head :: tail if period < values.size =>
      (Seq.fill(period - 2)(num.zero) ++ (values)) // zero padding
        .sliding(period)
        .foldLeft((num.zero, Seq(head))) { // Use a tuple to store previous head
          case ((prevHead, acc), y) => {
            (y.head, acc :+ acc.last - prevHead + y.last) // do the magic
          }
        }
        ._2 // only return the result
    case head :: tail => tail.scanLeft(head)(_ + _) // Regular cummulative sum
    case Nil          => Nil
  }
}

I also added some guards for special cases that need to be handled and made it a generic function for all Numeric types.

Here's a running example with some test cases.

Scala: Calculating the Moving Sum of a List with a fixed window

4 Answers4