Get MAD with Outliers with an Improved Median Function

This post presents a more robust method of detecting outliers in sample data than commonly used. The method is based on the median and an optimised F# median function is developed.

Background

Researchers most commonly use standard deviation around the mean to detect outliers. This is a problem because the mean and standard deviation give greater weight to extreme data points.

The mean is the point that minimises the sum of the square deviations, whereas the median is the point that minimises the sum of the absolute deviations. The median and median absolute deviation give a more robust measure of statistical dispersion and are more resilient to outliers.

When a politician says average wages are increasing be sure to check the median is being reported.

Median Absolute Deviation

The median is the value separating the higher half of the sample from the lower half.

The median absolute deviation is defined as

\[\operatorname{MAD} = \operatorname{median}\left(\left|x_i - \operatorname{median}(x_i)\right|\right)\]

Outliers can be identified as points that are outside a fixed multiple of the median absolute deviation from the median. Recommended values for this multiple are 2.5 or 3.

Median and MAD code

The following median function makes use of the MODIFIND algorithm by Vladimir Zabrodsky. It provides a 20-30% performance improvement over the Quickselect algorithm.

The array while loops allow equality which improves performance when there is duplication and ordering in the data. The selectInPlace function has also been extended to optionally return the middle of the kth and the k+1 element.

  1: 
  2: 
  3: 
  4: 
  5: 
  6: 
  7: 
  8: 
  9: 
 10: 
 11: 
 12: 
 13: 
 14: 
 15: 
 16: 
 17: 
 18: 
 19: 
 20: 
 21: 
 22: 
 23: 
 24: 
 25: 
 26: 
 27: 
 28: 
 29: 
 30: 
 31: 
 32: 
 33: 
 34: 
 35: 
 36: 
 37: 
 38: 
 39: 
 40: 
 41: 
 42: 
 43: 
 44: 
 45: 
 46: 
 47: 
 48: 
 49: 
 50: 
 51: 
 52: 
 53: 
 54: 
 55: 
 56: 
 57: 
 58: 
 59: 
 60: 
 61: 
 62: 
 63: 
 64: 
 65: 
 66: 
 67: 
 68: 
 69: 
 70: 
 71: 
 72: 
 73: 
 74: 
 75: 
 76: 
 77: 
 78: 
 79: 
 80: 
 81: 
 82: 
 83: 
 84: 
 85: 
 86: 
 87: 
 88: 
 89: 
 90: 
 91: 
 92: 
 93: 
 94: 
 95: 
 96: 
 97: 
 98: 
 99: 
100: 
101: 
102: 
103: 
104: 
105: 
106: 
107: 
108: 
109: 
110: 
111: 
112: 
113: 
114: 
115: 
116: 
117: 
118: 
119: 
120: 
121: 
122: 
123: 
124: 
125: 
126: 
127: 
128: 
129: 
module Statistics =
    /// Returns the median of three input values.
    let inline median3 a b c =
        if a<=b then
            if b<=c then b
            elif c<=a then a
            else c
        else
            if a<=c then a
            elif c<=b then b
            else c
    /// Returns the minimum value of a subsection of an array.
    let inline minSub (a:_[]) lo hi =
        let mutable v = a.[lo]
        for i = lo+1 to hi do
            let nv = a.[i]
            if nv<v then v<-nv
        v
    /// Returns the maximum value of a subsection of an array.
    let inline maxSub (a:_[]) lo hi =
        let mutable v = a.[lo]
        for i = lo+1 to hi do
            let nv = a.[i]
            if nv>v then v<-nv
        v
    /// Returns the middle point of the two smallest values of a subsection of an array.
    let inline min2middleSub (a:_[]) lo hi =
        let mutable v0 = a.[lo]
        let mutable v1 = a.[lo+1]
        if v1<v0 then
            let tmp = v0
            v0<-v1
            v1<-tmp
        for i = lo+2 to hi do
            let nv = a.[i]
            if nv<v0 then
                v1<-v0
                v0<-nv
            elif nv<v1 then
                v1<-nv
        middleOrdered v0 v1
    /// Returns the middle point of the two largest values of a subsection of an array.
    let inline max2middleSub (a:_[]) lo hi =
        let mutable v0 = a.[lo]
        let mutable v1 = a.[lo+1]
        if v1>v0 then
            let tmp = v0
            v0<-v1
            v1<-tmp
        for i = lo+2 to hi do
            let nv = a.[i]
            if nv>v0 then
                v1<-v0
                v0<-nv
            elif nv>v1 then
                v1<-nv
        middleOrdered v1 v0
    /// Swap two elements in an array.
    let inline swap (a:_[]) i j =
        let temp = a.[i]
        a.[i]<-a.[j]
        a.[j]<-temp
    /// Swap two elements in an array if the first is larger than the second.
    let inline swapIf (a:_[]) i j =
        let ai = a.[i]
        let aj = a.[j]
        if ai>aj then
            a.[i]<-aj
            a.[j]<-ai
    /// Returns the kth smallest element in an array and optionally the middle with
    /// the next largest. Elements will be reordered in place and cannot be equal
    /// to the max or min value of the generic type.
    let inline selectInPlace (a:_[]) k middleNext =
        let rec outerLoop lo hi =
            swapIf a lo k
            swapIf a lo hi
            swapIf a k hi
            let pivot = a.[k]
            let resetLo = if a.[lo]=pivot then a.[lo]<-minValue(); true else false
            let resetHi = if a.[hi]=pivot then a.[hi]<-maxValue(); true else false
            let mutable i = lo+1
            let mutable j = hi-1
            while a.[i]<=pivot do i<-i+1
            while a.[j]>=pivot do j<-j-1
            while i<k && k<j do
                swap a i j
                i<-i+1
                j<-j-1
                while a.[i]<=pivot do i<-i+1
                while a.[j]>=pivot do j<-j-1
            if i<j then
                swap a i j
                if k<j then
                    i<-lo
                    j<-j-1
                    while a.[j]>=pivot do j<-j-1
                else
                    j<-hi
                    i<-i+1
                    while a.[i]<=pivot do i<-i+1
            else
                if k<j then i<-lo
                elif k>i then j<-hi
            if resetLo then a.[lo]<-pivot
            if resetHi then a.[hi]<-pivot
            if i>=j then if middleNext then if k+1=i then
                                                minSub a i hi |> middleOrdered pivot
                                            else pivot 
                         else pivot
            elif k=i then if middleNext then min2middleSub a i j else minSub a i j
            elif k=j then if middleNext then max2middleSub a i j else maxSub a i j
            else outerLoop i j
        outerLoop 0 (Array.length a-1)
    /// Returns the median of an array. Elements will be reordered in place and
    /// cannot be equal to the max or min value of the generic type.
    let inline medianInPlace (a:_[]) =
        match Array.length a-1 with
        | 0 -> a.[0]
        | 1 -> middle a.[0] a.[1]
        | 2 -> median3 a.[0] a.[1] a.[2]
        | last -> selectInPlace a (last/2) (last%2=1)
    /// Returns the median and median absolute deviation of an array.
    /// Elements cannot be equal to the max or min value of the generic type.
    let inline medianAndMAD (a:_[]) =
        let a = Array.copy a
        let median  = medianInPlace a
        for i = 0 to Array.length a-1 do
            a.[i]<-abs(a.[i]-median)
        median,medianInPlace a

Property and Performance testing

A simple FsCheck property test comparing the result with a full sort version ensures no mistakes have been made in the implementation.

The performance versus a full sort algorithm and the Math.Net C# Quickselect implementation are compared for different degrees of duplication and sorting.

The performance testing library developed in a previous post is used after extending it to allow subfunction measurement. This is run from the build script in 64-bit Release mode.

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
43: 
44: 
45: 
46: 
47: 
48: 
49: 
50: 
51: 
52: 
53: 
54: 
55: 
56: 
57: 
58: 
59: 
60: 
61: 
62: 
63: 
64: 
module StatisticsTests =
    let inline medianQuickSelect (a:float[]) =
        MathNet.Numerics.Statistics.ArrayStatistics.MedianInplace a

    let inline medianFullSort a =
        Array.sortInPlace a
        let l = Array.length a
        if l%2=0 then
            let i = l/2
            let x = a.[i-1]
            let y = a.[i]
            x+(y-x)*0.5
        else a.[l/2]

    [<Property>]
    let MedianProp (x:int) (xs:int list) =
        let l = x::xs |> List.map float
        let m1 = List.toArray l |> Statistics.medianInPlace
        let m2 = List.toArray l |> medianFullSort 
        m1=m2

    type Duplication =
        | Low | Medium | High
        member i.ToInt = match i with | Low->500000000 | Medium->5000 | High->50
        override i.ToString() = match i with | Low->"Low" | Medium->"Medium" | High->"High"

    type Sorted =
        | No | Part | Yes
        override i.ToString() = match i with | No->"No" | Part->"Part" | Yes->"Yes"

    let list (duplication:Duplication) (sorted:Sorted) =
        let r = System.Random 123
        let next() = r.Next(0,duplication.ToInt) |> float
        Seq.init 5000 (fun i ->
            let l = List.init (i+1) (fun _ -> next())
            match sorted with
            | No -> l
            | Yes -> List.sort l
            | Part ->
                let a = List.sort l |> List.toArray
                let len = Array.length a
                Seq.iter (fun _ -> Statistics.swap a (r.Next len) (r.Next len)) {1..len/4}
                List.ofArray a
            )

    [<Fact>]
    let MedianPerfTest() =
        printfn
            "| Duplication |   Sorted   |  Current  |  MathNet  |  FullSort  |  1.000 =  |"
        printfn
            "|:-----------:|:----------:|:---------:|:---------:|:----------:|:---------:|"
        Seq.collect (fun d -> Seq.map (fun s -> (d,s),list d s) [No;Part;Yes])
            [Low;Medium;High]
        |> Seq.iter (fun ((d,s),lists) ->
            let timeStatistics f =
                Performance.timeStatistics
                    (fun timer -> Seq.iter (List.toArray >> timer f >> ignore) lists)
            let p1 = timeStatistics Statistics.medianInPlace
            let p2 = timeStatistics medianQuickSelect
            let p3 = timeStatistics medianFullSort
            printfn
                "|    %-6s   |    %-4s    |   1.000   |  %6.3f   |   %6.3f   |  %.4fs  |"
                (string d) (string s) (p2.Mean/p1.Mean) (p3.Mean/p1.Mean) p1.Mean
        )

