• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Tim Cooke
  • Jeanne Boyarsky
  • Liutauras Vilda
Sheriffs:
  • Frank Carver
  • Henry Wong
  • Ron McLeod
Saloon Keepers:
  • Tim Moores
  • Frits Walraven
  • Tim Holloway
  • Stephan van Hulst
  • Carey Brown
Bartenders:
  • Al Hobbs
  • Piet Souris
  • Himai Minh

best java queue implementation

 
Ranch Hand
Posts: 348
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi all,

I want to know what's the best impl for queue (FIFO) in java 8. These are the only operations I'm gonna do to the collection:
1. add element (always at the tail)
2. remove element (always at the head)
no random access, no iteration, no synchronization needed, and it will have a fixed max size.

I saw that many people say linkedlist must be avoided (memory issue, etc), but arraylist is inferior in speed for the 2 operations I need compared to linkedlist.

Thanks
 
Ranch Hand
Posts: 239
12
Scala IntelliJ IDE Eclipse IDE Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I don't know why you would use a LinkedList. It is a doubly-linked list which you should only need if you plan on inserting and/or removing from the middle of it. Maybe try the LinkedBlockingQueue.
 
Java Cowboy
Posts: 16084
88
Android Scala IntelliJ IDE Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

David Spades wrote:I saw that many people say linkedlist must be avoided (memory issue, etc), ...


It's never good to dismiss something because you heard somebody say something but you don't understand it yourself. It is not true that you should always avoid LinkedList.

There's nothing wrong with a LinkedList and it's perfectly well suited for the things you mentioned.
 
Ranch Hand
Posts: 954
4
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Depends upon your requirement:

ArrayList use mostly when search operations is higher than delete and add
LinkedList Use mostly when add and delete operations are higher than search.

Secondly if you want constant time for every operation than LinkedList will be used against ArrayList because of time taken by ArrayList to ensure the capacity
if its full.
 
David Spades
Ranch Hand
Posts: 348
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I see. so for my operations:
1. add element always at the end
2. remove element always at the beginning
3. no iteration, no random access and no synchronization

LinkedList is best options in java 8, yes?
just want to make sure with those already using this impl if there's a better way or if linkedlist has undesirable side effects.
thanks
 
Marshal
Posts: 5409
326
IntelliJ IDE Python Java Linux
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Comparing a LinkedList and an ArrayList is not useful as ArrayList is not a Queue, in that it does not implement java.util.Queue.

I predict that you're overthinking this by a mile. Why not pick one, a LinkedList say, and try it out. Running tests in your own application is the only way to find out if a particular Queue implementation is suitable for your needs. If you find that a LinkedList is not up to the job, then analyse where the bottleneck or resource usage problem is and then review the other Queue implementations to find one that suits.

With the limited context you've provided, it's near impossible for us to advise you correctly.
 
Marshal
Posts: 76401
364
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
If you simply want a Queue implementation without bells and whistles, then this claims to be the fastest. Note no synchronisation.
 
David Spades
Ranch Hand
Posts: 348
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
ok, so what I'm trying to do is "guard" a certain method with a certain access frequency.
lets say I want the method not be accessed more than 60 times within any 5-minute window. so everytime the method is accessed:
1. it will first get "now" timestamp
2. check if the timestamp diff of first access token in queue and "now" is MORE than 5 mins
3. if #2 condition is met, pop first access token, create new access token and push said access token
4. if #3 condition is not met, then sleep

Thanks
 
Scott Shipp
Ranch Hand
Posts: 239
12
Scala IntelliJ IDE Eclipse IDE Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

David Spades wrote:I see. so for my operations:
1. add element always at the end
2. remove element always at the beginning
3. no iteration, no random access and no synchronization

LinkedList is best options in java 8, yes?
just want to make sure with those already using this impl if there's a better way or if linkedlist has undesirable side effects.
thanks



LinkedList doesn't fit your third criteria. You should try the LinkedBlockingQueue I mentioned. It fits all the criteria even #3.
 
Scott Shipp
Ranch Hand
Posts: 239
12
Scala IntelliJ IDE Eclipse IDE Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

