ocaml - ocaml のプライオリティ キューの関数

Question

優先キューを作成して処理できる ocaml のライブラリはありますか?

この「http://holgerarnold.net/software/ocaml/doc/base/PriorityQueue.Make.html」を確認しましたが、これらのコマンドの使用方法の例はどこにもありません。

Answer 1

Core のヒープについては、少し大きめのチュートリアルを次に示します。

open Core.Std

(* A heap only expects a comparsion function on its elements. Use
  polymorphic compare if you just want something tham makes sense most
  of the time *)

let pq = Heap.create compare

let reverse_pq = Heap.create ~min_size:10 (Fn.flip compare)

(* The optional min size argument is there for optimization purposes. If you
   know that your heap will grow past a certain size you can allocate the array
   of that size in advance to save copying/resizing later on since the heap is
   array based *)

let () = 
  let random_list = List.init 10 ~f:(fun _ -> Random.int 10) in
  (* core wraps values inserted into the heap in the type 'el heap_el
    where 'el is the type of elements in your heap *)
  let heap_el = Heap.push pq (Random.int 10) in
  (* this gives you O(1) existence check in the heap: *)
  let x = Heap.heap_el_mem pq heap_el in (* true in O(1) *)
  let value_in_el = Heap.heap_el_get_el heap_el in
  (* now standard heap stuff, insert a list into a heap *)
  random_list |> List.iter ~f:(Fn.compose ignore (Heap.push pq));
  (* now drain the heap and get a list in sorted order, for reverse
  order you'd us reverse_pq *)
  let sorted_list = 
    let rec loop acc =
      match Heap.pop pq with
      | None -> acc
      | Some e -> loop (e::acc)
    in loop [] in
  printf "Sorted: %s\n" 
    (Sexp.to_string_hum (List.sexp_of_t Int.sexp_of_t sorted_list))

Core を使用することを躊躇しないでください。それはあなたの OCaml をもっと楽しくします。その他の質問はいつでも大歓迎です。

Answer 2

含まれている OCaml Batteries には、BatHeapという名前のモジュールにポリモーフィック プライオリティ キューがあります。空のヒープに要素を追加するだけで使用できます。

Jane Stree Core には、Heapという名前のモジュールに、より洗練された優先キューがあります。

アップデート：

Jane Stree Core のヒープは確かに素晴らしいです。これを説明する 1 つの方法は、ヒープへの 2 つのインターフェイスがあるということです。最初のインターフェイスは、順序付けられた値のコレクションであり、その最小要素は定数時間で特定され、対数時間で削除されます。2 番目のインターフェイスは、ヒープを、順序付けされた値を持つコンテナー (「ヒープ要素」) のコレクションと見なします。これらのコンテナーを明示的に処理する場合は、一部のヒープ操作をより迅速に実行できます。

ヒープ (最初のインターフェース) を使用してリストをソートする非常に単純な例を次に示します。

let heapsort l =
    let heap = Core.Std.Heap.create compare in
    List.iter (fun x -> ignore (Core.Std.Heap.push heap x)) l;
    let rec extract () =
        match Core.Std.Heap.pop heap with
        | None -> []
        | Some x -> x :: extract ()
    in
    extract ()

(このコードはやや人為的です。値をヒープに入れ、それを取り出す方法を示しているだけです。)

このコードを実行する例を次に示します (コアをサポートする OCaml トップレベルで):

# #use "sort.ml";;
val heapsort : 'a list -> 'a list = <fun>
# heapsort [3;1;4;1;5;9];;
- : int list = [1; 1; 3; 4; 5; 9]
#