CODEWITHSUNDEEP
scalamapping
scala_newbie
scala_newbie

Reputation: 3465

Seq with maximal elements

I have a Seq and function Int => Int. What I need to achieve is to take from original Seq only thoose elements that would be equal to the maximum of the resulting sequence (the one, I'll have after applying given function):

def mapper:Int=>Int= x=>x*x
val s= Seq( -2,-2,2,2 )
val themax= s.map(mapper).max
s.filter( mapper(_)==themax)

But this seems wasteful, since it has to map twice (once for the filter, other for the maximum). Is there a better way to do this? (without using a cycle, hopefully)

EDIT The code has since been edited; in the original this was the filter line: s.filter( mapper(_)==s.map(mapper).max). As om-nom-nom has pointed out, this evaluates `s.map(mapper).max each (filter) iteration, leading to quadratic complexity.

Upvotes: 2

Views: 240

Answers (1)

Christopher Chiche
Christopher Chiche

Reputation: 15335

Here is a solution that does the mapping only once and using the `foldLeft' function:

The principle is to go through the seq and for each mapped element if it is greater than all mapped before then begin a new sequence with it, otherwise if it is equal return the list of all maximums and the new mapped max. Finally if it is less then return the previously computed Seq of maximums. 

def getMaxElems1(s:Seq[Int])(mapper:Int=>Int):Seq[Int] = s.foldLeft(Seq[(Int,Int)]())((res, elem) => {
  val e2 = mapper(elem)
  if(res.isEmpty || e2>res.head._2) 
    Seq((elem,e2)) 
  else if (e2==res.head._2) 
    res++Seq((elem,e2)) 
  else res 
}).map(_._1) // keep only original elements

// test with your list
scala> getMaxElems1(s)(mapper)
res14: Seq[Int] = List(-2, -2, 2, 2)

//test with a list containing also non maximal elements
scala> getMaxElems1(Seq(-1, 2,0, -2, 1,-2))(mapper)
res15: Seq[Int] = List(2, -2, -2)

Remark: About complexity

The algorithm I present above has a complexity of O(N) for a list with N elements. However:

  • the operation of mapping all elements is of complexity O(N)
  • the operation of computing the max is of complexity O(N)
  • the operation of zipping is of complexity O(N)
  • the operation of filtering the list according to the max is also of complexity O(N)
  • the operation of mapping all elements is of complexity O(M), with M the number of final elements

So, finally the algorithm you presented in your question has the same complexity (quality) than my answer's one, moreover the solution you present is more clear than mine. So, even if the 'foldLeft' is more powerful, for this operation I would recommend your idea, but with zipping original list and computing the map only once (especially if your map is more complicated than a simple square). Here is the solution computed with the help of *scala_newbie* in question/chat/comments.

def getMaxElems2(s:Seq[Int])(mapper:Int=>Int):Seq[Int] = {
  val mappedS = s.map(mapper) //map done only once 
  val m = mappedS.max         // find the max
  s.zip(mappedS).filter(_._2==themax).unzip._1
}

// test with your list
scala> getMaxElems2(s)(mapper)
res16: Seq[Int] = List(-2, -2, 2, 2)

//test with a list containing also non maximal elements
scala> getMaxElems2(Seq(-1, 2,0, -2, 1,-2))(mapper)
res17: Seq[Int] = List(2, -2, -2)

Upvotes: 3

Related Questions