斯卡拉计算中位数最多为5

因此，在回答其他一些问题时，我偶然发现了计算5的中位数的必要性。现在，在另一种语言中有similar question，但我想要一个Scala算法，而我我不确定我对我很满意。斯卡拉计算中位数最多为5

2011-01-21 Daniel C. Sobral

你为什么不张贴你的开始？（我最初被追求答案和相关答案混淆，因为我只知道三位数的中位数。） – Raphael 2011-01-21 17:46:41

@Raphael Done。我也改变了一些措辞，因为我对计算一到五个元素的中位数的东西很感兴趣。 – 2011-01-21 20:17:08

下面是具有最小数量不变的斯卡拉版本进行比较（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)) 
}

编辑：根据要求由Daniel，这里的一起工作的修改所有的大小和数组，所以它应该是有效的。我无法做到这一点，所以效率是下一个最好的事情。（> 200M中位数/秒，预分配数组为5，比丹尼尔版本略快100倍以上，比我上面的永久版本（长度为5）快8倍）。

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

来源

2011-01-21 17:40:47

美丽，但它缺少4例。 ;-) – 2011-01-21 20:16:03

至于建议，这是我自己的算法：

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

来源

2011-01-21 20:14:05

哎呀，这样过度觉得，伙计们。

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

来源

2011-01-22 06:44:58 Malvolio

斯卡拉计算中位数最多为5

回答

相关问题