Em Ae February 2016

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


Peter Lawrey February 2016

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.


Andy Turner February 2016

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.

Post Status

Asked in February 2016
Viewed 2,502 times
Voted 8
Answered 2 times

Search




Leave an answer