OCaml中的簡單非最佳unionfind

我爲union find算法編寫了OCaml程序。我寫的這個算法不是最優的，也是最簡單的版本。OCaml中的簡單非最佳unionfind

我把我的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好？

有沒有辦法避免使用數組？

最後，

總體而言，這是一段代碼不夠好？

什麼都可以改進？

P.S.我沒有使用OCaml的面向對象的一點，因爲我還沒有學到這一點。

來源

2013-02-07 Jackson Tale

我認爲http://codereview.stackexchange.com/會更適合這類問題。 – jrouquie

啊，對不起，不知道那個網站。 –

有太多的stackexchange網站，沒有人應該被期望成爲這個網站的臨時用戶，並保持跟蹤，或有任何願意註冊每一個（雖然儘可能微不足道）。他在這個網站上有很多問題，我不會擔心太多的傑克遜。 – nlucaroni

幾個風格要點：

不知道爲什麼unionfy需要id_ary作爲參數，因爲它保持其恆定整個

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

print_string "...\n"相當於print_endline "..."

下面的定義可以用雙關語被清理到 let union u p q =到：以便有以u沒有多餘的引用let union {id_ary; _} p q。爲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-07 20:07:22 rgrinberg

爲你的嘮叨的事情，如果我不ref'u .'，'u'裏面的'id_ary'不會改變，對嗎？我需要改變它，就好像「多重聯合」一樣。 –

'id_ary'是一個數組，因此它是可變的。不明白你的意思。如果你問你是否需要更改代碼，那麼不會，因爲名稱是相同的。 – rgrinberg

我的意思是，如果我使用'{id_ary; _}'而不是'u.id_ary'，這兩個id_ary是否完全一樣？我認爲OCaml會複製id_ary。 –

的代碼一些評論：

你似乎沒有使用sz_ary任何東西。
您的代碼遍歷整個數組，用於每個聯合操作。這對於標準（Tarjan）聯合查找來說是不正確的。對於線性數量的聯合操作，您的代碼會生成二次解。維基百科有標準算法：Disjoint-set Data Structure。

要回答你的第二個問題：據我所知，工會的發現是對其中有沒有已知的功能（不可變的）具有相同的複雜性是最好的解決方案必須解決方案的算法之一。由於數組只是一個從整數到值的映射，因此可以使用映射將任何基於數組的解決方案轉換爲不可變的解決方案。據我已經能夠確定，這將匹配漸近複雜性中最好的已知解決方案;即它會增加一個額外的log n因子。當然，也會有一個可能足以成爲問題的恆定因素。

我已經在OCaml中實現了union-find幾次，並且我一直選擇使用可變數據。但是，我沒有使用數組。我的基本對象有一個記錄類型，我在每個記錄中使用一個可變字段來指向它的父對象。要進行路徑壓縮，可以修改父指針以指向樹的當前根。

來源

2013-02-08 00:14:45

OCaml中的簡單非最佳unionfind

回答

相關問題