Morgan Schweers wrote:
> This is ESPECIALLY relevant in Java, with Swing's data model
> interface. If you can display a list of 10,000 names in alphabetical
> order, and be able to search to the 5000th with minimal overhead, then
> it becomes possible to display this to the user in a very clean fashion,
> with VERY good response time for nearly arbitrarily sized datasets.
>
> Most of the other ways of doing this seem to require more storage, or
> more time, or a static dataset in order to work cleanly. I feel that
> this would be a wonderful addition to the project, although it's not
> specifically oriented towards Sun Java compatibility.
I think that static dataset is an answer here. I doubt if you really
want to add 10000 entries one by one, updating display each time. Just
make a copy of data to ArrayList/Vector each time you need to display
it/data changed. I think that such copy would be faster than finding
5000-5020 entries in tree even with your speedup. And redisplays when
data has not changed would be a lot faster. As far as memory usage is
concerned, you use additional int per each node - so for 10000 nodes it
is sizeof(int)*10000 = 40000. And additional vector keeping data is
sizeof(ptr)*10000 = 40000 on most platforms :)
You solution may be faster if there would be one update to dataset after
each repaint. But even then I'm not sure if finding number of entries in
tree one by one would be faster than copying entire tree to Vector.
This way or another, all of it should be in userspace - not in default
classpath implementation.
And BTW, TreeSet/TreeMap does not implement List I think, so it normally
do not have to service get(int index) method. Optimizing for
nonexistnent method is not good thing :) You would have to extend
TreeSomething to implement List interface, add get(int index) method and
touch the internals to use the hack - but internals are private, so you
cannot do this.
So, the answer is implement TreeMapList, conforming to List interface,
possibly extends AbstractList or something like this, using some
portions of open source TreeMap/TreeSet classes from classpath.
Artur
