1

I'm using a huge ArrayList with the code bellow

public final List<MyClass> list = new ArrayList<>();

public void update(MyClass myClass) {
int i;
for (i=0; i < list.size(); i++) {
        if (myClass.foo(list.get(i))) {
            list.set(i, myClass);
            break;
        }    
    }    
    if (i == list.size()) {    
        list.add(myClass);    
    }    
}

The list is extremely large. There is something else that I can do to increase the performance with this scenario? Maybe using some Java 8 feature, replacing ArrayList or something like that.

Another code that is taking too long to run related this List is the code bellow:

public List<MyClass> something(Integer amount) {
list.sort((m1, m2) -> Double.compare(m2.getBar(), m1.getBar()));
return list.stream()
        .limit(amount)
        .collect(Collectors.toList());
}

Any help is welcome, thank you all

Improve this question
5
  • Arrays are crazy faster than ArrayLists, so if you can change your structure from an ArrayList to an Array, you'd increase performance by a huge margin. Changing to an Array from an ArrayList may be difficult, however. Commented Jun 27, 2018 at 12:59
  • What does the foo function do ? and how many objects do you have in your list ? Commented Jun 27, 2018 at 13:13
  • @ValentinMichalak foo function just compare the current object with the argument objet with equals. I have thousand Objects in my list Commented Jun 27, 2018 at 13:19
  • I think ArrayList is not the right datamodel. Why you doesn't use HashMap ? Commented Jun 27, 2018 at 13:22
  • You're just equals comparing - that's what Maps are for! The second problem may get much faster when amount is much less than list.size(), but maybe it's even simpler - just tell us how Bar is related to equals. Commented Jun 27, 2018 at 18:27

2 Answers 2

Reset to default
2

It seems like the choice of the ArrayList is not good.

In the first case, you attempt to find an object by his properties in the list. To find an object in the list, you have to check in each elements of your list. Bigger is the list, the longer it will be. (You have a worst case complexity of O(N) with ArrayList)

If you use an HashMap instead of a List, you can use your property as key of your map. Like this, you can select the object you need to update directly without check each element of your list. The execution time will be no more dependent of the number of entries. (You have a worst case complexity of O(1) with HashMap)

If you use HashMap instead of ArrayList, your update code gonna look like this:

public void update(MyClass myClass) {
    map.put(myClass.getKey(), myClass);
}

(where getKey() is the properties you try to equals in your foo method).

But this is only for the first case. With the informations we have it seems the best solution.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Thank you very much Valentim, I will try change to HashMap and put the results here!
I just change the code public void update(MyClass myClass) { map.put(myClass.getKey(), myClass); }
1

There is something else that I can do to increase the performance with this scenario?

The problem is that your algorithm has to apply myClass.foo to every element of the list until you find the first match. If you do this serially, then the worst-case complexity is O(N) where N is the list size. (And the list size is large.)

Now, you could do the searching in parallel. However, if there can be multiple matches, then matching the first one in the list is going to be tricky. And you still end up with O(N/C) where C is the number of cores available.

The only way to get better than O(N) is to use a different data structure. But without knowing what the MyClass::foo method does, it is hard to say what that data structure should be.

Your second problem seems to be trying to solve the "top K of N" problem. This can be implemented in O(N log K) and possibly better; see Optimal algorithm for returning top k values from an array of length N.

Improve this answer

3 Comments

Good idea to add complexity directly in the answer. I update my answer.
This is what myClass.foo does public boolean foo(Myclass other) { return source.equals(other.source); }
In that case, you should be using a HashSet. Performance will be O(1) for the operation that you are doing, and you can implement it as set.add(myClass). Of course, your equals and hashcode methods must obey the equals/hashcode contract. Read the javadocs.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.