arrays - 在 ocaml 中展平数组的最快方法是什么？

Question

在 ocaml 中压平数组的最快方法是什么？请注意，我指的是数组，而不是列表。

我想以尽可能低的系数线性执行此操作。

Answer 1

OCaml 标准库相当不足，需要您从头开始实现很多东西。这就是为什么我们有像 Batteries 和 Core 这样的扩展库。我建议您使用它们，这样您就不会遇到此类问题。

仍然，为了完整起见，让我们尝试实现我们自己的解决方案，然后将其与建议的 fun xxs -> Array.(concat (to_list xxs)) 进行比较解决方案。

在实现中我们遇到了一些小问题。首先，为了构造一个数组，我们需要为每个单元格提供一个值。我们不能只创建一个未初始化的数组，这会破坏类型系统。我们当然可以使用 Obj模块，但这相当丑陋。另一个问题是输入数组可能为空，因此我们需要以某种方式处理这种情况。当然，我们可以只提出一个异常(exception)，但我更愿意让我的功能完整。虽然并不明显，如何创建一个空数组，但这并非不可能:

 let empty () = Array.init 0 (fun _ -> assert false)

这是一个将创建一个空的多态数组的函数。我们使用底值(每个类型的居民的值)，表示为 assert false .这是类型安全且整洁的。

接下来是如何创建一个没有默认值的数组。我们可以编写一个非常复杂的代码，它将使用 Array.init并翻译i j 的索引n'th 的第 ' 个索引大批。但这是乏味的、容易出错的，而且效率很低。另一种方法是在输入数组中找到第一个值并将其用作默认值。另一个问题来了，因为在标准库中我们没有 Array.find功能。原文如此。遗憾的是，在 21 世纪，我们需要写一个 Array.find功能，但这就是生活的方式。再次使用 Core (或 Core_kernel )图书馆或 Batteries . OCaml 社区中有许多优秀的库，可通过 opam 获得。 .但回到我们的问题，因为我们没有查找功能，我们将使用我们自己的自定义解决方案。我们可以使用 fold_left , 但它会遍历整个数组，尽管我们只需要找到第一个元素。有一个解决方案，我们可以使用异常，用于非本地导出。不要害怕，这在 OCaml 中是惯用的。在 OCaml 中引发和捕获异常也非常快。除了非本地导出，我们还需要发送我们找到的值。我们可以使用引用细胞作为沟通 channel 。但这比较丑陋，我们将使用异常本身来为我们承担值(value)。由于我们事先不知道元素的类型，因此我们将使用 OCaml 语言的两个现代特性。本地抽象类型和本地模块。那么让我们开始实现吧:

let array_concat (type t) xxs =
  let module Search = struct exception Done of t end in
  try
    Array.iter (fun xs ->
        if Array.length xs <> 0
        then raise_notrace (Search.Done xs.(0))) xxs;
    empty ()
  with Search.Done default ->
    let len =
      Array.fold_left (fun n xs -> n + Array.length xs) 0 xxs in
    let ys = Array.make len default in
    let _ : int = Array.fold_left (fun i xs ->
        let len = Array.length xs in
        Array.blit xs 0 ys i len;
        i+len) 0 xxs in
    ys

现在，有趣的部分。对标!让我们使用建议的解决方案进行比较:

let default_concat xxs = Array.concat (Array.to_list xxs)

这是我们的测试工具:

let random_array =
  Random.init 42;
  let max = 100000 in
  Array.init 1000 (fun _ -> Array.init (Random.int max) (fun i -> i))


let test name f =
  Gc.major ();
  let t0 = Sys.time () in
  let xs = f random_array in
  let t1 = Sys.time () in
  let n = Array.length xs in
  printf "%s: %g sec (%d bytes)\n%!" name (t1 -. t0) n

let () =
  test "custom "  array_concat;
  test "default" default_concat

然后...结果:

$ ./array_concat.native
custom : 0.38 sec (49203647 bytes)
default: 0.20 sec (49203647 bytes)

顺便说一句，他们并不让我感到惊讶。我们的解决方案比标准库慢两倍。这个故事的寓意是:

1. 总是在优化之前进行基准测试
2. 使用扩展库(核心、电池、容器……)

更新(使用 Base 连接数组)

有了基础库，我们可以很容易的拼接数组，

let concat_base = Array.concat_map ~f:ident

这是我们的基准:

./example.native 
custom : 0.524071 sec (49203647 bytes)
default: 0.308085 sec (49203647 bytes)
base   : 0.201688 sec (49203647 bytes)

所以现在基本实现是最快和最小的。