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

[Wheeler Ruml <ruml@parc.com>]

>   - 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