8

我正在尝试派生一个描述结构化值的 Graphviz 文件。这是出于诊断目的，所以我希望我的图表尽可能地反映内存中的实际结构。我正在使用以下内容将值映射到 Graphviz 顶点，以便在值具有两个或多个入站引用时可以重用顶点：

let same = (==)

module StateIdentity : Hashtbl.HashedType = struct
  type t = R.meta_t state
  let hash = Hashtbl.hash
  let equal = same
end

module StateHashtbl = Hashtbl.Make (StateIdentity)

的文档Hashtbl.hash建议它适合在何时StateIdentity.equal = (=)和何时使用，StateIdentity.equal = (==)但我想确保哈希表访问尽可能接近 O(1)，因此宁愿不Hashtbl.hash走一个（在这种情况下可能很大）对象每次查找的图表。

我知道 Ocaml 会移动引用，但是 Ocaml 中是否有用于引用标识的 O(1) 代理？

Ocaml中可变变量哈希表的答案表明不是。

我不愿意将序列号附加到状态，因为这是诊断代码，所以我所做的任何错误都有可能掩盖其他错误。

4

4 回答 4

6

< ... >如果您在 OCaml 的对象类型的意义上使用“对象”一词，那么您可以使用Oo.id来为每个实例获取唯一的整数标识。否则，“是否存在价值同一性的一般代理”的答案是“否”。在这种情况下，我的建议是从 开始Hashtbl.hash，评估它是否符合您的需要，否则设计您自己的散列函数。

您还可以使用Hashtbl.hash_param（参见文档）在散列期间打开值遍历的旋钮。请注意，Hashtbl 代码对相同哈希值的桶使用链表，因此存在大量哈希冲突将触发线性搜索行为。使用冲突桶的二叉搜索树转移到其他实现可能会更好。但是话又说回来，您应该在转向更复杂（并且在“好案例”中表现更差）解决方案之前评估您的情况。

于 2012-10-24T15:49:56.263 回答
5

我发现使用物理相等性进行散列非常棘手。您当然不能使用值的地址之类的东西作为哈希键，因为（正如您所说）事情会被 GC 移动。一旦有了哈希键，只要您的值是可变的，您似乎就可以使用物理相等性进行比较。如果您的值不可变，OCaml 并不能保证 (==) 的含义。实际上，如果 OCaml 编译器或运行时希望（反之亦然），理论上可以将相等 (=) 的不可变对象合并为单个物理对象。

当我处理各种可能性时，我通常会在需要唯一 ID 时将序列号放入我的值中。正如gasche所说，Oo.id如果您的值是实际的OO风格对象，则可以使用。

于 2012-10-24T15:59:54.827 回答
4

像其他人一样，我认为唯一的 ID 是要走的路。

唯一 ID 并不难安全地生成。一种解决方案是使用所谓的私人记录，如下所示。它可以防止模块的用户复制 id 字段：

模块类型 Intf =
签名
  类型 t = 私人 {
    身份证：整数；
    foo : 字符串；
  }

  val create_t : foo: string -> t
结尾

模块 Impl : Intf =
结构
  类型 t = {
    身份证：整数；
    foo : 字符串；
  }

  让 create_id =
    让 n = ref 0 在
    乐趣（）->
      如果 !n = -1 那么
        失败并显示“唯一 ID 不足”
      别的 （
        增加 n;
        !n
      )

  让 create_t ~foo = {
    id = create_id ();
    富
  }
结尾
于 2012-10-24T17:02:13.037 回答
4

对不起，丑陋的黑客，但我前段时间做了类似的事情。

诀窍是确保值在插入表后不会在内存中移动。有两种情况可以在内存中移动值：从次要堆复制到主要堆和主要堆压缩。这意味着当你在表中插入一个值时，它必须在主堆中并且在表的两个操作之间你必须确保没有发生压缩。

可以使用 C 函数 is_young 检查值是否在次堆中，如果是这种情况，可以使用 Gc.minor() 强制将值迁移到主堆。

对于第二个问题，您可以完全停用压缩或在压缩上重建表。禁用它可以使用

Gc.set { Gc.get () with Gc.max_overhead = max_int }

可以通过比较每次访问表时返回的数字来检测是否发生了压缩

( Gc.quick_stat () ).Gc.compactions

请注意，您必须在访问表之前禁用压缩。如果您禁用压缩，您还应该考虑更改分配策略以避免堆的无限碎片。

Gc.set {(Gc.get ()) with Gc.allocation_policy = 1}

如果你想在 OCaml 的旧版本（4.00 之前）中做一些非常丑陋的事情，压缩会在内存中保持相同的顺序，所以你可以实现基于物理地址的集合或映射而不必担心。

于 2012-10-24T21:00:43.220 回答