add element to limited size list

user_1279180 0
Viewed 350

I have the following method which adds an element to a size limited ArrayList. If the size of the ArrayList exceeds, previous elements are removed (like FIFO = "first in first out") (version 1):

// adds the "item" into "list" and satisfies the "limit" of the list
public static <T> void add(List<T> list, final T item, int limit) {
        var size = list.size() + 1;
        if (size > limit) {
            var exeeded = size - limit;
            for (var i = 0; i < exeeded; i++) {
                list.remove(0);
            }
        }
        list.add(item);
    }

The "version 1"-method works. However, I wanted to improve this method by using subList (version 2):

public static <T> void add(List<T> list, final T item, int limit) {
    var size = list.size() + 1;
    if (size > limit) {
        var exeeded = size - limit;
        list.subList(0, exeeded).clear();
    }
    list.add(item);
}

Both methods works. However, I want to know if "version 2" is also more performant than "version 1".

EDIT: improved "Version 3":

public static <T> void add(List<T> list, final T item, int limit) {
        var size = list.size() + 1;
        if (size > limit) {
            var exeeded = size - limit;
            if (exeeded > 1) {
                list.subList(0, exeeded).clear();
            } else {
                list.remove(0);
            }
        }
        list.add(item);
    }
collections java
2 Answers

It seems you have the ArrayList implementation in mind where remove(0) imposes the cost of copying all remaining elements in the backing array, repeatedly if you invoke remove(0) repeatedly.

In this case, using subList(0, number).clear() is a significant improvement, as you’re paying the cost of copying elements only once instead of number times.

Since the copying costs of remove(0) and subList(0, number).clear() are identical when number is one, the 3rd variant would save the cost of creating a temporary object for the sub list in that case. This, however is a tiny impact that doesn’t depend on the size of the list (or any other aspect of the input) and usually isn’t worth the more complex code. See also this answer for a discussion of the costs of a single temporary object. It’s even possible that the costs of the sub list construction get removed by the JVM’s runtime optimizer. Hence, such a conditional should only be used when you experience an actual performance problem, the profiler traces the problem back to this point, and benchmarks prove that the more complicated code has a positive effect.

But this is all moot when you use an ArrayDeque instead. This class has no copying costs when removing its head element, hence you can simply remove excess elements in a loop.

user_27114880

Question 1: The problem is this line:

list = list.subList(exeeded, list.size());

You're reassigning the variable list which will not change to object passed as an argument but only its local counterpart.

Question 2: The sublist will (on an array list) still need to recreate the array at some point. If you don't want that you could use a LinkedList. But as a general rule the ArrayList will still perform better on the whole. Since the underlying array only has to be recreated when exceeding the maximum capacity it usually doesn't matter a lot. You could also try to actually shift the array, move every element to the next slot in the array. That way you would have to move all elements when a new one is added but don't need to recreate the array. So you avoid the trip to the heap which is usually the biggest impact on performance.

user_63852320
Related