Why is Array.map (pretty) faster than a tail recursive map?

I write my tail recursive version map_tailas follows:

let map_tail f l =
  let rec map acc = function
    | [] -> List.rev acc
    | hd::tl -> map (f hd :: acc) tl
  in 
  map [] l

And then an array based on map_by_array:

let map_by_array f l =
  Array.of_list l |> Array.map f |> Array.to_list

Here is the reference code

let ran_list n =
  Random.self_init();
  let rec generate acc i =
    if i = n then acc
    else generate (Random.int 5::acc) (i+1)
  in 
  generate [] 0

let _ =
  let l = ran_list 10000000 in
  let f x = x+1 in
  let t1 = Sys.time() in
  let l1 = map_tail f l in
  let t2 = Sys.time() in
  let l2 = map_by_array f l in
  let t3 = Sys.time() in
  Printf.printf "map_tail: %f sec\nmap_by_array: %f sec\n" (t3-.t2) (t2-.t1)

I found that an array-based card is faster, which surprises me a bit.

It crawls the map_taillist twice, and map_by_arraythe crawl list three times, why is it even faster?

+3
source share
1 answer

This probably depends on the size of the list.

N, map_tail 2 * N (N , N List.rev), map_by_array N + 2 (1 Array.of_list, 1 Array.map N Array.to_list, ).

, , , .

+3

All Articles