Duplication

Sorted

Current

MathNet

FullSort

1.000 =

Low

No

1.000

1.369

6.582

0.1028s

Low

Part

1.000

1.350

9.269

0.0476s

Low

Yes

1.000

1.516

12.964

0.0106s

Medium

No

1.000

1.373

6.577

0.1018s

Medium

Part

1.000

1.397

9.471

0.0478s

Medium

Yes

1.000

1.840

17.519

0.0100s

High

No

1.000

1.341

4.745

0.1059s

High

Part

1.000

1.576

8.050

0.0526s

High

Yes

1.000

3.193

26.390

0.0087s

Conclusion

Optimised generic select, median and median absolute deviation functions have been developed.

The performance results show a good improvement over Quickselect which is already an optimised algorithm. The performance of the code is also more predictable due to its handling of duplication and partially sorted data.

This also demonstrates how property based testing and a performance testing library can be used together to optimise algorithms.

namespace System
namespace System.Diagnostics
type PropertyAttribute = | FactAttribute

Full name: Main.PropertyAttribute
union case PropertyAttribute.FactAttribute: PropertyAttribute
Multiple items
type AutoOpenAttribute =
  inherit Attribute
  new : unit -> AutoOpenAttribute
  new : path:string -> AutoOpenAttribute
  member Path : string

Full name: Microsoft.FSharp.Core.AutoOpenAttribute

--------------------
new : unit -> AutoOpenAttribute
new : path:string -> AutoOpenAttribute
val sqr : x:'a -> 'b (requires member ( * ))

Full name: Main.Functions.sqr
val x : 'a (requires member ( * ))
Multiple items
union case MinValueGen.MinValueGen: MinValueGen

--------------------
type MinValueGen =
  | MinValueGen
  static member ( => ) : MinValueGen * int -> int
  static member ( => ) : MinValueGen * int64 -> int64
  static member ( => ) : MinValueGen * float -> float
  static member ( => ) : MinValueGen * MinValueGen -> 'a

Full name: Main.Functions.MinValueGen
Multiple items
val int : value:'T -> int (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int

--------------------
type int = int32

Full name: Microsoft.FSharp.Core.int

--------------------
type int<'Measure> = int

Full name: Microsoft.FSharp.Core.int<_>
type Int32 =
  struct
    member CompareTo : value:obj -> int + 1 overload
    member Equals : obj:obj -> bool + 1 overload
    member GetHashCode : unit -> int
    member GetTypeCode : unit -> TypeCode
    member ToString : unit -> string + 3 overloads
    static val MaxValue : int
    static val MinValue : int
    static member Parse : s:string -> int + 3 overloads
    static member TryParse : s:string * result:int -> bool + 1 overload
  end

Full name: System.Int32
field int.MinValue = -2147483648
Multiple items
val int64 : value:'T -> int64 (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.int64

--------------------
type int64 = Int64

Full name: Microsoft.FSharp.Core.int64

--------------------
type int64<'Measure> = int64

Full name: Microsoft.FSharp.Core.int64<_>
type Int64 =
  struct
    member CompareTo : value:obj -> int + 1 overload
    member Equals : obj:obj -> bool + 1 overload
    member GetHashCode : unit -> int
    member GetTypeCode : unit -> TypeCode
    member ToString : unit -> string + 3 overloads
    static val MaxValue : int64
    static val MinValue : int64
    static member Parse : s:string -> int64 + 3 overloads
    static member TryParse : s:string * result:int64 -> bool + 1 overload
  end

Full name: System.Int64
field int64.MinValue = -9223372036854775808L
Multiple items
val float : value:'T -> float (requires member op_Explicit)

Full name: Microsoft.FSharp.Core.Operators.float

--------------------
type float = Double

Full name: Microsoft.FSharp.Core.float

--------------------
type float<'Measure> = float

