Reducing time complexity

I have list of objects which contains a statusEnum. Now, I want to return all those objects which falls under specific list of provided statuses.

A simple solution is to loop on list of objects and then another for loop on provided list of statusEnums ... This would work however, It would make the time complexity of O(n)^2. Is there a way i could reduce it to O(n) ?

I can't change the map. The only other solution i could think of is maintaining another map based on statusEnums as the key but then it would increase the space complexity a lot.

EDIT

  • I had hashMap of objects (which i said as a list)

Here is the code which i came up with for others ...

public List<MyObjects> getObjectsBasedOnCriteria (List<ObjectStatus> statuses, String secondCriteria){
    EnumSet<ObjectStatus> enumSet = EnumSet.copyOf(statuses);
    for (Map.Entry<Long, MyObject> objEntry : myObjs.entrySet()){
        MyObjects obj = objEntry.getValue();
        if (enumSet.contains(obj.getStatus()) && obj.equals(secondCriteria)){
        ...
        }
    }
}

Answers


Use an Set to hold statusEnums (probably an EnumSet), and check if each instance's status is in that set using set.contains(object.getStatus()), or whatever.

Lookups in EnumSet and HashSet are O(1), so the solution is linear (assuming just one status per object). EnumSet.contains is more efficient than HashSet.contains with enum values; however, the choice is irrelevant to overall time complexity.


Assuming you have a sane number of statuses, esp if you have a enum of statuses you can use an EnumSet to match the status or a HashMap.

Even if you don't do this the time complexity is O(n * m) where n is the number of entries and m if the number of statuses you are looking for. In general it is assumed that you will have much more records than you have statuses you are checking for.

The number of possible enum values is limited to a few thousand due to a limitation in way Java is compiled so this is always an upper bound for enums.


Need Your Help

Applying new UI to JInternalFrame title

java swing uimanager

I've never done anything with UI's before and I've been tasked with getting our internal frame titles changed. We're using the Nimbus L&amp;F and in our UI manager I've tried

jqGrid require on custom selectList

c# jquery model-view-controller jqgrid

I am trying to require user input on dynamic select list. I have the editrules:{require:true} in the ColModel but the pop up doesn't require the user to select an item that doesn't have the value o...