OCaml中简单的非最佳unionfind(Simple non-optimal unionfind

我写了一个程序ocaml的union find算法。这个算法我写的是不是最佳的，是最简单的版本。

我把我的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的面向对象位呢，因为我还没有学会的那部分。

Answer 1:

几个风格要点：

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

不使用Array.init以恒定的功能。只需使用Array.make 。

print_string "...\n"等同于print_endline "..."

下面的定义可以被清理以双关于let union upq =于： let union {id_ary; _} pq let union {id_ary; _} pq ，以便有没有多余的引用u 。

对于相同的双关特技let is_connected upq = 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;;

Answer 2:

在代码中的一些评论：

你似乎没有使用sz_ary任何东西。
通过整个阵列的每个联盟操作你的代码循环。这是不正确的标准（的Tarjan）的合并 - 查找。对于联合运营的线性数你的代码产生的二次方程式解答。维基百科有标准算法：并查集。

要回答你的第二个问题：据我所知，工会发现是对其中有没有已知的功能（不可变的）具有相同的复杂性是最好的解决方案必须解决方案的算法之一。由于数组是简单地从一个整数地图值，你总是可以翻译任何基于阵列的解决方案将使用地图的不可变的。据我已经能够确定，这将匹配渐近复杂性的最佳已知的解决方案; 也就是说，它会增加日志n的额外因素。当然，也有可能是大到足以成为一个问题一个常数因子。

我实现了OCaml中工会找了几次，我一直选择使用可变数据来做到这一点。不过，我没有使用数组。我有一个记录类型为我的基本对象，我用一个可变场中的每个记录指向其父对象。要做到路径压缩，修改父指针指向树的当前根。

文章来源: Simple non-optimal unionfind in OCaml