Re: [Caml-list] Priority queues, reloaded

Re: [Caml-list] Priority queues, reloaded

[james woodyatt]

"Jon Harrop" <jon@ffconsultancy.com> asks about heaps and priority queues in Ocaml:
> 
> Anyone got this in OCaml?

I released this years ago.  It's stable, meaning I use it all the time, and I never touch it.

   <https://bitbucket.org/jhw/oni>

From the README in the Cf library:

>> Highlighted features include:
>> 
>> - Functional streams and stream processors (extended).
>> - Functional bootstrapped skew-binomial heap.
     *******************************************
>> - Functional red-black binary tree (associative array).
>> - Functional sets based on red-black binary tree.
>> - Functional real-time catenable deque.
>> - Functional LL(x) parsing using state-exception monad.
>> - Functional lazy deterministic finite automaton (DFA).
>> - Functional lexical analyzer (using lazy DFA and monadic parser).
>> - Functional substring list manipulation (message buffer chains).
>> - Gregorian calendar date manipulation.
>> - Standard time manipulation.
>> - System time in Temps Atomique International (TAI).
>> - Unicode transcoding.
>> - Universal resource identifier (URI) manipulation.
>> - Extended socket interface (supports more options, and UDP w/multicast).
>> - I/O event multiplexing (with Unix.select).
>> - Functional XML stream parsing and generation
>> - Functional MIME stream parsing and generation

Among other treasures, it has priority queues built with the bootstrapped skew-binomial heaps.

  <https://bitbucket.org/jhw/oni/src/ef09a44a61ea/cf/cf_pqueue.mli>
  <https://bitbucket.org/jhw/oni/src/ef09a44a61ea/cf/cf_sbheap.mli>

Nobody knows about my Oni project because I rarely put any effort into promoting it, but its Cf library is an excellent alternative to the OCaml standard library in many ways.  There is a GODI package for it, of course, but the OCaml With Batteries people settled on a more popular alternative (and who can blame them) so again nobody knows about it.  Nevertheless, if you need the complete array of functional data structures in OCaml, you should look at the Cf library I wrote.  It's pretty good.


—
j h woodyatt <jhw@conjury.org>
http://jhw.dreamwidth.org/

Re: [Caml-list] Priority queues, reloaded

[james woodyatt]

On Jul 9, 2011, at 11:52 , Anil Madhavapeddy wrote:
> 
> That's awesome; I didn't know it existed! 

The whole project is my original work and released with a 2-clause BSD-style license, so Knock Yourself Out.


—
j h woodyatt <jhw@conjury.org>
http://jhw.dreamwidth.org/

RE: [Caml-list] Priority queues, reloaded

[Jon Harrop]

Jean-Christophe Filliâtre wrote:
> Hum... You forgot the 13 lines for function app :-) You must admit that
all
> together it's quite a lot of code (37 lines).

Ugh, yeah.

> The code for removal in AVLs is shorter (19 lines) and follows a simpler
logic
> (based on min_elt and remove_min_elt).

Point taken. :-)

Cheers,
Jon.

RE: [Caml-list] Priority queues, reloaded

[Jon Harrop]

Radu Grigore wrote:
> With a time limit of three hours this is what I'd do. In a real program,
I'd
> probably go for binomial heaps if imperative is OK, or maxiphobic heaps if
> persistence is important.

FWIW, I found that Okasaki's binomial heaps are among the slowest. Pairing
heaps were the fastest overall, closely followed by leftist heaps in OCaml.
If elements are inserted in order then the leftist heap is ~3x slower than a
pairing heap in OCaml and ~5x slower in F#.

Cheers,
Jon.

Re: [Caml-list] Priority queues, reloaded

[Jean-Christophe Filliâtre]

Le 09/07/2011 11:02, Jon Harrop a écrit :
> Jean-Christophe Filliâtre wrote:
>> Wow, that's impressive! But I guess you didn't need to implement the
> remove
>> operation on red-black trees :-) That's a real pain.
>
> Is Kahrs' so bad:

Hum... You forgot the 13 lines for function app :-)
You must admit that all together it's quite a lot of code (37 lines).

The code for removal in AVLs is shorter (19 lines) and follows a simpler 
logic (based on min_elt and remove_min_elt).

