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正しく作成していますか?

内部に2つの配列を含める必要がありますか、それとももっと良い方法がありますか?

2番、

arrayこのコードで使用していますarrayが、どちらが適切mutableではないfpでしょうか?

配列の使用を避ける方法はありますか?

ついに、

全体として、このコードは十分でしょうか?

何か改善できますか？

PS 私はまだ OCaml のオブジェクト指向ビットを使用していません。

4

2 に答える 2

5

コードに関するいくつかのコメント:

  • sz_ary を何にも使用していないようです。

  • コードは、ユニオン操作ごとに配列全体を反復処理します。これは、標準 (Tarjan) の共用体検索では正しくありません。ユニオン演算の線形数の場合、コードは二次解を生成します。ウィキペディアには、標準アルゴリズムDisjoint-set Data Structureがあります。

2 番目の質問に答えるには: 私が知る限り、union-find は、最適な命令型ソリューションと同じ複雑さを持つ既知の関数 (不変) ソリューションがないアルゴリズムの 1 つです。配列は単に整数から値へのマップであるため、マップを使用して配列ベースのソリューションを不変のソリューションにいつでも変換できます。私が判断できる限り、これは漸近的な複雑さで最もよく知られているソリューションと一致します。つまり、log n の余分な要素が追加されます。もちろん、問題になるのに十分な大きさの定数要因もあります。

私は OCaml で union-find を数回実装しましたが、常に変更可能なデータを使用することを選択してきました。ただし、配列は使用していません。基本オブジェクトのレコード タイプがあり、各レコードで変更可能なフィールドを使用して、その親オブジェクトをポイントします。パス圧縮を行うには、ツリーの現在のルートを指すように親ポインターを変更します。

于 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 に答える