F＃數學庫 - 計算平均

Question

我想知道是否有人計算在F＃整數數組/列表/序列的中位數微軟（或其它庫）的認識。我看到平均功能，但沒有中位數。

由於提前，

JP

Answer 1

拿起其中@布賴恩和@BrokenGlass不放過......

let inline median input = 
    let sorted = input |> Seq.toArray |> Array.sort 
    let m1,m2 = 
     let len = sorted.Length-1 |> float 
     len/2. |> floor |> int, len/2. |> ceil |> int 
    (sorted.[m1] + sorted.[m2] |> float)/2. 

//by marking the function inline, we gain some extra flexibility with static member constraints 
//val inline median : 
// seq< ^a> -> float 
// when ^a : comparison and ^a : (static member (+) : ^a * ^a -> ^b) and 
//   ^b : (static member op_Explicit : ^b -> float) 

（有點讓我長的數字類型間的轉換）

Here's描述了一個平均O（n）算法與C＃實現的鏈接。

Answer 2

如何

let a = input |> Seq.toArray |> Array.sort 
a.[a.Length/2] 

？ （在瀏覽器中編碼，任何錯誤都是我的。）

Answer 3

如果你絕對要出庫，你可以看看this question，或查找有關.NET統計庫的其他問題。

這裏是quickselect的實現。它預期時間爲O（n）和最壞情況下的時間爲O（n 2 ）。該類型的唯一限制是它們具有可比性。

/// Calculate the median of a list of items. 
/// The result is a tuple of two items whose mean is the median. 
let median xs = 
    /// Partition list into three piles; less-than, equal and greater-than 
    /// x: Current pivot 
    /// xs: Sublist to partition 
    /// cont: Continuation function 
    let rec partition x xs cont = 
     match xs with 
     | [] -> 
      // place pivot in equal pile 
      cont [] 0 [x] 1 [] 0 
     | y::ys -> 
      if y < x then 
       // place item in less-than pile 
       partition x ys (fun lts n1 eqs n2 gts n3 -> 
        cont (y::lts) (n1+1) eqs n2 gts n3) 
      elif y = x then 
       // place pivot in equal pile, and use item as new pivot, 
       // so that the order is preserved 
       partition y ys (fun lts n1 eqs n2 gts n3 -> 
        cont lts n1 (x::eqs) (n2+1) gts n3) 
      else // y > x 
       // place item in greater-than pile 
       partition x ys (fun lts n1 eqs n2 gts n3 -> 
        cont lts n1 eqs n2 (y::gts) (n3+1)) 
    /// Partition input and recurse into the part than contains the median 
    /// before: Number of elements before this sublist. 
    /// xs:  Current sublist. 
    /// after: Number of elements after this sublist. 
    let rec loop before xs after = 
     match xs with 
     | [] -> failwith "Median of empty list" 
     | x::xs -> 
      partition x xs (fun lts numlt eqs numeq gts numgt -> 
       if before + numlt > numeq + numgt + after then 
        // Recurse into less pile 
        loop before lts (after + numeq + numgt) 
       elif before + numlt = numeq + numgt + after then 
        // Median is split between less and equal pile 
        (List.max lts, x) 
       elif before + numlt + numeq > numgt + after then 
        // Median is completely inside equal pile 
        (x, x) 
       elif before + numlt + numeq = numgt + after then 
        // Median is split between equal and greater pile 
        (x, List.min gts) 
       else 
        // Recurse into greater pile 
        loop (before + numlt + numeq) gts after) 
    loop 0 xs 0 

我用延續使它尾遞歸。我試圖以這樣一種方式編寫調用，它類似於一個簡單的遞歸調用;而不是let x, y = f a b; body我用f a b (fun x y -> body)。可以用CPS monad稍微簡化一下。

實施例：

> median [1];; 
val it : int * int = (1, 1) 
> median [1;2];; 
val it : int * int = (1, 2) 
> median [1..9];; 
val it : int * int = (5, 5)