-- 
Jean-Christophe

RE: [Caml-list] Priority queues, reloaded

[Jon Harrop]

Andrew wrote:
> Since the previous discussion regarding priority queues pretty much
concluded
> that they weren't available in OCaml, could you point to the most compact
> implementation that you know of? I'm very likely to have to recode my own
> implementation in a time-restricted setting, so I'd love to hear about
efficient-
> yet-easy/fast-to-implement options.

Skew heap from Okasaki translated to OCaml:

    module SkewHeap(Elt: Set.OrderedType) = struct
      type t = E | T of Elt.t * t * t

      let empty = E
        
      let is_empty = function E -> true | _ -> false
      
      let rec merge t1 t2 =
        match t1, t2 with
        | E, t | t, E -> t
        | T(x, l1, r1), T(y, l2, r2) ->
            let c = Elt.compare x y in
            if c<=0 then T(x, merge t2 r1, l1) else T(y, merge t1 r2, l2)
       
      let insert x h = merge (T(x, E, E)) h
        
      let min = function
        | E -> None
        | T(x, l, r) -> Some(x, merge l r)
    end;;

Cheers,
Jon.

RE: [Caml-list] Priority queues, reloaded

[Jon Harrop]

Jean-Christophe Filliâtre wrote:
> Wow, that's impressive! But I guess you didn't need to implement the
remove
> operation on red-black trees :-) That's a real pain.

Is Kahrs' so bad:

delete :: Ord a => a -> RB a -> RB a
delete x t =
	case del t of {T _ a y b -> T B a y b; _ -> E}
	where
	del E = E
	del (T _ a y b)
	    | x<y = delformLeft a y b
	    | x>y = delformRight a y b
            | otherwise = app a b
	delformLeft a@(T B _ _ _) y b = balleft (del a) y b
	delformLeft a y b = T R (del a) y b
	delformRight a y b@(T B _ _ _) = balright a y (del b)
	delformRight a y b = T R a y (del b)

balleft :: RB a -> a -> RB a -> RB a
balleft (T R a x b) y c = T R (T B a x b) y c
balleft bl x (T B a y b) = balance bl x (T R a y b)
balleft bl x (T R (T B a y b) z c) = T R (T B bl x a) y (balance b z (sub1
c))

balright :: RB a -> a -> RB a -> RB a
balright a x (T R b y c) = T R a x (T B b y c)
balright (T B a x b) y bl = balance (T R a x b) y bl
balright (T R a x (T B b y c)) z bl = T R (balance (sub1 a) x b) y (T B c z
bl)

sub1 :: RB a -> RB a
sub1 (T B a x b) = T R a x b
sub1 _ = error "invariance violation"

From:

  http://www.cs.kent.ac.uk/people/staff/smk/redblack/Untyped.hs

Anyone got this in OCaml?

Cheers,
Jon.

Re: [Caml-list] Priority queues, reloaded

[Radu Grigore]

I asked:
> How is that [a leftist heap implementation] better than using Set?

and Andrew answered:
> Sets are not heaps ; they can't have multiple copies of the same element.

I asked my question in the context of Andrew's original query:
>  I'd love to hear about efficient-yet-easy/fast-to-implement options.

I meant to ask why would it be easier/faster to implement a leftist heap. Of course, if leftist heaps can do something that an implementation based on Set can't then that would be a problem. Also, if an implementation based on Set would be much slower or memory hungry, that would also be a problem. But it was already explained by others for Dijsktra at least the lack of Decrease-Key is not a problem, and (asymptotic) performance is not an issue.

You now bring up the question of multiplicity, which may be important if you try to, say, find the top K elements in a stream. Again, a Set based implementation is much simpler than the leftist heaps that were posted already. Here it is.

  module S = Set.Make (struct type t = int*int*int let compare = compare end)
  let uid = ref 0
  let push pq p x = incr uid; S.add (p, x, !uid) pq
  let pop pq = let (_,x,_) as k = S.min_elt pq in (x, S.remove k, pq)

With a time limit of three hours this is what I'd do. In a real program, I'd probably go for binomial heaps if imperative is OK, or maxiphobic heaps if persistence is important.

Re: [Caml-list] Priority queues, reloaded

