[Caml-list] Wanted - General Purpose "Glue Logic" Data-Structures

[Caml-list] Wanted - General Purpose "Glue Logic" Data-Structures

[John Gerard Malecki]

I want to broaden my arsenal of data-structures that interface data
between the specific structures that some algorithms require.  Here is
an example of a real problem that I solved too specifically:

  I had an existing reader that produced a list of objects, 'a list.

  I wrote a filter which fractured those items producing 'a list list.

  I then wanted to feed that data to an existing program which builds
  a balanced tree top-down.  It expects 'a list which it then passes
  to a median finder which prefers its input list to be in random
  order.

In the great ocaml tradition this worked just fine and the first time.
(What a great language.)  To really test things I then ran it on
MOADB, the mother of all data bases, a very large but real-world
data-base.

The program broke down in 2 places.  First, List.concat was used to
convert the output of the fracturer from 'a list list to 'a list.  Not
only is List.concat not tail-recursive but @ (Pervasives.append) is
also not tail-recursive.  I modified the fracturer to directly produce
'a list.

Second, the median program has some limitations.  It not only prefers
the input to be randomized but while it runs it too constructs some 'a
list list.  (Why?  This median program returns not just the median but
the set of items lt and gt the median.)  I re-wrote the median program.

I would prefer not to keep re-writing programs and instead have a
better collection intermediate data-structures that I can use to glue
my programs together efficiently and safely.  One can argue that the
median program was already flawed and it was best to re-write it.
Still, it would be nice to have a data-structure which the fracturer
could produce that not only can deal with large data sets but also has
the randomizing property.  Of course I want all this at very little
expense as none of these manipulations are germane to the real problem
at hand.

I considered having the fracturer build a priority queue over random
numbers but all that balancing book-keeping seems expensive.  I guess
what I'm looking for are inexpensive data-structures that have
properties like

   - fast computation of cardinality
 
   - fast addition of single elements
 
   - fast addition of lists of elements
 
   - fast removal of single elements in random order
 
   - not choking on a large data size

Any suggestions?  Does anyone have other useful glue-logic
data-structures which they use?

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Wanted - General Purpose "Glue Logic" Data-Structures

[Brian Hurt]

On Wed, 19 Mar 2003, John Gerard Malecki wrote:

> The program broke down in 2 places.  First, List.concat was used to
> convert the output of the fracturer from 'a list list to 'a list.  Not
> only is List.concat not tail-recursive but @ (Pervasives.append) is
> also not tail-recursive.  I modified the fracturer to directly produce
> 'a list.

I have a tail-recursive version of the entire list library, including 
append, kicking around- I'll send it to you.  That fixes this problem.  
But thank you for proving me right- this *is* a problem :-).

As for producing the tree, I'd recommend using a self-balancing tree- 
perhaps a Red-Black tree (which is surprisingly easy to implement in 
Ocaml.  It's annoying that the standard library's set doesn't *quite* do 
what you need).  Inserting an element should be O(log n), meaning you 
should be able to build the whole tree in O(n * log n).

Hmm.  Alternatively, you might also look at my Priority Search Queue 
implementation.  This probably does more than you need, but that's better 
than doing less than you need :-).  With PSQueue:

>    - fast computation of cardinality

Cardinality is, or should be, O(1) (if all else, I just keep a running 
count of elements in the tree).

>  
>    - fast addition of single elements

PSQueue is O(log n) addition.

>  
>    - fast addition of lists of elements

Adding a list of k elements to a n-element PSQueue is O(k * log n).

>  
>    - fast removal of single elements in random order

PSQueue is O(log n) removal of any element.  Also, finding any given 
element given it's key is O(log n).

>  
>    - not choking on a large data size

PSQueue is not tail recursive, but it only uses O(log n) stack space (it's 
a balanced tree).  I'll send the code on and you can look at it.

Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Wanted - General Purpose "Glue Logic" Data-Structures

[Matthew W. Boyd]

> The program broke down in 2 places.  First, List.concat was used to
> convert the output of the fracturer from 'a list list to 'a list.  Not
> only is List.concat not tail-recursive but @ (Pervasives.append) is
> also not tail-recursive.  I modified the fracturer to directly produce
> 'a list.
> 
> 

This has been brought up many times in the past.  Perhaps this could be
in the List module documentation?

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Wanted - General Purpose "Glue Logic" Data-Structures

[Nicolas Cannasse]

