Вычислить медиану до 5 в Scala

Question

Итак, отвечая на какой-то другой вопрос, я наткнулся на необходимость вычисления медианы 5. Теперь есть аналогичный вопрос на другом языке, но я хочу для него алгоритм Scala, и я 'я не уверен, что доволен собой.

Answer 1

Вот неизменная версия Scala, которая имеет минимальное количество сравнений (6) и выглядит не слишком уродливо:

def med5(five: (Int,Int,Int,Int,Int)) = {

  // Return a sorted tuple (one compare)
  def order(a: Int, b: Int) = if (a<b) (a,b) else (b,a)

  // Given two self-sorted pairs, pick the 2nd of 4 (two compares)
  def pairs(p: (Int,Int), q: (Int,Int)) = {
    (if (p._1 < q._1) order(p._2,q._1) else order(q._2,p._1))._1
  }

  // Strategy is to throw away smallest or second smallest, leaving two self-sorted pairs
  val ltwo = order(five._1,five._2)
  val rtwo = order(five._4,five._5)
  if (ltwo._1 < rtwo._1) pairs(rtwo,order(ltwo._2,five._3))
  else pairs(ltwo,order(rtwo._2,five._3))
}

---

Редактировать: По просьбе Даниэля, вот модификация для работы со всеми размерами и в массивах, поэтому она должна быть эффективной. Я не могу сделать это красиво, поэтому эффективность - следующая лучшая вещь. (> 200M медиан / сек с предварительно выделенным массивом 5, что чуть более чем в 100 раз быстрее, чем версия Даниила, и в 8 раз быстрее, чем моя неизменная версия выше (для длины 5)).

def med5b(five: Array[Int]): Int = {

  def order2(a: Array[Int], i: Int, j: Int) = {
    if (a(i)>a(j)) { val t = a(i); a(i) = a(j); a(j) = t }
  }

  def pairs(a: Array[Int], i: Int, j: Int, k: Int, l: Int) = {
    if (a(i)<a(k)) { order2(a,j,k); a(j) }
    else { order2(a,i,l); a(i) }
  }

  if (five.length < 2) return five(0)
  order2(five,0,1)
  if (five.length < 4) return (
    if (five.length==2 || five(2) < five(0)) five(0)
    else if (five(2) > five(1)) five(1)
    else five(2)
  )
  order2(five,2,3)
  if (five.length < 5) pairs(five,0,1,2,3)
  else if (five(0) < five(2)) { order2(five,1,4); pairs(five,1,4,2,3) }
  else { order2(five,3,4); pairs(five,0,1,3,4) }
}

Answer 2

Боже, способ обдумать это, ребята.

def med5(a : Int, b: Int, c : Int, d : Int, e : Int) = 
   List(a, b, c, d, e).sort(_ > _)(2)

Answer 3

Как и предполагалось, вот мой собственный алгоритм:

def medianUpTo5(arr: Array[Double]): Double = {
    def oneAndOrderedPair(a: Double, smaller: Double, bigger: Double): Double =
        if (bigger < a) bigger
        else if (a < smaller) smaller else a

    def partialOrder(a: Double, b: Double, c: Double, d: Double) = {
        val (s1, b1) = if (a < b) (a, b) else (b, a)
        val (s2, b2) = if (c < d) (c, d) else (d, c)
        (s1, b1, s2, b2)
    }

    def medianOf4(a: Double, b: Double, c: Double, d: Double): Double = {
        val (s1, b1, s2, b2) = partialOrder(a, b, c, d)
        if (b1 < b2) oneAndOrderedPair(s2, s1, b1)
        else oneAndOrderedPair(s1, s2, b2)
    }

    arr match {
        case Array(a)       => a
        case Array(a, b)    => a min b
        case Array(a, b, c) =>
            if (a < b) oneAndOrderedPair(c, a, b) 
            else oneAndOrderedPair(c, b, a)
        case Array(a, b, c, d) => medianOf4(a, b, c, d)
        case Array(a, b, c, d, e) =>
            val (s1, b1, s2, b2) = partialOrder(a, b, c, d)
            if (s1 < s2) medianOf4(e, b1, s2, b2)
            else medianOf4(e, b2, s1, b1)
    }
}