[Andrew]

Radu Grigore wrote:
> On Thursday, June 30, 2011 7:14:56 PM UTC+1, Jean-Christophe Filliâtre wrote:
>> Le 30/06/2011 19:26, Gabriel Scherer a �crit :
>>> Okasaki (eg. in its book "Purely functional data structure", but can
>>> probably be found in papers available on the net) has a "leftist heap"
>>> data structure [...]
>
> Okasaki probably prefers maxiphobic heaps.
>    http://www.eecs.usma.edu/webs/people/okasaki/sigcse05.pdf
>
>> I confirm that leftist heap is probably the best possible choice.
>
> How is that better than using Set?
>
> The only reason I see for implementing your own heap is to save space: Binomial heaps have much better constants. (Smaller space&  cache will likely lead to less time.)
>

Sets are not heaps ; they can't have multiple copies of the same element.

Re: [Caml-list] Priority queues, reloaded

[Radu Grigore]

On Thursday, June 30, 2011 7:14:56 PM UTC+1, Jean-Christophe Filliâtre wrote:
> Le 30/06/2011 19:26, Gabriel Scherer a �crit :
> > Okasaki (eg. in its book "Purely functional data structure", but can
> > probably be found in papers available on the net) has a "leftist heap"
> > data structure [...]

Okasaki probably prefers maxiphobic heaps.
  http://www.eecs.usma.edu/webs/people/okasaki/sigcse05.pdf

> I confirm that leftist heap is probably the best possible choice.

How is that better than using Set?

The only reason I see for implementing your own heap is to save space: Binomial heaps have much better constants. (Smaller space & cache will likely lead to less time.)

Re: [Caml-list] Priority queues, reloaded

[Norman Ramsey]

