高达5斯卡拉的计算中位数 [英] Compute median of up to 5 in Scala

问题描述

所以，在回答我偶然发现了计算5.现在的中位数的必要性，一些其他的问题，有一个的类似的问题在另一种语言，但我希望有一个Scala的算法吧，我不知道我很高兴我的。

So, while answering some other question I stumbled upon the necessity of computing the median of 5. Now, there's a similar question in another language, but I want a Scala algorithm for it, and I'm not sure I'm happy with mine.

推荐答案

下面是一个具有最少数量的不可变的Scala版本相比较（6），看起来并不太难看：

Here's an immutable Scala version that has the minimum number of compares (6) and doesn't look too ugly:

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

---

编辑：所要求的丹尼尔，这里的修改与各种规模的工作，并且在阵，因此它应该是有效的。我不能让pretty的，所以效率是未来最好的事情。 （> 200M中位数/秒，为5 pre-分配的数组，这是略多于100倍比丹尼尔的版本速度更快，和8倍比我一成不变以上版本（更快的长度5））。

---

As requested by Daniel, here's a modification to work with all sizes, and in arrays so it should be efficient. I can't make it pretty, so efficiency is the next best thing. (>200M medians/sec with a pre-allocated array of 5, which is slightly more than 100x faster than Daniel's version, and 8x faster than my immutable version above (for lengths of 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) }
}

这篇关于高达5斯卡拉的计算中位数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！