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.

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 nvv 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 v1v0 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=pivot do j<-j-1 if i=pivot do j<-j-1 else j<-hi i<-i+1 while a.[i]<=pivot do i<-i+1 else if ki 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] [] 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 ) [] 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 ( => ))

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