Skip to content

Instantly share code, notes, and snippets.

@lindig
Last active October 13, 2016 21:18
Show Gist options
  • Save lindig/f7f42b5f3d2b2e73557e1898d8d22cdd to your computer and use it in GitHub Desktop.
Save lindig/f7f42b5f3d2b2e73557e1898d8d22cdd to your computer and use it in GitHub Desktop.
(*
* ocamlbuild -pkg unix assoc_timing.native
*
* When visiting all keys in an association list, when does it
* make sense to build a map first? According to this,
* building the map is amortised for list longer than 20 to 30
* elements.
*)
module Int = struct
type t = int
let compare (x:int) (y:int) = compare x y
end
module IntMap = Map.Make(Int)
let seq n =
let rec loop acc = function
| 0 -> acc
| n -> loop (n::acc) (n-1)
in
loop [] n
let data n =
seq n
|> List.map (fun n -> (n, Random.int n))
|> List.sort (fun (_,y1) (_,y2) -> compare y1 y2)
let map_of pairs =
let add map (k,v) = IntMap.add k v map in
List.fold_left add IntMap.empty pairs
let elapsed f =
let before = Unix.gettimeofday () in
let () = f () |> ignore in
let after = Unix.gettimeofday () in
after -. before
let rec repeat n f = match n with
| 0 -> ()
| n -> f (); repeat (n-1) f
let visit keys data =
List.iter (fun key -> List.assoc key data |> ignore) keys
let visit' keys data =
let map = map_of data in
List.iter (fun key -> IntMap.find key map |> ignore) keys
let run n =
let keys = seq n in
let assoc = data n in
let timed f =
elapsed (fun () -> repeat 10000 @@ fun () -> f keys assoc) in
let t = timed visit in
let t' = timed visit' in
( Printf.printf "%5fs List.assoc\n" t
; Printf.printf "%5fs Map.find\n" t'
)
let main () =
let argv = Array.to_list Sys.argv in
let this = Sys.executable_name in
let () = Random.init 0 in
match argv with
|[_;n] -> run (int_of_string n)
| _ -> Printf.eprintf "usage: %s n\n" this
let () = if !Sys.interactive then () else main ()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment