• Post Reply Bookmark Topic Watch Topic
  • New Topic

using a TreeSet

 
Asuthosh Borikar
Ranch Hand
Posts: 75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have a program which uses a TreeSet to store and retrieve objects in a particular order. I have a class that implements the Comparator interface, that's used by the TreeSet while storing the objects. The code looks something like the following:
//For each user
createTreeSet()
{
//add objects to the TreeSet in the order defined by the class
//that implements the Comparator interface
}
retrieveObjects()
{
Iterator iter = treeSet.iter();
while(iter.hasNext())
{
foo obj1 = (foo)iter.next();
//use this object
}
//end of For loop
I've read some posts in this forum and realized that I've fallen into the pit of casting objects retrieved from an Iterator(I wish I'd read them BEFORE the design phase). I can not use an Array here, since I want to retrieve the objects in a particular order, defined by the class that implements the Comparator interface. This piece of code is running very slow compared with other parts of the program and is becoming a bottleneck for performance. Is it possible, to improvise this code at all? I will be really glad if somebody can suggest me a solution. Thanks!
-Asuthosh
 
Peter den Haan
author
Ranch Hand
Posts: 3252
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Until Java implements proper generic types (templates) you won't be able to get around casts in the Collection framework.
What you might be able to do, if you tend to read the TreeSet multiple times, is to populate an Array with it:

The array will then contain your foo objects, cast and ready to use. The toArray method is defined to return the objects in the same order as the iterator.
- Peter
 
Asuthosh Borikar
Ranch Hand
Posts: 75
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks Peter! I will try this out.
 
Jack Shirazi
Author
Ranch Hand
Posts: 96
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
You haven't made clear whether it is the build or the access that is the bottleneck. The tuning strategies would be different if it is only one or the other. Peter's solution may be all you need.
If not, here are some suggestions. Firstlt, you could try reimplementing the TreeSet. You have access to the source, and it is not that difficult to understand (the underlying implementation is a TreeMap). Here are a couple of articles which may help in understanding Map structures and optimizing them: Optimizing a query on a Map and Optimizing hash functions for a perfect Map.
Note that the first of these articles covers how to specialize the implementation for a specific class, i.e. for your elements. With a TreeSet/TreeMap implementation specialized for your elements, you can access the element comparator methods more efficiently, or even bypass the method call and execute the comparison directly in the TreeSet for full efficiency. Using your own implementation also allows you to run the retrieval query more efficiently by implementing it in your TreeSet, allowing efficient traversal of the data structure.
Another possibility is to use an array structure with your own update which uses a binary sort based on the element comparators. Again, you can take advantage of efficiency gains which let you bypass the compareTo() method call if necessary.
Alternative strategies become available if one or the other is the bottleneck, for example use a simple Set for building, then convert to a sorted array - Arrays.sort and Collections.sort can help, and there are many other sort implementations available on the web.
--Jack Shirazi http://www.JavaPerformanceTuning.com/
 
Jack Shirazi
Author
Ranch Hand
Posts: 96
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
On further reflection, my last post wasn't as useful as it could have been. The TreeMap implentation is not explained by either of the referred to articles, as it is a Red-Black tree implementation. Still, although it is a little more complicated, you can optimize some of it without too much trouble.
In particular, three useful optimizations are not too difficult. Firstly, you can change the TreeMap.Entry class to be specialized to hold your own elements for keys, and change the various accessors and updators from Object to your element type, thus avoiding a bunch of casts (I just start with changing the key of the Entry inner class itself, then let the compiler tell me what else I have to change - boring but effective).
Secondly, the TreeMap.compare() private method can be specialized for your elements. And thirdly, the private successor() method provides the algorithm that iterates through the elements in order, so you can use this method to build your specialized retrieval query. I haven't had time to try these changes yet, but I'll confirm them once I do (but probably won't be for a couple of weeks).
Also, rather than use the TreeSet, you could use the TreeMap directly the way the TreeSet does, cutting out a little more overhead.
--Jack Shirazi http://www.JavaPerformanceTuning.com/
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!