Re: [gui-dev] QueryRouteTable.java.patch (second version)

Any container abstraction suffers from the need to very quickly be able to
switch from one concrete representation to another.  In the specific case of
Integer array, we need to keep track of certain fill level after which the
bitset representation becomes more efficient and be able to convert the array
to that bitset on the fly using minimal amounts of cpu. Needless to say, any
such conversion must be ultra-efficient when done both directions. 
Furthermore, the managing code which decides when to do the conversion must be
lightweight and optimal.

Regarding various sub-bitset representations, we would ideally have an algorithm
which finds the optimal one for a given load factor/distribution.  My hunch is
that such algorithm would require memoization, but if anyone is aware of
something greedy that would work, let us know.

Quoting Philippe Verdy <[email protected]>:

> > The problem is that the BitSet implementation that we're using (a
> > customized
> > version of java.util.BitSet) is not sparse.  So, if the table is 1000
>
> I see... Couldn't we use multiple sub-bitsets? The complexity being to
> create the indirection table.
> I had another idea in the past, using something similar to Integer-Trie (the
> way they are used in the implementation of Unicode normalization tables),
> but dynamic maintenance and even generation of these tables are quite
> complex...
> The problem is that, despite tables are sparsely used, their distribution is
> still random, and the coverage still uniform, so solutions with double
> indirections will too often give the worst case where nothing can be gained.
> A sparse table will only save memory provided that it is nearly empty or
> nearly full (we can ignore this second case if we want to create larger
> tables).
>
> So may be we could use two alternate representation within a container
> class: as a bitset above some fill-threshold, or as an array of integers or
> an integer hashtable with collision below this threshold, the transformation
> back to an array of integers or hash table occuring only after a complete
> patch has been applied, that has reduced the fill level.
>
> Another representation could use binary trees for low fill levels.
>
>
> _______________________________________________
> gui-dev mailing list
> [email protected]
> http://www.limewire.org/mailman/listinfo/gui-dev
>



_______________________________________________
gui-dev mailing list
[email protected]
http://www.limewire.org/mailman/listinfo/gui-dev