java + increasing performance and scalability

Question

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;

}

Remember the most important rule of optimizing--before you do it you must have performance requirements and you must have failed to meet those requirements--otherwise use the most readable code! How much do you have to improve to meet the requirements? — Bill K
– Bill K, Commented Sep 19, 2011 at 20:01

RonK · Accepted Answer · 2010-06-13 08:01:43Z

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.

Stephen C · Accepted Answer · 2010-06-13 05:04:50Z

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.

edited Jun 13, 2010 at 5:04

answered Jun 13, 2010 at 4:57

Stephen C

723k95 gold badges849 silver badges1.3k bronze badges

1 Comment

Chadwick Over a year ago

The Map would have to point to another collection to hold multiple Widgets of the same name.

Will Hartung · Accepted Answer · 2010-06-13 04:56:58Z

1

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

Map<String, List<Widget>> widgetMap;

answered Jun 13, 2010 at 4:56

Will Hartung

119k20 gold badges134 silver badges209 bronze badges

Collectives™ on Stack Overflow

java + increasing performance and scalability

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related