Int 和 Long 的 Scala 中值函数

Question

我是 scala 语言的新手，正在尝试实现应该适用于 Int 和 Long 的中值函数，这就是我尝试做的：

 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
       }
  }

但比较运算符对于数字类无效。我能做些什么来实现这个目标。

Answer 1

结果类型有问题。如果将一个整数除以 2，结果不一定是整数。但谁来决定结果的精确度呢？应该是吗Double？或者足够Float接近？

这是一个必须明确指定结果类型的解决方案：

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)
    }
}

您现在可以按如下方式使用它：

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

它输出两次 2.5，但第一次是单精度，而最后一次是用双精度计算的。

当您这样做时，您可以实现O(n) 选择算法，例如快速选择，并用于T: Ordering比较元素。这些算法都不依赖于任何算术运算。