[-- Attachment #1: Type: text/plain, Size: 435 bytes --]

 > Since the previous discussion regarding priority queues pretty much
 > concluded that they weren't available in OCaml, could you point to the most
 > compact implementation that you know of? 

Attached find a transliteration of some Standard ML code I wrote last
summer.  The SML was tested; the transliteration is not.  But it does
compile, and I've put it under CC BY license: attribution required,
all uses permitted.


Norman



[-- Attachment #2: leftistheap.ml --]
[-- Type: text/plain, Size: 2603 bytes --]

(* Leftist heap (priority queue) by Norman Ramsey *)
(* Copyright 2011, licensed Creative Commons Attribution (BY),
   i.e., attribution required, but all uses permitted 
*)

module type PQUEUE = sig
  type t
  type elem
  val empty  : t
  val insert : elem * t -> t
  val is_empty : t -> bool
  exception Empty
  val deletemin : t -> elem * t  (* raises Empty *)
  val ok : t -> bool (* satisfies invariant *)

  val merges : int ref
end


module MkTreePQ (Elem : sig
                           type t
                           val compare : t * t -> int
                         end) :
  PQUEUE with type elem = Elem.t
=
struct
  type elem = Elem.t
  type height = int
  type t = EMPTY
         | NODE of elem * height * t * t
    (* invariant:
         elem in a node is not greater than the elems in its nonempty children
         left child is at least as high as right child
         height represents true height
     *)

  let le (x1, x2) = Elem.compare (x1, x2) <= 0

  let rec height = function
    | EMPTY -> 0
    | (NODE (_, h, _, _)) -> h

  let merges = ref 0

  let rec merge = function
    | (EMPTY, q) -> q
    | (q, EMPTY) -> q
    | ((NODE (x1, _, l1, r1) as q1), (NODE (x2, _, _, _) as q2)) ->
        if le (x1, x2) then
                let (to_merge, to_stand) =
                  if height l1 > height q2 then (q2, l1) else (l1, q2) in
                let newq1 = merge (r1, to_merge) in
                let newq2 = to_stand in
                let h1 = height newq1 in
                let h2 = height newq2 in
                let h = max h1 h2 + 1 in
                let (l, r) = if h1 > h2 then (newq1, newq2) else (newq2, newq1) in
                let _ = merges := !merges + 1 in
                NODE (x1, h, l, r)
        else
            merge (q2, q1)
            
  let empty = EMPTY
  let rec insert = function
    | (x, EMPTY) -> NODE (x, 1, EMPTY, EMPTY)
    | (x, q) -> merge (insert(x, empty), q)

  let is_empty = function
    | EMPTY -> true
    | (NODE _) -> false

  exception Empty
  let deletemin = function
    | EMPTY -> raise Empty
    | (NODE (x, _, q, q')) -> (x, merge (q, q'))


  let rec ok_h_le h x q =
       (* q satisfies invariant, has height h, each elem at least x *)
    match q with
    | EMPTY -> h = 0
    | NODE (x', h', l, r) ->
                 h = h' && le(x, x') &&
                 (h = height l + 1 || h = height r + 1) &&
                 h > height l && h > height r &&
                 ok_h_le (height l) x' l && ok_h_le (height r) x' r

  let ok = function
    | EMPTY -> true
    | (NODE (x, h, _, _) as q) -> ok_h_le h x q

end

Re: [Caml-list] Priority queues, reloaded

[Wojciech Meyer]

Gabriel Scherer <gabriel.scherer@gmail.com> writes:

> The heap implementation in the OCaml manual, which was pointed to in
> the precedent thread, is quite compact.
>
> Okasaki (eg. in its book "Purely functional data structure", but can
> probably be found in papers available on the net) has a "leftist heap"
> data structure that is also compact and, to my personal taste, easier
> to understand, get familiar with and remember than the usual heap
> implementation -- or more exotic heaps. I was once in a situation
> similar to yours and found that I could implement both his leftist
> heap and the red-black trees in around 15 minutes.

Yes, they are nice, and I'd also recommend reading whole book if you
have some time for a good lecture. The examples are in Standard ML so
it's nearly direct translation to OCaml. I think it was mentioned but
Markus Mottl has implemented Okasaki's data structures in OCaml and made
it available on his website.  One thing to note is that you don't need
really laziness in case of leftitst heaps and red-black trees, as far as
I recall both are amortised.

Cheers;
Wojciech

>
> On Thu, Jun 30, 2011 at 7:13 PM, Andrew <newsgroups.fr@gmail.com>
> wrote:
>
>     Hi all,
>     
>     Since the previous discussion regarding priority queues pretty
>     much concluded that they weren't available in OCaml, could you
>     point to the most compact implementation that you know of? I'm
>     very likely to have to recode my own implementation in a
>     time-restricted setting, so I'd love to hear about
>     efficient-yet-easy/fast-to-implement options.
>     
>     Thanks!
>     
>     -- 
>     Caml-list mailing list.  Subscription management and archives:
>     https://sympa-roc.inria.fr/wws/info/caml-list
>     Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>     Bug reports: http://caml.inria.fr/bin/caml-bugs
>     
>     

Re: [Caml-list] Priority queues, reloaded

[Andrew]

Gabriel Scherer a écrit :
> The heap implementation in the OCaml manual, which was pointed to in the precedent thread, is quite compact.
>
> Okasaki (eg. in its book "Purely functional data structure", but can probably be found in papers available on the net)
> has a "leftist heap" data structure that is also compact and, to my personal taste, easier to understand, get familiar
> with and remember than the usual heap implementation -- or more exotic heaps. I was once in a situation similar to yours
> and found that I could implement both his leftist heap and the red-black trees in around 15 minutes.
>

Did you need red-black trees, though, during the exam?

Re: [Caml-list] Priority queues, reloaded

[Jean-Christophe Filliâtre]

Le 30/06/2011 19:26, Gabriel Scherer a écrit :
> implementation -- or more exotic heaps. I was once in a situation
> similar to yours and found that I could implement both his leftist heap
> and the red-black trees in around 15 minutes.

Wow, that's impressive! But I guess you didn't need to implement the 
remove operation on red-black trees :-) That's a real pain.

Frankly, AVLs are not *that* difficult to implement. And contrary to 
what you can read in some books, it is really difficult to get anything 
faster.

-- 
Jean-Christophe

Re: [Caml-list] Priority queues, reloaded

[Jean-Christophe Filliâtre]

Le 30/06/2011 19:26, Gabriel Scherer a écrit :
> Okasaki (eg. in its book "Purely functional data structure", but can
> probably be found in papers available on the net) has a "leftist heap"
> data structure that is also compact and, to my personal taste, easier to
> understand, get familiar with and remember than the usual heap
> implementation -- or more exotic heaps.