Full name: Microsoft.FSharp.Core.float<_>
type Double =
  struct
    member CompareTo : value:obj -> int + 1 overload
    member Equals : obj:obj -> bool + 1 overload
    member GetHashCode : unit -> int
    member GetTypeCode : unit -> TypeCode
    member ToString : unit -> string + 3 overloads
    static val MinValue : float
    static val MaxValue : float
    static val Epsilon : float
    static val NegativeInfinity : float
    static val PositiveInfinity : float
    ...
  end

Full name: System.Double
field float.MinValue = -1.79769313486e+308
val failwith : message:string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith
val minValue : unit -> 'a (requires member get_Zero and member ( => ))

Full name: Main.Functions.minValue


 Returns the minimum value for a generic type.
module LanguagePrimitives

from Microsoft.FSharp.Core
val GenericZero<'T (requires member get_Zero)> : 'T (requires member get_Zero)

Full name: Microsoft.FSharp.Core.LanguagePrimitives.GenericZero
Multiple items
union case MaxValueGen.MaxValueGen: MaxValueGen

--------------------
type MaxValueGen =
  | MaxValueGen
  static member ( => ) : MaxValueGen * int -> int
  static member ( => ) : MaxValueGen * int64 -> int64
  static member ( => ) : MaxValueGen * float -> float
  static member ( => ) : MaxValueGen * MaxValueGen -> 'a

Full name: Main.Functions.MaxValueGen
field int.MaxValue = 2147483647
field int64.MaxValue = 9223372036854775807L
field float.MaxValue = 1.79769313486e+308
val maxValue : unit -> 'a (requires member get_Zero and member ( => ))

Full name: Main.Functions.maxValue


 Returns the maximum value for a generic type.
Multiple items
union case HalfPositiveGen.HalfPositiveGen: HalfPositiveGen

--------------------
type HalfPositiveGen =
  | HalfPositiveGen
  static member ( => ) : HalfPositiveGen * x:int -> int
  static member ( => ) : HalfPositiveGen * x:int64 -> int64
  static member ( => ) : HalfPositiveGen * x:float -> float
  static member ( => ) : HalfPositiveGen * HalfPositiveGen -> 'a

Full name: Main.Functions.HalfPositiveGen
val x : int
val x : int64
val x : float
val halfPositive : x:'a -> 'a (requires member ( => ))

Full name: Main.Functions.halfPositive


 Returns half of the positive generic input value.
val x : 'a (requires member ( => ))
val middleOrdered : a:'a -> b:'c -> 'd (requires member ( + ) and member ( - ) and member ( => ))

Full name: Main.Functions.middleOrdered


 Returns the middle point of two ordered input values.
val a : 'a (requires member ( + ) and member ( - ) and member ( => ))
val b : 'c (requires member ( - ) and member ( + ) and member ( => ))
val middle : a:'a -> b:'a -> 'c (requires comparison and member ( + ) and member ( - ) and member ( => ))

Full name: Main.Functions.middle


 Returns the middle point of two input values.
val a : 'a (requires comparison and member ( + ) and member ( - ) and member ( => ))
val b : 'a (requires comparison and member ( + ) and member ( - ) and member ( => ))
type SampleStatistics =
  {N: int;
   Mean: float;
   Variance: float;}
  member MeanStandardError : float
  member StandardDeviation : float

Full name: Main.SampleStatistics
SampleStatistics.N: int
SampleStatistics.Mean: float
SampleStatistics.Variance: float
val s : SampleStatistics
member SampleStatistics.StandardDeviation : float

Full name: Main.SampleStatistics.StandardDeviation
val sqrt : value:'T -> 'U (requires member Sqrt)

Full name: Microsoft.FSharp.Core.Operators.sqrt
member SampleStatistics.MeanStandardError : float

Full name: Main.SampleStatistics.MeanStandardError
type WelchStatistic =
  {T: float;
   DF: int;}

Full name: Main.WelchStatistic
WelchStatistic.T: float
WelchStatistic.DF: int
val sampleStatistics : s:seq<'a> -> seq<SampleStatistics> (requires member op_Explicit)

Full name: Main.StatisticsPerf.sampleStatistics


 Online statistics sequence for a given sample sequence.
val s : seq<'a> (requires member op_Explicit)
val calc : (int * float * float -> float -> int * float * float)
val n : int
val m : float
val s : float
val m' : float
module Seq

