SortedDictionary vs Dictionary vs Map vs Array

gistfile1.fs

#time

open System.Collections.Generic

// create the data to work with ahead of time to reduce the amount 
// of variance to the actual time taken by each
let capacity = 1000000
let items = [1..capacity]
let kvp = items |> List.map (fun i -> i , i)

(* ADD ITEMS *)
// create an empty SortedDictionay and add the items iteratively
let sortedDict = new SortedDictionary<int, int>()
items |> List.iter (fun i -> sortedDict.Add(i, i))

// create an empty Dictionary with enough capacity to hold the
// entire data set before adding the items iteratively
let dictWithCapacity = new Dictionary<int, int>(capacity)
items |> List.iter (fun i -> dictWithCapacity.Add(i, i))

// create an empty Dictionary and add the items iteratively
let dict = new Dictionary<int, int>()
items |> List.iter (fun i -> dict.Add(i, i))

// create an empty map and add the items iteratively
let mutable map = Map.empty<int, int>
items |> List.iter (fun i -> map <- map.Add(i, i))

// create a map from the list
let map2 = kvp |> Map.ofList

// create an empty array and then populate it
let arr : (int * int) array = Array.zeroCreate capacity
items |> List.iter (fun i -> arr.[i-1] <- (i, i))

// create an array from the list
items |> List.toArray

(* ITERATING *)
sortedDict |> Seq.iter (fun _ -> ())

dict |> Seq.iter (fun _ -> ())

map |> Seq.iter (fun _ -> ())

arr |> Seq.iter (fun _ -> ())