ocaml - 为什么 Array.map 比尾递归映射(相当)快？

Question

我这样写 map_tail 的尾递归版本:

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

然后是一个基于数组的 map_by_array:

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

---

这是基准代码

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)

---

我发现基于数组的 map 速度更快，这让我有点吃惊。

在map_tail中，它遍历列表两次，而map_by_array遍历列表三次，为什么还是更快？

Answer 1

这可能取决于列表的大小。

在大小为 N 的长列表上，map_tail 将进行 2*N 分配(映射期间为 N，然后为 List.rev)，而 map_by_array 将执行 N+2 分配(1 个用于 Array.of_list，1 个用于 Array.map 和 N for Array.to_list，实际上，也可以优化为只进行一次分配)。

由于分配可能是此代码中最昂贵的操作，因此这种差异应该可以解释性能差异。