Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] Wanted - General Purpose "Glue Logic" Data-Structures
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Wheeler Ruml <ruml@p...>
Subject: [Caml-list] Re: Wanted - General Purpose "Glue Logic" Data-Structures
>   - 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

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 Ruml, Palo Alto Research Center, Rm 1522, 650-812-4329 voice                          650-812-4334 fax

To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: