CODEWITHSUNDEEP
scala
SiXUlm
SiXUlm

Reputation: 159

List whose elements depend on the previous ones

Suppose I have a list of increasing integers. If the difference of 2 consecutive numbers is less than a threshold, then we index them by the same number, starting from 0. Otherwise, we increase the index by 1.

For example: for the list (1,2,5,7,8,11,15,16,20) and the threshold = 3, the output will be: (0, 0, 1, 1, 1, 2, 3, 3, 4).

Here is my code:

  val listToGroup = List(1,2,5,7,8,11,15,16,20)
  val diff_list = listToGroup.sliding(2,1).map{case List(i, j) => j-i}.toList

  val thres = 2

  var j=0
  val output_ = for(i <- diff_list.indices) yield {
    if (diff_list(i) > thres ) {
      j += 1
    }
    j
  }
  val output = List.concat(List(0), output_)

I'm new to Scala and I feel the list is not used efficiently. How can this code be improved?

Upvotes: 1

Views: 57

Answers (2)

Suma
Suma

Reputation: 34413

You can avoid the mutable variable by using scanLeft to get a more idiomatic code:

val output = diff_list.scanLeft(0) { (count, i) => 
  if (i > thres) count + 1
  else count
}

Your code shows some constructs which are usually avoided in Scala, but common when coming from procedural langugues, like: for(i <- diff_list.indices) ... diff_list(i) can be replaced with for(i <- diff_list).

Other than that, I think your code is efficient - you need to traverse the list anyway and you do it in O(N). I would not worry about efficiency here, more about style and readability.

My rewrite to how I think it would be more natural in Scala for the whole code would be:

val listToGroup = List(1,2,5,7,8,11,15,16,20)

val thres = 2

val output = listToGroup.zip(listToGroup.drop(1)).scanLeft(0) { case (count, (i, j)) => 
  if (j - i > thres) count + 1
  else count
}

My adjustments to your code:

  • I use scanLeft to perform the result collection construction
  • I prefer x.zip(x.drop(1)) over x.sliding(2, 1) (constructing tuples seems a bit more efficient than constructing collections). You could also use x.zip(x.tail), but that does not handle empty x
  • I avoid the temporary result diff_list

Upvotes: 3

Shankar Shastri
Shankar Shastri

Reputation: 1154

val listToGroup = List(1, 2, 5, 7, 8, 11, 15, 16, 20)

val thres = 2

listToGroup
  .sliding(2)
  .scanLeft(0)((a, b) => { if (b.tail.head - b.head > thres) a + 1 else a })
  .toList
  .tail

You don't need to use mutable variable, you can achieve the same with scanLeft.

Upvotes: 2

Related Questions