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?

Improve this question
6
  • When you say non-blocking, do you mean threadsafe too? Commented Feb 11, 2011 at 13:14
  • 1
    Don't System.arraycopy, have indexes to where you are. Commented Feb 11, 2011 at 13:21
  • @MHarris Not necessarily, just that there will never be any reason for putting item 101 to wait until some other operation occurs. Commented Feb 11, 2011 at 13:26
  • Did you have any performance issues using a JDK Queue implementation such ArrayDeque? Commented Feb 11, 2011 at 14:07
  • @Puce: ArrayDeque is not auto-discarding. Commented Feb 11, 2011 at 14:40

3 Answers 3

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

6 Comments

A circular int queue is even more efficient :) If you can findan implementation. I'll let you have the one I'm using when I get to a PC.
@Chris: Why would a circular int queue be more efficient when the OP is trying to store floats?
Even if internally using a float[], it should be wrapped in a nice class.
@Paŭlo: Absolutely. I wasn't suggesting it should just use a float array. I'll edit to make this clearer.
IntRingBuffer code: pastebin.com/abi1CLT4 -- you can easily convert this for any data type.
|
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.

Improve this answer

Comments

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

Improve this answer

2 Comments

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.)
I would just do a wrapper above float[] and thats it. Propose to close.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.