Geek asks and answers

Best strategy for adding and removing in giant lists?

Using the Java .

I write small objects for some calculations, etc., and I only need the last x thousand of them. Therefore, I would like to release the first garbage collector. But since removing from ArrayLists is expensive ...

The following is important (I can not change)

  • no db
  • objects of the same type
  • up to 50,000 objects per second
  • performance is important
  • Fast iteration over the whole list is important.
  • random access also required

This can be changed:

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

My hunch:

  • LinkedList
  • Ringbuffer
  • ???

What can I do to iterate very quickly and quickly delete old objects?

+5
3

... , .

  • no get/put/etc. ,

( , " " ):

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

}

, .

, nextPutIndex, , 0 .

, node , LinkedList, , ArrayList.

, .

  • DB - ,

  • -

  • 50 000 - , Java

  • - , -

  • - , - / nextPutIndex

+5

, - . ( "" ) ( "" ). . .

(O(1)), .

, , .

, , . , ArrayList ( Java) . , , . ( , , - List.size()).

, , ( ).

+3

I would use an array and implement RingBuffer. I did this, but used a lot of unit test to make sure it always works. I did not find a suitable ring buffer for my needs, maybe you are more fortunate.

+3
source

More articles:


All Articles