F＃数学ライブラリ - メジアンを計算する

Question

F＃で整数の配列/リスト/シーケンスの中央値を計算するためにMicrosoft（または他のライブラリ）を知っている人がいるかどうかは疑問でした。私は平均関数を参照しますが、中央値はありません。事前に

おかげで、

JP

Answer 1

@Brianと@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 ）です。型の唯一の制限は、それらが匹敵するということです。

/// 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で少し簡略化できます。

例：Cでは

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