[collections] SparseArrayList and SkipList [WAS Re: [primitives] objects indexed by int's and long's]

[robert burrell donkin <ro...@blueyonder.co.uk>]

(this sub-thread has moved towards collections territory)

On Sun, 2006-02-19 at 01:09 -0500, Sandy McArthur wrote:
> On 2/18/06, robert burrell donkin <ro...@blueyonder.co.uk> wrote:
> > an IntMap (for want of a better name) would have
> >
> > Object get(int key)
> >
> > rather than
> >
> > Object get(Object key)
> >
> > and so would avoid creating these intermediary key objects.
> 
> Looks like to me what you really want is a SparseArrayList implementation.
> 
> With a Map the int from key.hashCode() is a hint to optimize finding
> of the actually key. If you already have an int and that is the key,
> there is almost nothing to optimize. With an ArrayList you just jump
> to the value, no need to seach for it, couldn't be faster.
> Unfortunatly that may waste large chunks of memory in the space
> between meaningful indexes.
> 
> Now that I think of it more, I think you want a SkipList or something
> similar. http://en.wikipedia.org/wiki/Skip_list 

thanks very much for the pointers: i know very little about efficient
algorithms (possibly just a little ironic given my degrees are in
mathematics). 

> (I'm kind of suprised I don't see a SkipList in Commons Collections.)

quite probably it's waiting for a volunteer to step up and develop
one ;) 

if you've the time to lend a hand, sounds like it'd be good to have one
in there. 

any comments from the collections team?

- robert


---------------------------------------------------------------------
To unsubscribe, e-mail: commons-dev-unsubscribe@jakarta.apache.org
For additional commands, e-mail: commons-dev-help@jakarta.apache.org