java + increasing performance and scalability

Question

Hi,

below is the a code snippet, which returns the object of a class. now the object is basially comparing to some parameter in loop.

my concern is what if there are thousands of objects in loop, in that case performance and scalability can be an issue. please suggest how to improve this code for performance part

public Widget get(String name,int major,int minor,boolean exact) {
   Widget widgetToReturn = null;
   if(exact) {
       Widget w = new Widget(name, major, minor);

       // for loop using JDK 1.5 version
       for(Widget wid : set) {
            if((w.getName().equals(wid.getName())) && (wid.getVersion()).equals(w.getVersion())) {
                widgetToReturn = w;
                break;
            } 
       }
   } else {
       Widget w = new Widget(name, major, minor);
       WidgetVersion widgetVersion = new WidgetVersion(major, minor);

       // for loop using JDK 1.5 version
       for(Widget wid : set) {
           WidgetVersion wv = wid.getVersion();
           if((w.getName().equals(wid.getName())) && major == wv.getMajor() && WidgetVersion.isCompatibleAndNewer(wv, widgetVersion)) {
                widgetToReturn = wid;
           } else if((w.getName().equals(wid.getName())) && wv.equals(widgetVersion.getMajor(), widgetVersion.getMinor())) {
                widgetToReturn = w;
           }
       }
   }
   return widgetToReturn;

}

Answer 1

And these Widgets aren't in a map keyed by name...why?

Map<String, List<Widget>> widgetMap;

Answer 2

Rather than a simple "set" of Widgets, you probably need to maintain a Map<WidgetVersion, Widget>. This will give you O(1) (for a hash map) or O(logN) (for a tree map) lookup, compared with the O(N) lookup of the current version.

(You might actually need two maps, or a Map> or even something more complicated. I cannot quite figure out what your exact / inexact matching is supposed to do, and it also depends on how many versions of a given widget are likely in practice.)

In addition, the logic of your "exact" case looks broken. You are creating a widget, looking in the set of existing widgets, then:

• if you find a match you return the widget you just created ... (so why bother with the lookup??)
• if you didn't find a match you return null.

Answer 3

I think Will's question is the 1st question to ask - why are you holding the Widgets in a none efficient data structure?

If you use a structure like this:

Map<String, Map<WidgetVersion,Widget>> widgetMap;

You can write the following code:

public Widget get(String name,int major,int minor,boolean exact) 
{
   Widget widgetToReturn = null;

   Map<WidgetVersion,Widget> widgetVersionMap = widgetMap.get(name);
   WidgetVersion widgetVersion = new WidgetVersion(major, minor);
   widgetToReturn = widgetVersionMap.get(widgetVersion);
   if(widgetToReturn==null && exact==false) 
   {
       // for loop using JDK 1.5 version
       for(Entry<WidgetVersion,Widget> entry : widgetVersionMap.entrySet()) 
       {
           WidgetVersion wv = entry.getKey();
           if(major == wv.getMajor() && WidgetVersion.isCompatibleAndNewer(wv, widgetVersion)) 
           {
                widgetToReturn = entry.getValue();
           } 
       }
   }
   return widgetToReturn;
}

That way for exact searches you have an O(1) search time and for no-exact you have O(K) where K is the number of versions a widget has.