4

I am trying to find (or write) a Java class that represents a fixed-size, non-blocking, auto-discarding FIFO queue. (e.g. if the queue has a capacity of 100, putting item 101 removes item 1 then successfully appends item 101.) The answer to this question seems helpful, but I have an extra constraint - I need it to be fast, for capacities of around 100-1000.

The items in my queue are only Floats, so is it generally more efficient to use something like the AutoDiscardingDeque<Float> described in the linked question, or just to use a float[] and some System.arraycopy() manipulation to handle it?

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

Community
  • 1
  • 1
Ian Renton
  • 699
  • 2
  • 8
  • 21

3 Answers3

2

If you only ever need to use floats, then yes, a float[] will be optimal in the implementation. You shouldn't 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 the array to start with and never budge from it.

Note that I'm not suggesting you use a float[] instead of a queue here - just that you can implement the queue using a float[]. Of course, that means you can't easily make it implement Deque<Float> which you may want it to, without incurring boxing/unboxing costs... but if you're happy only ever using the concrete class within your client code, you'll end up with efficiency savings.

Jon Skeet
  • 1,421,763
  • 867
  • 9,128
  • 9,194
1

If you think you are going to want to perform a number of math related functions on your structure, specifically statistics functions like mean, max, min, ect., then you could use DescriptiveStatistics from Apache Commons Math (http://commons.apache.org/math/userguide/stat.html#a1.2_Descriptive_statistics). You can set your window size and it will automatically maintain your elements. However it takes doubles, not floats, so it might not be the perfect solution for you.

dmcnelis
  • 2,913
  • 1
  • 19
  • 28
0

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

Please, specify, which operations you need to be fast? Implementation is very sensible to how you are going to use it. If you need accessing it by index very often, than the solution above seems good enough

sakharuta
  • 31
  • 1
  • 5
  • It's the `put` that I particularly need to be fast; as a secondary consideration it would be nice if there was a fast way to get an array representation of the list, e.g. `Collection.toArray()`. (Obviously the second issue is trivial if I use a `float[]` anyway.) – Ian Renton Feb 11 '11 at 13:29
  • I would just do a wrapper above float[] and thats it. Propose to close. – sakharuta Feb 11 '11 at 14:50