> The program broke down in 2 places.  First, List.concat was used to
> convert the output of the fracturer from 'a list list to 'a list.  Not
> only is List.concat not tail-recursive but @ (Pervasives.append) is
> also not tail-recursive.  I modified the fracturer to directly produce
> 'a list.
[...]
> Any suggestions?  Does anyone have other useful glue-logic
> data-structures which they use?

We're currently running a project called ExtLib (
http://sourceforge.net/projects/ocaml-lib ) than aims at providing thoses
kind of needed tail-safe data structures, and some other useful modules
built together as an additionnal standard library.
Any people interested in helping can join the mailling list.

Nicolas Cannasse

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

[Caml-list] Re: Wanted - General Purpose "Glue Logic" Data-Structures

[Wheeler Ruml]

>   - fast computation of cardinality
> 
>   - fast addition of single elements
> 
>   - fast addition of lists of elements
> 
>   - fast removal of single elements in random order
> 
>   - not choking on a large data size

I saw Brian's recommendation of a priority queue, but wanted to
mention that a resizable array would do here as well.  Eg, something
like

type rarray = {
   a : 'a array;
   end : int;
}

where you allocate more space than you need (or allocate to the
correct size at the start, if you know it), doubling the size when
necessary, and only look at those elements before the end.  Brian's
queue may well do this underneath, but there's no reason to suffer
O(log n) insertion and removal time if you don't really care about the
order.  Just add to the end and swap with a random element in constant
time.  Or remove from a random place and copy in the last element.
The only tricky thing is to be careful to fill any "empty" cells in
the array with the same dummy value (which needs to be supplied at
creation time) so you don't prevent objects from being GC'ed.


Wheeler
-- 
Wheeler Ruml, Palo Alto Research Center, Rm 1522, 650-812-4329 voice
http://www.parc.com/ruml                          650-812-4334 fax

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: Wanted - General Purpose "Glue Logic" Data-Structures

[Markus Mottl]

On Mon, 07 Apr 2003, Wheeler Ruml wrote:
> I saw Brian's recommendation of a priority queue, but wanted to
> mention that a resizable array would do here as well.

The RES-library implements everything you need for that purpose and also
matches the signature of ordinary arrays:

  http://www.oefai.at/~markus/home/ocaml_sources.html#RES

Regards,
Markus Mottl

-- 
Markus Mottl          http://www.oefai.at/~markus          markus@oefai.at

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: Wanted - General Purpose "Glue Logic" Data-Structures

[Yaron M. Minsky]

Does anyone know if there's any hope of getting RES or a RES-like
library into the standard distribution?  Resizeable arrays seem like a
pretty essential data structure, and the fact that you can't implement
them nicely without breaking the standard compiler abstractions (due to
the dummy value issue) argues in favor of including it in the
distribution, I would think.

Yaron

On Tue, 2003-04-08 at 05:12, Markus Mottl wrote:
> On Mon, 07 Apr 2003, Wheeler Ruml wrote:
> > I saw Brian's recommendation of a priority queue, but wanted to
> > mention that a resizable array would do here as well.
> 
> The RES-library implements everything you need for that purpose and also
> matches the signature of ordinary arrays:
> 
>   http://www.oefai.at/~markus/home/ocaml_sources.html#RES
> 
> Regards,
> Markus Mottl
-- 
|--------/            Yaron M. Minsky              \--------|
|--------\ http://www.cs.cornell.edu/home/yminsky/ /--------|

Open PGP --- KeyID B1FFD916 (new key as of Dec 4th)
Fingerprint: 5BF6 83E1 0CE3 1043 95D8 F8D5 9F12 B3A9 B1FF D916



-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: Wanted - General Purpose "Glue Logic" Data-Structures

[Brian Hurt]

On Mon, 7 Apr 2003, Wheeler Ruml wrote:

> I saw Brian's recommendation of a priority queue, but wanted to
> mention that a resizable array would do here as well.  Eg, something
> like

It actually sounds like a simple tree is what he needs.  The problem with 
a resizeable array is that removing anything except the last element is 
O(n)- remember that you have to copy all the higher elements down.  He 
specified fast deletion of arbitrary elements.

> Brian's
> queue may well do this underneath, 

Actually, my PSQueue is built ontop of a red-black tree.  And it's mainly 
usefull when you need both the behaviors of a priority queue and a search 
tree.  Otherwise it is a little heavy/

> but there's no reason to suffer
> O(log n) insertion and removal time if you don't really care about the
> order.  Just add to the end and swap with a random element in constant
> time.  Or remove from a random place and copy in the last element.
> The only tricky thing is to be careful to fill any "empty" cells in
> the array with the same dummy value (which needs to be supplied at
> creation time) so you don't prevent objects from being GC'ed.

