Java - Best Strategy For Appending and Deleting In Giant Lists?

Question

Using Java.

I record small objects for some calculation etc. and I need only the last x thousand of them. So I'd like to release the first to the garbage collector. But since deleting from ArrayLists is expensive ...

The following is important (can't change)

• no DB
• objects are the same type
• up to 50,000 objects per second
• performance important
• quick iteration through the whole list is important
• random access is also important

This can be changed:

• right now using ArrayList<MyObject>
• limit: 100,000 objects (stops recording, but must continue)

My guesses:

• LinkedList
• RingBuffer
• ???

What can I do to iterate very quick and release old objects also quick at the same time ?

Answer 1

A solution

... If you need a constant amount of last elements, just use an array as a base for a ring buffer.

• single allocation

• no get/put/etc. method overhead if inlined

• simple

A sample (may not compile, written on the fly) implementation:

class LastElementsStore<T> {
  Object[] arr;
  int size;
  int nextPutIndex;

  LastElementsStore(int size ) {
    arr = new Object[size];
    this.size = size;
  }

  void put(T elt) {
    arr[nextPutIndex] = elt;
    nextPutIndex++;
    if (nextPutIndex == size) {
      nextPutIndex = 0;
    }
  }

  // getters of your choice

}

If there are not enough elements, nulls will be returned.

If you need them ordered, you start from nextPutIndex, read till the end, then go to 0 and continue reading.

You have full control of the memory, no additional node allocations will be made as in LinkedList, no resizing as in ArrayList.

Old objects are released automatically as soon as your reach the limit.

Your requirements

• no DB -- done, just an array used

• objects are the same type -- simple template

• up to 50,000 objects per second -- if an array can't handle it, nothing in Java can

• performance important -- as above, no additional overhead in accessing an array quick iteration through the whole list is important -- as fast an iteration as possible

• random access is also important -- the data is ordered, and the first not-null element at/after nextPutIndex is the first available

Answer 2

Without knowing any of your other requirements, some type of linked list would seem appropriate. Just keep track of the first element (the "head" in list-speak) and the last (the "tail"). Each linked element refences the next. Add to the tail, and remove from the head.

Adding and removing will be very fast (O(1)), and iterating will also be very simple.

However, if you need random access to elements, then this solution will perform poorly.

EDIT

Since you've added that you need to have random access, a linked list won't work. If the maximum number of objects at any given time is fixed, you could use an ArrayList (or a basic Java array) and treat it as a wrap-around buffer. Once you reach the end, start replacing objects from the beginning, and keep track of the index that represents the logical start of the list. (If you use a basic array, you will also need to track how many elements are currently in the buffer -- the equivalent to List.size()).

As you replace objects at the beginning of the buffer, the old objects will be automatically released and garbage-collected (as long as they aren't referenced elsewhere).