CODEWITHSUNDEEP
javaperformancelistdictionarytime-complexity
aphrid
aphrid

Reputation: 599

Performance / readibility: Nested for-loops vs HashMap

(Note: Sorry if I put this question on the wrong stack exchange, I'll repost it if this question should be going somewhere else...)

I'm just starting out my first internship at a tech company, and wanted to ask about code performance and/or coding practices. I'm going through code written by a senior dev that doesn't seem right to me in terms of performance, but I'm not sure if it's because I'm inexperienced or if it's something of his.

Here's the code that I'm looking at:

// Given the following:
List<TypeA> aList = (...)
List<TypeB> bList = (...)

for(TypeA obj : aList) {
    boolean found = false;

    for(TypeB obj2 : bList) {
        if(obj.name.equals(obj2.name) {
            found = true;
            break;
        }
    }

    if(!found) {
        obj.doSomething();
        someOtherList.add(obj);
    }
}

My thoughts are that a O(n^2) nested for-loop is pretty inefficient for what the code is trying to do. Would it be better to do something like this? (Also please don't mind any syntax errors, I'm typing this on the fly ;)):

// Given the following:
List<TypeA> aList = (...)
List<TypeB> bList = (...)

Map<TypeB, String> bListToName = new HashMap<>()
bList.forEach(obj -> bListToName.put(obj, obj.name));

for(TypeA obj : aList) {
    if(bListToName.get(obj.name) == null) {
        obj.doSomething();
        someOtherList.add(obj);
    }
}

My reasoning is that instead of a nested for-loop, I use two O(n) loops instead, which should improve performance by a decent margin, especially if our a/bLists are sufficiently large or used often enough.

Any insight or thoughts would be greatly appreciated, thanks!

Upvotes: 1

Views: 3804

Answers (1)

Patrick Parker
Patrick Parker

Reputation: 4959

As you hinted, size is a factor. Building the hashmap means allocating additional memory, which could outweigh the time saved on a small number of comparisons.

I suggest you get used to doing time tests to put your theories into provable results. You will need to do that anyway to justify such changes during peer review.

Beyond that, I would just point out that what you are proposing is a half-measure. If the code is really critical then it would make sense to structure it as a Map in the first place.

Upvotes: 5

Related Questions