Fast algorithm to remove a number of elements from an ArrayList

Question

Say an ArrayList is of size n.

In my case, I often need to remove from 1 to n elements with different indexes from an ArrayList.

By using visualvm profiler, I found the ArrayList.remove() took around 90% of the running time.

So I want to improve the performance of the removal. I wonder if it could be accelerated.

Here is a minimal example:

public void testArrayListRemove() {
        List list = new ArrayList();
        int[] indexes = new int[] { 1, 2, 4, 10, 100, 1000 };
        for (int i = 0; i < 100000; i++) {
            list.add(i);
        }
        for (int i = indexes.length - 1; i >= 0; i--) {
            list.remove(indexes[i]);
        }
    }

The idea I can think of is to exchange those to be removed elements to the end and remove them there so that ArrayList.remove() do not need to make system.arraycopy. I am not sure whether this will really work.

Note: ArrayList.remove(i) when i is not the last element, it will perform a System.arraycopy to move elements.

It would be very appreciated if you can provide ideas to deal with my problem. You can either comment on my naive idea of exchanging elements to the end or maybe even better provide more advanced algorithms other than my idea.

Thanks.

Answer 1

You should take a look at GapList – a lightning-fast List implementation

From the article:

---

Introduction to GapList

To solve the issues brought out, we introduce GapList as another implementation of the java.util.List interface. As main features, GapList provides

• Efficient access to elements by index
• Constant time insertion at head and tail of list
• Exploit the locality of reference often seen in applications

Let's see how GapList is implemented to offer these features.

If we compare how the different kind of inserts are handled by ArrayList, we can quickly come up with a solution to guarantee fast insertion both at the beginning and at the end of the list.

Instead of moving all elements to gain space at index 0, we leave the existing elements in place and write the elements at the end of the allocated array if there is space left. So we basically use the array as a kind of rotating buffer.

For accessing the elements in the right order, we have to remember the start position of the first element and use a modulo operation to calculate the physical index from the logical one:

physIndex = (start + index) % capacity

To exploit the locality of reference, we allow a gap to be included in the storage of the list elements. The gap formed by the unused slots in the backing array can be anywhere in the list. There is at most one gap, but there can also be none.

This gap helps you to take advantage of the locality of reference to the list, so if you add an element to the middle of the list, a subsequent addition to the middle will be fast.

If a GapList has no gap, one is created if needed. If the gap is at a wrong place, it is moved. But if the operations happen near to each other, only few data will have to be copied.

GapList also allows removal of elements at the beginning and at the end without any moving of elements.

Removals in the middle are handled similar to insertions: an existing gap may be moved or vanish if no longer needed.

---

Here's a small sample code:

package rpax.stackoverflow.q24077045;

import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
import org.magicwerk.brownies.collections.GapList;

public class Q24077045 {

    static int LIST_SIZE = 500000;

    public static void main(String[] args) {
        long a1, b1, c1 = 0, a2, b2, c2 = 0;
        int[] indexes = generateRandomIndexes(10000);

        a2 = System.currentTimeMillis();
        List<Integer> l2 = testArrayListRemove2(indexes);
        if (l2.size() < 1)
            return;
        b2 = System.currentTimeMillis();
        c2 = b2 - a2;

        a1 = System.currentTimeMillis();
        List<Integer> l = testArrayListRemove(indexes);
        if (l.size() < 1)
            return;
        b1 = System.currentTimeMillis();
        c1 = b1 - a1;

        System.out.println("1 : " + c1);
        System.out.println("2 : " + c2);

        System.out.println("Speedup : "+ c1 * 1.00 / c2+"x");

    }

    static int[] generateRandomIndexes(int number) {
        int[] indexes = new int[number];
        for (int i = 0; i < indexes.length; i++)
        {
            indexes[i] = ThreadLocalRandom.current().nextInt(0, LIST_SIZE);
        }
        Arrays.sort(indexes);
        return indexes;
    }

    public static List<Integer> testArrayListRemove(int[] indexes) {
        List<Integer> list = new ArrayList<Integer>(LIST_SIZE);

        for (int i = 0; i < LIST_SIZE; i++)
            list.add(i);

        for (int i = indexes.length - 1; i >= 0; i--)
            list.remove(indexes[i]);
        return list;
    }

    public static List<Integer> testArrayListRemove2(int[] indexes) {

        List<Integer> list = GapList.create(LIST_SIZE);

        for (int i = 0; i < LIST_SIZE; i++)
            list.add(i);

        for (int i = indexes.length - 1; i >= 0; i--)
            list.remove(indexes[i]);
        return list;
    }

}

I my laptop is about 10x faster. It seems to be a good alternative to ArrayList.

^{Disclaimer: This is not a performance analisis. It is only an illustrative example.}

Answer 2

You can deal with the array and iterate through it:

Integer[] arr = list.toArray(new int[]{});

int[] newArr = new int[arr.length-indices.length];

Now you'd System.arrayCopy each continguous block of the array:

for (int i=0;i<arr.length;i++) {
    for (int j : indexes) { // Should be 'indices' btw
        if (j == arr[i]) {
            // Array copy arr to newArr
            break;
        }
    }
}

Answer 3

Check out the list of datastructures here. Pick one depending on your requirements. Like Guarev mentioned, a HashMap is probably your best bet. Hashmaps have the advantage of a constant time for insert, search, and delete.

ArrayLists are not a good structure for a storing a lot of data, as the memory usage quickly goes through the roof, and search/delete times get very expensive very quickly.

Answer 4

ArrayList is not really a good data structure to do this operation.

I would suggest you to use the HashMap for this purpose, you can keep the key, value pair with the key as the indexes.