CODEWITHSUNDEEP
scala
hbogert
hbogert

Reputation: 4363

Sliding window based on values (not index)

I have a sparse list of timestamps, let's dumb it down to:

val stamps = List(1,2,3,7,10,11)

Imagine I have a window size of three, what would be a Scala/Functional way to get the following output

valueWindowed (3, stamps) == List(
  // Starting at timestamp 1 of stamps, we include the next values which are no bigger than the current value + the window size
  List(1, 2, 3), 
  // Starting at timestamp 2 include the next values in this window
  List(2, 3), 
  List(3), // ...
  // This one is empty as the window starts at timestamp 4 and ends at 6 (inclusive)
  List(), 
  // This one _does_ include 7, as the windows starts at 5 and ends at 7 (inclusive)
  List(7), 
  List(7), 
  List(7),
  List(10),
  List(10,11),
  List(10,11),
  List(11)
)

Update

I have the following implementation, but it looks very procedural, jammed into functional constructs. Also the complexity is max(stamps) * stamps size

def valueWindowed(step: Int, times: List[Int]) = {
  for(j <- (1 to times.max).toIterator) yield{
    times.dropWhile(_ < j) takeWhile(_ < j+step)
  }
}

Upvotes: 0

Views: 296

Answers (1)

The Archetypal Paul
The Archetypal Paul

Reputation: 41779

Here's a functional one that is O(N) - where N is the range of the numbers in times, not the length of it. But it's not possible to do better than that since that's the size of your output.

def  valueWindowed(step:Int, times:List[Int]) = {
(times :+ times.last+step)
    .sliding(2)
    .flatMap{case List(a,b) => Some(a)::List.fill(b-a-1)(None)}
    .sliding(step)
    .map(_.flatten)
}

The first sliding and flatMap expand the list so it has Some(x) for all x in times, and None for all intermediate values (adding a sentinel value to get the last element included correctly). Then we take steps windows and use flatten to remove the None/convert the Some back

Upvotes: 1

Related Questions