CODEWITHSUNDEEP
listscalasumrolling-sum
FlyUFalcon
FlyUFalcon

Reputation: 344

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

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.

Upvotes: 8

Views: 957

Answers (4)

CervEd
CervEd

Reputation: 4233

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.

Upvotes: 1

User9123
User9123

Reputation: 1733

  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
  }

Upvotes: 6

Raman Mishra
Raman Mishra

Reputation: 2686

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)

Upvotes: 2

jwvh
jwvh

Reputation: 51271

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)

Upvotes: 3

Related Questions