ArrayList was good (from the memory point of view) because it used array as a mean of element storage. Its disadvantage however was that it was not a queue, so the removal of its first element always moves all elements (with the first one excluded) to a lower index. And as the speed of such operation is O(n) this was not acceptable for cases where you had too many elements (my case).
| remove first | insert last | |
|---|---|---|
| ArrayList | O(n) | O(1) or O(n) when resizing |
| LinkedList | O(1) | O(1) |
The disadvantage of LinkedList (besides its slower insert) was that it wrapped each inserted element into a new wrapper and thus increased the memory usage.
As i needed something better I decided to implement my own queue. And so LinkedArrayQueue was born.
The design was quite simple: to reuse the principle of LinkedList (as this was more closely copying my expectations) and "fix" its memory issues. So instead of creating a wrapper for each new element I was wrapping an array that was suposed to hold the queue elements. When the array was fully written a new wrapper with array was created = O(1). When all elements from an array were polled/removed (O(1)) the array with its wrapper was thrown away = O(1). This way we'll get an insert (O(1)) almost as fast as an insert into an array and also m-times less element wrappers as in the LinkedList (where m means the size of the wrapped array). Also the creation of a new array with its wrapper takes a constant amount of time = O(1).
Here is a graphical representation of this concept:
And here are some interesting results I got on my machine (-Xmx64m, java 1.6.0_16):
As you can see with the same provided memory I was able to store more elements (in my case I was storing the same Integer n-times) and much faster that it was possible in LinkedList or ArrayList. Also the poll/remove operation was much faster than in ArrayList and only slightly faster than in LinkedList. And that is what I exactly wanted.
And here are some interesting results I got on my machine (-Xmx64m, java 1.6.0_16):
| inserts before OutOfMemory Error | insert last speed ns/element (of 1 milion inserts) - aprox. average | remove first speed ns/element (of 500 000 elements) - aprox. average | |
|---|---|---|---|
| ArrayList | 7 634 068 | 60 nanoseconds | 220 092 nanoseconds |
| LinkedList | 2 771 293 | 290 nanoseconds | 22 nanoseconds |
| LinkedArrayQueue (with array size 128) | 15 202 048 | 35 nanoseconds | 20 nanoseconds |
As you can see with the same provided memory I was able to store more elements (in my case I was storing the same Integer n-times) and much faster that it was possible in LinkedList or ArrayList. Also the poll/remove operation was much faster than in ArrayList and only slightly faster than in LinkedList. And that is what I exactly wanted.
So this is the design of my implementation. But if you know of some better (possibly existing) solution just let me know.
I think your solution may be optimal, as long as you need exactly what you described. But there are much more classes in Java, java.util.ArrayDeque could suit your needs, for the operations you need it's fast, although only in amortized time. This means that a single addLast or removeFirst may take a long time, but on the average the time is small and independent of the size. The advantage of ArrayDeque is the fast random access, which you don't need and which is for whatever reason missing in Java, but present in C++ deque.
ReplyDeleteYou wrote "[ArrayList's] disadvantage however was that it was not a queue, so the removal of its first element always created a new array into which it copied all elements with the first one excluded.", which is wrong, removal of the first element creates no new array, it "only" moves all the elements.
to maaartin: I have "fixed" the statement regarding the ArrayList object removal. Although the remove first operation only moves all elements to a lower index the speed of such operation is still O(n) which was not acceptable for me. but thank you for your correction and comment
ReplyDelete