I confirm that leftist heap is probably the best possible choice. Here 
is the code (and if you don't need a functor, it is even shorter):


module Make(X : sig type t val le : t -> t -> bool end) :
sig
   type t
   val empty : t
   val is_empty : t -> bool
   val add : X.t -> t -> t
   exception Empty
   val min : t -> X.t
   val extract_min : t -> X.t * t
   val merge : t -> t -> t
end
=
struct

   type t = E | T of int * X.t * t * t

   exception Empty

   let rank = function E -> 0 | T (r,_,_,_) -> r

   let make x a b =
     let ra = rank a and rb = rank b in
     if ra >= rb then T (rb + 1, x, a, b) else T (ra + 1, x, b, a)

   let empty = E

   let is_empty = function E -> true | T _ -> false

   let rec merge h1 h2 = match h1,h2 with
     | E, h | h, E ->
	h
     | T (_,x,a1,b1), T (_,y,a2,b2) ->
	if X.le x y then make x a1 (merge b1 h2) else make y a2 (merge h1 b2)

   let add x h = merge (T (1, x, E, E)) h

   let min = function E -> raise Empty | T (_,x,_,_) -> x

   let extract_min = function
     | E -> raise Empty
     | T (_,x,a,b) -> x, merge a b

end

-- 
Jean-Christophe

Re: [Caml-list] Priority queues, reloaded

[Daniel de Rauglaudre]

Hi,

Not sure what I am going to say is relevant or not, but in my software
GeneWeb, I implemented a priority queue a very simple way, and where
insertion and get are in constant time.

But... my problem is very specific: my priorities are always integers
between zero and a relatively small integer number (namely 100 or 150)
and will very not likely become larger (and if it does, the queue can
be easily dynamically extended).

In that situation, my priority queue is just an array of that size (let's
say 150) of lists of items.

Insertion queue item =
  let p = item.priority in
  queue.(p) := item :: queue.(p)

Get queue :=
  let p = first_index_with_not_empty_list queue in
  let r = List.hd queue.(p) in
  queue.(p) := List.tl queue.(p);
  r

-- 
Daniel de Rauglaudre
http://pauillac.inria.fr/~ddr/

Re: [Caml-list] Priority queues, reloaded

[Gabriel Scherer]

[-- Attachment #1: Type: text/plain, Size: 1399 bytes --]

The heap implementation in the OCaml manual, which was pointed to in the
precedent thread, is quite compact.

Okasaki (eg. in its book "Purely functional data structure", but can
probably be found in papers available on the net) has a "leftist heap" data
structure that is also compact and, to my personal taste, easier to
understand, get familiar with and remember than the usual heap
implementation -- or more exotic heaps. I was once in a situation similar to
yours and found that I could implement both his leftist heap and the
red-black trees in around 15 minutes.

On Thu, Jun 30, 2011 at 7:13 PM, Andrew <newsgroups.fr@gmail.com> wrote:

> Hi all,
>
> Since the previous discussion regarding priority queues pretty much
> concluded that they weren't available in OCaml, could you point to the most
> compact implementation that you know of? I'm very likely to have to recode
> my own implementation in a time-restricted setting, so I'd love to hear
> about efficient-yet-easy/fast-to-**implement options.
>
> Thanks!
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa-roc.inria.fr/**wws/info/caml-list<https://sympa-roc.inria.fr/wws/info/caml-list>
> Beginner's list: http://groups.yahoo.com/group/**ocaml_beginners<http://groups.yahoo.com/group/ocaml_beginners>
> Bug reports: http://caml.inria.fr/bin/caml-**bugs<http://caml.inria.fr/bin/caml-bugs>
>
>

[-- Attachment #2: Type: text/html, Size: 1876 bytes --]

[Caml-list] Priority queues, reloaded

[Andrew]

Hi all,

Since the previous discussion regarding priority queues pretty much concluded that they weren't available in OCaml, 
could you point to the most compact implementation that you know of? I'm very likely to have to recode my own 
implementation in a time-restricted setting, so I'd love to hear about efficient-yet-easy/fast-to-implement options.

Thanks!