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

> 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