from Microsoft.FSharp.Collections
val map : mapping:('T -> 'U) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.map
val scan : folder:('State -> 'T -> 'State) -> state:'State -> source:seq<'T> -> seq<'State>

Full name: Microsoft.FSharp.Collections.Seq.scan
val skip : count:int -> source:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.skip
val scale : f:float -> s:SampleStatistics -> SampleStatistics

Full name: Main.StatisticsPerf.scale


 Scale the statistics for a given underlying random variable change of scale.
val f : float
val singleIteration : ic:int -> s:SampleStatistics -> SampleStatistics

Full name: Main.StatisticsPerf.singleIteration


 Single iteration statistics for a given iteration count and total statistics.
val ic : int
val private tInv : float []

Full name: Main.StatisticsPerf.tInv


 Student's t-distribution inverse for 0.1% confidence level by degrees of freedom.
val welchStatistic : s1:SampleStatistics -> s2:SampleStatistics -> WelchStatistic

Full name: Main.StatisticsPerf.welchStatistic


 Welch's t-test statistic for two given sample statistics.
val s1 : SampleStatistics
val s2 : SampleStatistics
val f1 : float
val f2 : float
val welchTest : w:WelchStatistic -> int

Full name: Main.StatisticsPerf.welchTest


 Welch's t-test for a given Welch statistic to a confidence level of 0.1%.
val w : WelchStatistic
val abs : value:'T -> 'T (requires member Abs)

Full name: Microsoft.FSharp.Core.Operators.abs
type Array =
  member Clone : unit -> obj
  member CopyTo : array:Array * index:int -> unit + 1 overload
  member GetEnumerator : unit -> IEnumerator
  member GetLength : dimension:int -> int
  member GetLongLength : dimension:int -> int64
  member GetLowerBound : dimension:int -> int
  member GetUpperBound : dimension:int -> int
  member GetValue : [<ParamArray>] indices:int[] -> obj + 7 overloads
  member Initialize : unit -> unit
  member IsFixedSize : bool
  ...

Full name: System.Array
val get : array:'T [] -> index:int -> 'T

Full name: Microsoft.FSharp.Collections.Array.get
val min : e1:'T -> e2:'T -> 'T (requires comparison)

Full name: Microsoft.FSharp.Core.Operators.min
val length : array:'T [] -> int

Full name: Microsoft.FSharp.Collections.Array.length
val sign : value:'T -> int (requires member get_Sign)

Full name: Microsoft.FSharp.Core.Operators.sign
module StatisticsPerf

from Main
val private targetIterationCount : metric:(int -> 'a -> 'b) -> metricTarget:'b -> f:'a -> int (requires member ( <<< ) and comparison and member op_Explicit)

Full name: Main.Performance.targetIterationCount


 Find the iteration count to get to at least the metric target.
val metric : (int -> 'a -> 'b) (requires member ( <<< ) and comparison and member op_Explicit)
val metricTarget : 'b (requires member ( <<< ) and comparison and member op_Explicit)
val f : 'a
val find : (int -> int)
val item : 'b (requires member ( <<< ) and comparison and member op_Explicit)
val private measureStatistics : metric:(int -> 'a -> 'b) * metricTarget:'b -> relativeError:float -> f:'a -> SampleStatistics (requires member ( <<< ) and comparison and member op_Explicit and member op_Explicit)

Full name: Main.Performance.measureStatistics


 Create and iterate a statistics sequence for a metric until the given accuracy.
val metric : (int -> 'a -> 'b) (requires member ( <<< ) and comparison and member op_Explicit and member op_Explicit)
val metricTarget : 'b (requires member ( <<< ) and comparison and member op_Explicit and member op_Explicit)
val relativeError : float
val initInfinite : initializer:(int -> 'T) -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.initInfinite
val find : predicate:('T -> bool) -> source:seq<'T> -> 'T

Full name: Microsoft.FSharp.Collections.Seq.find
property SampleStatistics.MeanStandardError: float
val private measureCompare : metric:(int -> (('a -> 'a) -> 'b) -> 'c) * metricTarget:'c -> f1:(('a -> 'a) -> 'b) -> f2:(('a -> 'a) -> 'b) -> int (requires equality and member ( <<< ) and comparison and member op_Explicit and member op_Explicit)

Full name: Main.Performance.measureCompare


 Create and iterate two statistics sequences until the metric means can be compared.
val metric : (int -> (('a -> 'a) -> 'b) -> 'c) (requires equality and member ( <<< ) and comparison and member op_Explicit and member op_Explicit)
val metricTarget : 'c (requires member ( <<< ) and comparison and member op_Explicit and member op_Explicit)
val f1 : (('a -> 'a) -> 'b) (requires equality)
val f2 : (('a -> 'a) -> 'b) (requires equality)
val id : x:'T -> 'T

Full name: Microsoft.FSharp.Core.Operators.id
val stats : ((('a -> 'a) -> 'b) -> seq<SampleStatistics>) (requires equality)
val f : (('a -> 'a) -> 'b) (requires equality)
val map2 : mapping:('T1 -> 'T2 -> 'U) -> source1:seq<'T1> -> source2:seq<'T2> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.map2
val pick : chooser:('T -> 'U option) -> source:seq<'T> -> 'U

Full name: Microsoft.FSharp.Collections.Seq.pick
val maxDF : int
union case Option.Some: Value: 'T -> Option<'T>
union case Option.None: Option<'T>
val c : int
val private measureMetric : startMetric:(unit -> 'a) -> endMetric:('a -> 'b) -> ic:int -> f:((('d -> 'e) -> 'd -> 'e) -> 'f) -> 'c (requires member ( + ) and member get_Zero)

Full name: Main.Performance.measureMetric


 Measure the given function for the iteration count using the start and end metric.
val startMetric : (unit -> 'a)
val endMetric : ('a -> 'b) (requires member ( + ) and member get_Zero)
val f : ((('d -> 'e) -> 'd -> 'e) -> 'f)
type GC =
  static member AddMemoryPressure : bytesAllocated:int64 -> unit
  static member CancelFullGCNotification : unit -> unit
  static member Collect : unit -> unit + 2 overloads
  static member CollectionCount : generation:int -> int
  static member GetGeneration : obj:obj -> int + 1 overload
  static member GetTotalMemory : forceFullCollection:bool -> int64
  static member KeepAlive : obj:obj -> unit
  static member MaxGeneration : int
  static member ReRegisterForFinalize : obj:obj -> unit
  static member RegisterForFullGCNotification : maxGenerationThreshold:int * largeObjectHeapThreshold:int -> unit
  ...

Full name: System.GC
GC.Collect() : unit
GC.Collect(generation: int) : unit
GC.Collect(generation: int, mode: GCCollectionMode) : unit
GC.WaitForPendingFinalizers() : unit
val mutable total : 'c (requires member get_Zero and member ( + ))
val measurer : (('g -> 'h) -> 'g -> 'h)
val toMeasure : ('g -> 'h)
val args : 'g
val s : 'a
val ret : 'h
val m : 'b (requires member ( + ) and member get_Zero)
val loop : (int -> unit)
val i : int
val ignore : value:'T -> unit

Full name: Microsoft.FSharp.Core.Operators.ignore
val private timeMetric : ic:int -> f:((('a -> 'b) -> 'a -> 'b) -> 'c) -> int64

Full name: Main.Performance.timeMetric


 Measure the time metric for the given function and iteration count.
val f : ((('a -> 'b) -> 'a -> 'b) -> 'c)
Multiple items
type Stopwatch =
  new : unit -> Stopwatch
  member Elapsed : TimeSpan
  member ElapsedMilliseconds : int64
  member ElapsedTicks : int64
  member IsRunning : bool
  member Reset : unit -> unit
  member Restart : unit -> unit
  member Start : unit -> unit
  member Stop : unit -> unit
  static val Frequency : int64
  ...

Full name: System.Diagnostics.Stopwatch

--------------------
Stopwatch() : unit
Stopwatch.GetTimestamp() : int64
val t : int64
val private memoryMetric : ic:int -> f:((('a -> 'b) -> 'a -> 'b) -> 'c) -> int64

Full name: Main.Performance.memoryMetric


 Measure the memory metric for the given function and iteration count.
val startMetric : (unit -> int64)
val not : value:bool -> bool

Full name: Microsoft.FSharp.Core.Operators.not
GC.GetTotalMemory(forceFullCollection: bool) : int64
val endMetric : (int64 -> int64)
val s : int64
val private garbageMetric : ic:int -> f:((('a -> 'b) -> 'a -> 'b) -> 'c) -> int

Full name: Main.Performance.garbageMetric


 Measure the garbage collection metric for the given function and iteration count.
val count : (unit -> int)
GC.CollectionCount(generation: int) : int
val s : int
val private oneMillisecond : int64

Full name: Main.Performance.oneMillisecond


 Measure definitions which are a metric together with a metric target.
field Stopwatch.Frequency
val private timeMeasure : (int -> ((('a -> 'b) -> 'a -> 'b) -> 'c) -> int64) * int64

Full name: Main.Performance.timeMeasure
val private memoryMeasure : (int -> ((('a -> 'b) -> 'a -> 'b) -> 'c) -> int64) * int64

Full name: Main.Performance.memoryMeasure
val private garbageMeasure : (int -> ((('a -> 'b) -> 'a -> 'b) -> 'c) -> int) * int

Full name: Main.Performance.garbageMeasure
val timeStatistics : f:((('a -> 'b) -> 'a -> 'b) -> 'c) -> SampleStatistics

Full name: Main.Performance.timeStatistics


 Time statistics for a given function accurate to a mean standard error of 1%.
val memoryStatistics : f:((('a -> 'b) -> 'a -> 'b) -> 'c) -> SampleStatistics

Full name: Main.Performance.memoryStatistics


 Memory statistics for a given function accurate to a mean standard error of 1%.
val gcCountStatistics : f:((('a -> 'b) -> 'a -> 'b) -> 'c) -> SampleStatistics

Full name: Main.Performance.gcCountStatistics


 GC count statistics for a given function accurate to a mean standard error of 1%.
val timeCompare : f1:((('a -> 'b) -> 'a -> 'b) -> 'c) -> f2:((('a -> 'b) -> 'a -> 'b) -> 'c) -> int (requires equality)

Full name: Main.Performance.timeCompare


 Time comparison for two given functions to a confidence level of 0.1%.
val f1 : ((('a -> 'b) -> 'a -> 'b) -> 'c) (requires equality)
val f2 : ((('a -> 'b) -> 'a -> 'b) -> 'c) (requires equality)
val memoryCompare : f1:((('a -> 'b) -> 'a -> 'b) -> 'c) -> f2:((('a -> 'b) -> 'a -> 'b) -> 'c) -> int (requires equality)

Full name: Main.Performance.memoryCompare


 Memory comparison for two given functions to a confidence level of 0.1%.
val gcCountCompare : f1:((('a -> 'b) -> 'a -> 'b) -> 'c) -> f2:((('a -> 'b) -> 'a -> 'b) -> 'c) -> int (requires equality)

Full name: Main.Performance.gcCountCompare


 GC count comparison for two given functions to a confidence level of 0.1%.
val median3 : a:'a -> b:'a -> c:'a -> 'a (requires comparison)

Full name: Main.Statistics.median3


 Returns the median of three input values.
val a : 'a (requires comparison)
val b : 'a (requires comparison)
val c : 'a (requires comparison)
val minSub : a:'a [] -> lo:int -> hi:int -> 'a (requires comparison)

Full name: Main.Statistics.minSub


 Returns the minimum value of a subsection of an array.
val a : 'a [] (requires comparison)
val lo : int
val hi : int
val mutable v : 'a (requires comparison)
val nv : 'a (requires comparison)
val maxSub : a:'a [] -> lo:int -> hi:int -> 'a (requires comparison)

Full name: Main.Statistics.maxSub


 Returns the maximum value of a subsection of an array.
val min2middleSub : a:'a [] -> lo:int -> hi:int -> 'c (requires comparison and member ( + ) and member ( - ) and member ( => ))

Full name: Main.Statistics.min2middleSub


 Returns the middle point of the two smallest values of a subsection of an array.
val a : 'a [] (requires comparison and member ( + ) and member ( - ) and member ( => ))
val mutable v0 : 'a (requires comparison and member ( + ) and member ( - ) and member ( => ))
val mutable v1 : 'a (requires comparison and member ( + ) and member ( - ) and member ( => ))
val tmp : 'a (requires comparison and member ( + ) and member ( - ) and member ( => ))
val nv : 'a (requires comparison and member ( + ) and member ( - ) and member ( => ))
val max2middleSub : a:'a [] -> lo:int -> hi:int -> 'c (requires comparison and member ( + ) and member ( - ) and member ( => ))

Full name: Main.Statistics.max2middleSub


 Returns the middle point of the two largest values of a subsection of an array.
val swap : a:'a [] -> i:int -> j:int -> unit

Full name: Main.Statistics.swap


 Swap two elements in an array.
val a : 'a []
val j : int
val temp : 'a
val swapIf : a:'a [] -> i:int -> j:int -> unit (requires comparison)

Full name: Main.Statistics.swapIf


 Swap two elements in an array if the first is larger than the second.
val ai : 'a (requires comparison)
val aj : 'a (requires comparison)
val selectInPlace : a:'a [] -> k:int -> middleNext:bool -> 'a (requires comparison and member get_Zero and member ( => ) and member ( => ) and member ( - ) and member ( + ) and member ( => ))

Full name: Main.Statistics.selectInPlace


 Returns the kth smallest element in an array and optionally the middle with
 the next largest. Elements will be reordered in place and cannot be equal
 to the max or min value of the generic type.
val a : 'a [] (requires comparison and member get_Zero and member ( => ) and member ( => ) and member ( - ) and member ( + ) and member ( => ))
val k : int
val middleNext : bool
val outerLoop : (int -> int -> 'a) (requires comparison and member get_Zero and member ( => ) and member ( => ) and member ( - ) and member ( + ) and member ( => ))
val pivot : 'a (requires comparison and member get_Zero and member ( => ) and member ( => ) and member ( - ) and member ( + ) and member ( => ))
val resetLo : bool
val resetHi : bool
val mutable i : int
val mutable j : int
val medianInPlace : a:'a [] -> 'a (requires comparison and member ( + ) and member ( - ) and member get_Zero and member ( => ) and member ( => ) and member ( => ))

Full name: Main.Statistics.medianInPlace


 Returns the median of an array. Elements will be reordered in place and
 cannot be equal to the max or min value of the generic type.
val a : 'a [] (requires comparison and member ( + ) and member ( - ) and member get_Zero and member ( => ) and member ( => ) and member ( => ))
val last : int
val medianAndMAD : a:'a [] -> 'a * 'a (requires comparison and member ( + ) and member get_Zero and member ( => ) and member ( => ) and member Abs and member ( - ) and member ( => ))

Full name: Main.Statistics.medianAndMAD


 Returns the median and median absolute deviation of an array.
 Elements cannot be equal to the max or min value of the generic type.
val a : 'a [] (requires comparison and member ( + ) and member get_Zero and member ( => ) and member ( => ) and member Abs and member ( - ) and member ( => ))
val copy : array:'T [] -> 'T []

Full name: Microsoft.FSharp.Collections.Array.copy
val median : 'a (requires comparison and member ( + ) and member get_Zero and member ( => ) and member ( => ) and member Abs and member ( - ) and member ( => ))
module StatisticsTests

from Main
val medianQuickSelect : a:float [] -> 'a

Full name: Main.StatisticsTests.medianQuickSelect
val a : float []
namespace System.Numerics
module Statistics

from Main
val medianFullSort : a:float [] -> float

Full name: Main.StatisticsTests.medianFullSort
val sortInPlace : array:'T [] -> unit (requires comparison)

Full name: Microsoft.FSharp.Collections.Array.sortInPlace
val l : int
val y : float
val MedianProp : x:int -> xs:int list -> bool

Full name: Main.StatisticsTests.MedianProp
val xs : int list
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
val l : float list
Multiple items
module List

from Microsoft.FSharp.Collections

--------------------
type List<'T> =
  | ( [] )
  | ( :: ) of Head: 'T * Tail: 'T list
  interface IEnumerable
  interface IEnumerable<'T>
  member GetSlice : startIndex:int option * endIndex:int option -> 'T list
  member Head : 'T
  member IsEmpty : bool
  member Item : index:int -> 'T with get
  member Length : int
  member Tail : 'T list
  static member Cons : head:'T * tail:'T list -> 'T list
  static member Empty : 'T list

Full name: Microsoft.FSharp.Collections.List<_>
val map : mapping:('T -> 'U) -> list:'T list -> 'U list

Full name: Microsoft.FSharp.Collections.List.map
val m1 : float
val toArray : list:'T list -> 'T []

Full name: Microsoft.FSharp.Collections.List.toArray
val m2 : float
type Duplication =
  | Low
  | Medium
  | High
  override ToString : unit -> string
  member ToInt : int

Full name: Main.StatisticsTests.Duplication
union case Duplication.Low: Duplication
union case Duplication.Medium: Duplication
union case Duplication.High: Duplication
val i : Duplication
member Duplication.ToInt : int

Full name: Main.StatisticsTests.Duplication.ToInt
override Duplication.ToString : unit -> string

Full name: Main.StatisticsTests.Duplication.ToString
type Sorted =
  | No
  | Part
  | Yes
  override ToString : unit -> string

Full name: Main.StatisticsTests.Sorted
union case Sorted.No: Sorted
union case Sorted.Part: Sorted
union case Sorted.Yes: Sorted
val i : Sorted
override Sorted.ToString : unit -> string

Full name: Main.StatisticsTests.Sorted.ToString
Multiple items
val list : duplication:Duplication -> sorted:Sorted -> seq<float list>

Full name: Main.StatisticsTests.list

--------------------
type 'T list = List<'T>

Full name: Microsoft.FSharp.Collections.list<_>
val duplication : Duplication
val sorted : Sorted
val r : Random
Multiple items
type Random =
  new : unit -> Random + 1 overload
  member Next : unit -> int + 2 overloads
  member NextBytes : buffer:byte[] -> unit
  member NextDouble : unit -> float

Full name: System.Random

--------------------
Random() : unit
Random(Seed: int) : unit
val next : (unit -> float)
Random.Next() : int
Random.Next(maxValue: int) : int
Random.Next(minValue: int, maxValue: int) : int
property Duplication.ToInt: int
val init : count:int -> initializer:(int -> 'T) -> seq<'T>

Full name: Microsoft.FSharp.Collections.Seq.init
val init : length:int -> initializer:(int -> 'T) -> 'T list

Full name: Microsoft.FSharp.Collections.List.init
val sort : list:'T list -> 'T list (requires comparison)

Full name: Microsoft.FSharp.Collections.List.sort
val len : int
val iter : action:('T -> unit) -> source:seq<'T> -> unit

Full name: Microsoft.FSharp.Collections.Seq.iter
val ofArray : array:'T [] -> 'T list

Full name: Microsoft.FSharp.Collections.List.ofArray
val MedianPerfTest : unit -> unit

Full name: Main.StatisticsTests.MedianPerfTest
val printfn : format:Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn
val collect : mapping:('T -> #seq<'U>) -> source:seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.collect
val d : Duplication
val s : Sorted
val lists : seq<float list>
val timeStatistics : ((float [] -> 'a) -> SampleStatistics)
val f : (float [] -> 'a)
module Performance

from Main
val timer : ((float [] -> 'a) -> float [] -> 'a)
val p1 : SampleStatistics
val p2 : SampleStatistics
val p3 : SampleStatistics
Multiple items
val string : value:'T -> string

Full name: Microsoft.FSharp.Core.Operators.string

--------------------
type string = String

Full name: Microsoft.FSharp.Core.string