David Spades wrote:ok, so what I'm trying to do is "guard" a certain method with a certain access frequency.
lets say I want the method not be accessed more than 60 times within any 5-minute window. so everytime the method is accessed:
1. it will first get "now" timestamp
2. check if the timestamp diff of first access token in queue and "now" is MORE than 5 mins
3. if #2 condition is met, pop first access token, create new access token and push said access token
4. if #3 condition is not met, then sleep

Thanks



Oh...so in that case why not just do this:

1. Create a small data structure that consists of a time and an int.
2. Set the int to 0 and record the time.
3. Every time the method is accessed, increment the int.
4. Every time the int is incremented, check the time. When it goes over five minutes, start again at step 2.

That should accomplish the same thing with less memory usage and a simpler implementation.
 
David Spades
Ranch Hand
Posts: 348
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
your approach wont work for this case

max 5 requests in any 5-minute window
4.03 am
4.08 am
6.10 am
8.02 am
9.02 am
9.03 am
9.05 am --> violated
 
Saloon Keeper
Posts: 14266
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Yes, the guard should keep a queue of accesses. On a request, the method first removes all accesses that have occurred longer than 5 minutes ago. Then it checks the size of the queue to see if a new access can be made. If the access is approved, it gets added to the queue, and the access is performed.

The go-to Queue implementation is ArrayDeque:
 
Stephan van Hulst
Saloon Keeper
Posts: 14266
321
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Regarding the removeWhile(): Normally I would use an Iterator, but doing it like this ensures that you can swap out the ArrayDeque for a PriorityQueue if you so please. PriorityQueue's iterator doesn't return elements in the queue's defined order.
 
Scott Shipp
Ranch Hand
Posts: 239
12
Scala IntelliJ IDE Eclipse IDE Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

David Spades wrote:your approach wont work for this case

max 5 requests in any 5-minute window
4.03 am
4.08 am
6.10 am
8.02 am
9.02 am
9.03 am
9.05 am --> violated



Why not? Looks like it will work fine to me. You haven't even put more than five requests here. Between 9:00 and 9:05 you only list three requests.
 
David Spades
Ranch Hand
Posts: 348
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
max 5 requests in any 5-minute window

there are 6 requests between 4.08am to 9.05 am (less than 5 minutes)
 
Campbell Ritchie
Marshal
Posts: 76401
364
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
That is not what 4.08am means. You mean something like this, maybe, with an hour included:-
6.4.03 am
6.4.08 am
6.6.10 am
6.8.02 am
6.9.02 am
6.9.03 am
6.9.05 am --> violated
 
David Spades
Ranch Hand
Posts: 348
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@Campbell:
what do you mean?
4.08 am mean 8 past 4 in the morning. I dont include the seconds in the time. most people dont include seconds when referring to any specific point of time, meeting at 8.15 sharp or the show at 9.30. but okay, fair point, since this is programming forum and most application deals with time down to seconds part.
 
Scott Shipp
Ranch Hand
Posts: 239
12
Scala IntelliJ IDE Eclipse IDE Java Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

David Spades wrote:max 5 requests in any 5-minute window

there are 6 requests between 4.08am to 9.05 am (less than 5 minutes)



OK you must have meant hours, not minutes, or what Campbell said. :-)

What I hear you saying is that you are thinking of this as a sliding window always centered between right now and five minutes (or hours?) prior? In that case if the window is always meant to be sliding, and not discrete five minute chunks in serial like I am thinking, then my proposal would not work as you want and it seems that something like Stephan's approach is good.

You mentioned setting a fixed max size though. An ArrayDeque cannot be bound but will always expand. A LinkedBlockingQueue on the other hand can be set to a fixed size when it is constructed. I don't know that it is the best queue for what you're doing, but I just noticed that it does fit your criteria. I whipped up some code to try it out and threw it on Github Gists. On my machine at least, this bumps around the 60 access limit, disallowing some calls and allowing others.
 
David Spades
Ranch Hand
Posts: 348
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@all:
damn, you're right. 4.08 - 9.05 --> that's 5 hour difference, not 5 minutes. sorry about that.
signs of brain overload, time for some relaxation and it's friday, tequila time.
thanks for the suggestions.
 
Yes, my master! Here is the tiny ad you asked for:
the value of filler advertising in 2021
https://coderanch.com/t/730886/filler-advertising
reply
    Bookmark Topic Watch Topic
  • New Topic