What is the most efficient way to implement a non-blocking fixed-size queue in Java?

Question

I am trying to find (or write) a Java class that represents a fixed, non-blocking, automatically drops FIFO queue. (for example, if the queue has a capacity of 100, then position 101 deletes element 1, and then successfully adds element 101.) The answer to this question seems useful, but I have an additional limitation - I need it to be fast, for capacities of about 100 -1000.

The elements of my queue are Float only, since is it usually more efficient to use something like AutoDiscardingDeque<Float> described in a related question, or just use float[] manipulations and some System.arraycopy() to process it?

Alternatively, is there an even better solution that I haven't thought about?

Answer 1

If you need to use float, then yes, float[] will be optimal in implementation. You do not need to copy the array at all - just maintain a "start position" and an "end position". You already know the capacity, so you can create an array to start with it and not move from it.

Note that I do not suggest using float[] instead of the queue here - you can simply implement the queue using float[] . Of course, this means that you cannot easily implement its Deque<Float> , which you may need without the cost of boxing / unpacking ... but if you are only happy to ever use a particular class in your client code, you ultimately cost savings.

Answer 2

If you think that you are going to perform a number of mathematics-related functions in your structure, in particular, statistical functions such as mean, max, min, ect., Then you can use DescriptiveStatistics from Apache Commons Math (http: //commons.apache .org / math / userguide / stat.html # a1.2_Descriptive_statistics). You can set the window size and it will automatically save your elements. However, it requires doubling, not swimming, so this may not be the ideal solution for you.

Answer 3

I need it to be fast, for capacities of about 100-1000

Indicate what operations you need to be fast? The implementation is very reasonable how you intend to use it. If you need to access it by index very often than the above solution seems good enough