This was the problem I ran into trying to do an arbitrary resizeable
array- I ended up doing a Some of/None trick to handle empty array
elements.  Which, of course, added a whole second layer of references.  
Although requiring the user to supply a null item isn't as bad as I first
thought- it's the same thing that Array.make does...

Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: Wanted - General Purpose "Glue Logic" Data-Structures

[John Gerard Malecki]

Brian Hurt wrote (2003-04-08T10:07:16-0500):
 > 
 > It actually sounds like a simple tree is what he needs.  The problem with 
 > a resizeable array is that removing anything except the last element is 

Yes, I'm looking for is a light-weight, auto-balancing data-structure.
It does not necessarily need to be a tree.  It does not necessarily
need to be functional.  So far I have experimented with specialized
code, maps, treaps and splay-trees.  I still haven't found the Silver
Bullet or Holy Grail.  I'll summarize my findings later this month.

To re-iterate, I'm looking for a general purpose data-structure that
can collect large amounts of data, perform and prepare it for input to
specialized algorithms.  This typically means adding lots of elements
and lists of elements and then removing (controlled mapping) of those
elements preferably in random order.

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: Wanted - General Purpose "Glue Logic" Data-Structures

[Jean-Christophe Filliatre]

Yaron M. Minsky writes:
 > Resizeable arrays seem like a
 > pretty essential data structure, and the fact that you can't implement
 > them nicely without breaking the standard compiler abstractions (due to
 > the dummy value issue) argues in favor of including it in the
 > distribution, I would think.

There is an easy trick for this dummy value issue.

What you want is an interface looking like:

======================================================================
type 'a t                    (* resizeable vectors *)
val create : int -> 'a t     (* only initial capacity is given *)
val add : 'a t -> 'a -> unit 
...
======================================================================

The idea is  to initially store the capacity as  a negative size, thus
remembering that the data array still needs initialization:

======================================================================
type 'a t = { mutable size : int; mutable data : 'a array }

let create n = 
  if n <= 0 then invalid_arg "create";
  { size = -n; data = [||] }
======================================================================

Note that being empty is having a size less or equal than zero:

======================================================================
let is_empty v = v.size <= 0
======================================================================

Then the first time an addition is performed, you allocate the array:

======================================================================
let add v x =
  if v.size < 0 then begin  (* first addition: we allocate the array *)
    v.data <- Array.create (- v.size) x; v.size <- 0
  end;
  (* code to insert x, resizing data if needed *)
  ...
======================================================================

Hope this helps,
-- 
Jean-Christophe Filliâtre (http://www.lri.fr/~filliatr)

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: Wanted - General Purpose "Glue Logic" Data-Structures

[Brian Hurt]

This doesn't work, or at least doesn't work well.  What happens when you 
delete the value being used as the null value?  You have to go through and 
reset all the null values to the new null value.  Also, you want to keep 
reallocations to a minimum.  If you hit the point where you keep adding 
and deleting the last element, you have to keep allocating and 
deallocating the array block.

Brian


On Wed, 9 Apr 2003, Jean-Christophe Filliatre wrote:

> 
> Yaron M. Minsky writes:
>  > Resizeable arrays seem like a
>  > pretty essential data structure, and the fact that you can't implement
>  > them nicely without breaking the standard compiler abstractions (due to
>  > the dummy value issue) argues in favor of including it in the
>  > distribution, I would think.
> 
> There is an easy trick for this dummy value issue.
> 
> What you want is an interface looking like:
> 
> ======================================================================
> type 'a t                    (* resizeable vectors *)
> val create : int -> 'a t     (* only initial capacity is given *)
> val add : 'a t -> 'a -> unit 
> ...
> ======================================================================
> 
> The idea is  to initially store the capacity as  a negative size, thus
> remembering that the data array still needs initialization:
> 
> ======================================================================
> type 'a t = { mutable size : int; mutable data : 'a array }
> 
> let create n = 
>   if n <= 0 then invalid_arg "create";
>   { size = -n; data = [||] }
> ======================================================================
> 
> Note that being empty is having a size less or equal than zero:
> 
> ======================================================================
> let is_empty v = v.size <= 0
> ======================================================================
> 
> Then the first time an addition is performed, you allocate the array:
> 
> ======================================================================
> let add v x =
>   if v.size < 0 then begin  (* first addition: we allocate the array *)
>     v.data <- Array.create (- v.size) x; v.size <- 0
>   end;
>   (* code to insert x, resizing data if needed *)
>   ...
> ======================================================================
> 
> Hope this helps,
> 

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: Wanted - General Purpose "Glue Logic" Data-Structures

