2

我正在为二维数组编写基本函数。有两种写“set”函数的方法。第一个包括制作矩阵的副本，然后对其进行修改：

let copy_matrix (m: 'a array array): 'a array array =
  let l = Array.length m in
    if l = 0 then m else
      let result = Array.make l m.(0) in
        for i = 0 to l - 1 do
           result.(i) <- Array.copy m.(i)
        done;
        result

let set_copy (m: 'a array array) (r: int) (c: int) (v: 'a): 'a array array =
  let m' = copy_matrix m in
  m'.(r).(c) <- v;
  m'

第二个只是直接在矩阵上修改：

let set (m: 'a array array) (r: int) (c:int) (v: 'a) : unit =
  m.(r).(c) <- v

我认为如果它是在 Java 中，那么显然第二个函数比第一个函数更快、更经济。但是，有人（我忘记了）告诉我，1）OCaml 的内存管理非常聪明，set_copy不会花费太多，2）有一些原因（我忘记了）它set_copy比set.

谁能告诉我这是不是真的？

4

2 回答 2

5

如果您需要持久数组（您需要保留所有版本以用于回溯等），则复制版本当然要好得多，但它会很慢。我们在这篇 StackOverflow 帖子中讨论了持久化数组数据结构，如果你想要持久化，你应该考虑使用它们而不是普通数组。通过使用持久数组的持久数组来处理矩阵可能会工作得很好。当然，您也可以使用带有类型键的Map(int * int)作为起点（但访问成本不可忽略）。

如果您不需要持久性（您永远不需要保留“旧”数组），那么避免复制并保留标准数据类型会更好。

此外，您可以实现matrix_copy为

let matrix_copy m = Array.map Array.copy m
于 2013-05-10T16:58:13.297 回答
3

我不认为有任何内存管理魔法可以覆盖每次您想要更改一个值时复制整个数组。

使用不可变数据有很好的理由，这些数据适用于数组以及其他所有内容。但是除非数组很小，否则您显示的复制代码将产生相当大的成本。

还有其他方式来表示不需要太多复制的数组（例如，作为差异列表或树）。但当然，他们也有自己的问题。

于 2013-05-10T16:50:49.350 回答