1

union find我为算法编写了一个 OCaml 程序。我写的这个算法不是最优的，是最简单的版本。

我把我的 OCaml 代码放在这里是因为我不确定这段代码是否足够好（尽管有算法本身），尽管这段代码可以毫无错误地运行。

这是我开始学习 OCaml 后第一次写一个完整的工作的东西，所以请通过复习帮助我。

有用的建议将帮助我提高我的 OCaml 技能。谢谢

type union_find = {id_ary : int array; sz_ary : int array};;

let create_union n = {id_ary = Array.init n (fun i -> i); 
                  sz_ary = Array.init n (fun i -> 1)};;

let union u p q = 
  let rec unionfy id_ary i = 
    let vp = id_ary.(p) in
    let vq = id_ary.(q) in
    if i < Array.length id_ary then begin 
      if i != q && id_ary.(i) = vp then id_ary.(i) <- vq;
      unionfy id_ary (i + 1)
    end 
    else print_string "end of union\n"
  in
  unionfy u.id_ary 0;;

let is_connected u p q = u.id_ary.(p) = u.id_ary.(q);;

首先，

我是否正确创建union（如union find）的数据结构？

我应该在里面包含两个数组还是有更好的方法？

第二，

我array在这段代码中使用，但是这array不是mutable很好fp吗？

有没有办法避免使用数组？

最后，

总的来说，这段代码足够好吗？

有什么可以改进的吗？

PS我还没有使用OCaml的面向对象位，因为我还没有学会那部分。

4

2 回答 2

5

对代码的一些评论：

  • 您似乎没有将 sz_ary 用于任何事情。

  • 您的代码为每个联合操作遍历整个数组。这对于标准（Tarjan）联合查找是不正确的。对于线性数量的联合操作，您的代码会产生二次解。维基百科有标准算法：不相交集数据结构。

回答你的第二个问题：据我所知， union-find 是一种算法，没有已知的功能（不可变）解决方案与最佳命令式解决方案具有相同的复杂性。由于数组只是从整数到值的映射，因此您始终可以使用映射将任何基于数组的解决方案转换为不可变的解决方案。据我所知，这将与渐近复杂性中最著名的解决方案相匹配；即，它会增加一个额外的 log n 因子。当然，还有一个常数因素可能大到足以成为问题。

I've implemented union-find a few times in OCaml, and I've always chosen to do it using mutable data. However, I haven't used arrays. I have a record type for my basic objects, and I use a mutable field in each record to point to its parent object. To do path compression, you modify the parent pointer to point to the current root of the tree.

于 2013-02-08T00:14:45.797 回答
2

几个风格点：

不知道为什么unionfy将 id_ary 作为参数，因为它始终保持不变

不要Array.init与常量函数一起使用。只需使用Array.make.

print_string "...\n"相当于print_endline "..."

可以使用双关语来清理以下定义 let union u p q =to:let union {id_ary; _} p q以便没有对u.

同样的双关语let is_connected u p q = u.id_ary.(p) = u.id_ary.(q);;

这可能是个人选择，但我会摆脱：

let vp = id_ary.(p) in
let vq = id_ary.(q) in

或者至少将它们推到递归定义之上，以便清楚它们是恒定的。

编辑：更正版本

let union {id_ary;_} p q = 
    let (vp, vq) = (id_ary.(p), id_ary.(q)) in
    let rec unionfy i = 
        if i < Array.length id_ary then begin 
            if i != q && id_ary.(i) = vp then id_ary.(i) <- vq;
            unionfy (i + 1)
        end else print_endline "end of union"
    in unionfy 0;;
于 2013-02-07T20:07:22.453 回答