[Jean-Christophe Filliatre]

In the solution I proposed, you do not deallocate the array block when
you delete the last element; only the size is decreased.

Actually, I didn't use this  trick to implement resizeable arrays, but
to implement heaps encoded in (resizeable) arrays---available from the
hump; but I think the same idea applies.

-- 
Jean-Christophe

Brian Hurt writes:
 > 
 > This doesn't work, or at least doesn't work well.  What happens when you 
 > delete the value being used as the null value?  You have to go through and 
 > reset all the null values to the new null value.  Also, you want to keep 
 > reallocations to a minimum.  If you hit the point where you keep adding 
 > and deleting the last element, you have to keep allocating and 
 > deallocating the array block.
 > 
 > Brian
 > 
 > 
 > On Wed, 9 Apr 2003, Jean-Christophe Filliatre wrote:
 > 
 > > 
 > > Yaron M. Minsky writes:
 > >  > Resizeable arrays seem like a
 > >  > pretty essential data structure, and the fact that you can't implement
 > >  > them nicely without breaking the standard compiler abstractions (due to
 > >  > the dummy value issue) argues in favor of including it in the
 > >  > distribution, I would think.
 > > 
 > > There is an easy trick for this dummy value issue.
 > > 
 > > What you want is an interface looking like:
 > > 
 > > ======================================================================
 > > type 'a t                    (* resizeable vectors *)
 > > val create : int -> 'a t     (* only initial capacity is given *)
 > > val add : 'a t -> 'a -> unit 
 > > ...
 > > ======================================================================
 > > 
 > > The idea is  to initially store the capacity as  a negative size, thus
 > > remembering that the data array still needs initialization:
 > > 
 > > ======================================================================
 > > type 'a t = { mutable size : int; mutable data : 'a array }
 > > 
 > > let create n = 
 > >   if n <= 0 then invalid_arg "create";
 > >   { size = -n; data = [||] }
 > > ======================================================================
 > > 
 > > Note that being empty is having a size less or equal than zero:
 > > 
 > > ======================================================================
 > > let is_empty v = v.size <= 0
 > > ======================================================================
 > > 
 > > Then the first time an addition is performed, you allocate the array:
 > > 
 > > ======================================================================
 > > let add v x =
 > >   if v.size < 0 then begin  (* first addition: we allocate the array *)
 > >     v.data <- Array.create (- v.size) x; v.size <- 0
 > >   end;
 > >   (* code to insert x, resizing data if needed *)
 > >   ...
 > > ======================================================================
 > > 
 > > Hope this helps,
 > > 


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: Wanted - General Purpose "Glue Logic" Data-Structures

[Markus Mottl]

On Thu, 10 Apr 2003, Jean-Christophe Filliatre wrote:
> In the solution I proposed, you do not deallocate the array block when
> you delete the last element; only the size is decreased.

There is one problem with this: you still need to fill in an object. If
you use one provided by the user, this will consume memory dependent
on the object size. Therefore, it is usually best to overwrite the
slot using evil "Obj.magic" inside of the library. Note that there may
also be finalizers associated with the value or it may be monitored by
weak arrays.

Regards,
Markus Mottl

-- 
Markus Mottl          http://www.oefai.at/~markus          markus@oefai.at

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: Wanted - General Purpose "Glue Logic" Data-Structures

[Brian Hurt]

On Thu, 10 Apr 2003, Jean-Christophe Filliatre wrote:

> 
> In the solution I proposed, you do not deallocate the array block when
> you delete the last element; only the size is decreased.

If the array is holding pointers to allocated blocks, then you may be 
keeping false pointers and preventing GC from cleaning up garbage.

Brian


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Re: Wanted - General Purpose "Glue Logic" Data-Structures

[David Brown]

On Thu, Apr 10, 2003 at 12:35:19PM +0200, Markus Mottl wrote:

> There is one problem with this: you still need to fill in an object. If
> you use one provided by the user, this will consume memory dependent
> on the object size. Therefore, it is usually best to overwrite the
> slot using evil "Obj.magic" inside of the library. Note that there may
> also be finalizers associated with the value or it may be monitored by
> weak arrays.

If you fill with an object provided by the user (a special empty object)
there will only be one of them.  It's still tacky, since to use it, you
have to think of the smallest element of your type.

For something I recently did, I ended up using evil "Obj.magic" to make
the module easier to use.  Thanks to the RES example.

Dave

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners