CODEWITHSUNDEEP
scalagenericsnumbers
JSR29
JSR29

Reputation: 354

Scala median function for Int and Long

I am new to scala language and was trying to implement the median function which should work for Int and Long both, this is what I tried to do: 

 def getMedian[T: Numeric](seq: Seq[T]): T = {
      val sortedSeq = seq.sortWith(_ < _)
      if (seq.size % 2 == 1) sortedSeq(sortedSeq.size / 2)  else {
            val (up, down) = sortedSeq.splitAt(seq.size / 2)
            (up.last + down.head) / 2
       }
  }

but the comparison operator is not valid for numeric class. What can I do to accomplish this.

Upvotes: 3

Views: 1346

Answers (1)

Andrey Tyukin
Andrey Tyukin

Reputation: 44918

There is a problem with the result type. If you divide an integer by 2, the result is not necessarily an integer. But who decides about the precision of the result? Should it be Double? Or would Float be close enough?

Here is a solution where you have to specify the result type explicitly:

def getMedian[T: Ordering, F]
  (seq: Seq[T])
  (implicit conv: T => F, f: Fractional[F]): F = {
    val sortedSeq = seq.sorted
    if (seq.size % 2 == 1) sortedSeq(sortedSeq.size / 2)  else {
      val (up, down) = sortedSeq.splitAt(seq.size / 2)
      import f._
      (conv(up.last) + conv(down.head)) / fromInt(2)
    }
}

You now can use it as follows:

println(getMedian[Int, Float](List(1,2,3,4)))
println(getMedian[Int, Double](List(1,2,3,4)))

It outputs 2.5 two times, but the first one is single precision, whereas the last one is computed with double precision.

While you're at it, you could implement an O(n) selection algorithm like for example quickselect, and use T: Ordering for comparing elements. Neither of those algorithms relies on any arithmetic operations.

Upvotes: 5

Related Questions