A class I find missing in the new java.util.concurrent package is PriorityBlockingDeque. Just like PriorityBlockingQueue, this class should be sorting its elements either by their natural order or by a supplied Comparator.
I fail to understand the reason for having this class obviously missing from the package, and because I need it very much, I decided to create a blocking wrapper around NavigableSet using locks and conditions. This uses NavigableSet’s already existing methods of pollFirst, pollLast, first and last to fulfil the Deque interface.
Update: After some comments appeared I’ve realised that by using NavigableSet I do not allow for duplicate values on the Deque. Therefore, I’ve changed the implementation to use LinkedList internally, using Collections.sort calls to keep the list sorted. Unfortunately, this brings the basic add operation to O(n log(n)), instead of the O(log(n)) it used to be.
The code is fully available here, as part of the collections project, and some unit tests are available here.
I will later post how I used it, but let me know if you used it and if it was of any help (or filled with bugs..)
September 14th, 2007 at 6:13 pm
hi there,
What is the license for your software ?
Thank you,
BR,
~A
September 14th, 2007 at 6:16 pm
Which software? The collections library?
September 14th, 2007 at 6:21 pm
I think I understand what you mean, and I’ve added a license section above the code. I don’t know how that slipped out… Basically it’s the new BSD license.
September 15th, 2007 at 7:31 pm
PriorityQueue is implemented as a heap, which can be constructed in linear time (via bottom-up heap construction), which is much less expensive than sorting. However, if a dequeue is implemented upon a heap, the max (getFirst) can be retrieved in O(1) time, but there is no efficient way to get the min (getLast).
Maybe a “PriorityDequeue” is actually a SortedList ?
September 15th, 2007 at 8:40 pm
What you say is true – a heap is unusable for retrieving the last element.
I don’t understand your suggestion – I do not know of a SortedList interface/implementation in the JDK.. Perhaps you meant SortedSet? And if so, NavigableSet, which I use, is an extension of that interface.
The unfortunate thing about the PriorityBlockingDeque implementation of mine is that it doesn’t allow duplicate values, as that’s the primary constraint a Set has.
September 18th, 2007 at 8:11 am
I guess there is no need for a SortedList interface. A sorted List can be easily attained via Collections.sort(List), and subsequently maintained via ordered insertion via Collections.binarySearch(List).
September 18th, 2007 at 8:37 am
I disagree. This obviously works fine but it lacks two main features of actually having a SortedList interface:
1. There is no abstraction from the List’s user, where he can just count on the items to be sorted. As a user of a framework, I want to be able to call “add” on a List interface, and later on an internal implementation would know this is sorted and use it for its own needs – Otherwise, I need to abstract it myself when exposing the List in my classes.
2. There is no ability to implement the list in a way that is better suited for sorting, i.e. using data structures that are better for the task. Just like that a Set interface can be implemented using a hash table, but to reach a SortedSet you need a different implementation – each is more efficient for what the interface needs to provide.
September 18th, 2007 at 8:40 am
The reason there is no SortedList is in the List’s documentation:
A SortedList would break this rule, and methods such as “add(int, Object)” would have no meaning.
September 18th, 2007 at 8:45 am
So, since I seem to be contradicting myself in the last two comments, let me reiterate:
An interface that encapsulates SortedList would have been important even if you can achieve the same goal with java.util.Collections methods. The reason is for abstraction and for straight definition, also for additional methods that might be required such as retrieving the used Comparator (such as in SortedSet).
However, since List as an interface does not allow automatic sorting by definition, this seems (to me at least) to be the reason why this type of List is missing.
On the other hand, PriorityDeque is not a SortedList as well because it lacks features of a List – such as retrieving elements at a certain index etc.
On a different note, implementing PriorityDeque using a List and Collections methods would probably prove to be better conceptually, if not in performance, since it will permit duplicate values, something that NavigableSet does not.
What do you think?
September 19th, 2007 at 3:53 am
>implementing PriorityDeque using a List and
>Collections methods would probably prove to be
>better conceptually, if not in performance, since it
>will permit duplicate values, something that
>NavigableSet does not.
>What do you think?
That’s basically what I was trying to suggest
September 19th, 2007 at 6:56 am
I’ve created a test for it, and sure enough it fails with duplicate values; I’ve re-implemented it, this time using a LinkedList with a Collections.sort call when adding elements, and now it accepts duplicates.
I’ve checked it in so it should be available now.
September 24th, 2007 at 11:47 am
>with a Collections.sort call when adding elements
There is no need to sort when adding elements. Sorting is necessary only when the list is initially constructed. Subsequently adding elements only requires a binary search + insert. That will yield ln(n) instead of n*ln(n) time.
September 26th, 2007 at 11:27 pm
You’re right. I’ve changed it and checked it in.
October 4th, 2007 at 9:02 pm
I havn’t looks at how LinkedList and Collection.sort are implemented in detail, but doing a binary search on a linked list seems to be a bad idea to me. Accessing index i takes i steps on a linked list, so a binary search would be in O(n * log(n)). Simple linear scanning would be faster (O(n)). It’s kind of sad that ListIterator doesn’t have an insert method – that would avoid the issue that you have to scan twice: once iterating over the list to find the right place to insert your element, then again to actually insert it, using add(int, Object).
Anyway, by not doing a binary search but simply scanning for the place to insert the new item, i believe you can bring the complexity of add from O(n*log(n)) down to O(n). Still not great, but better…
October 4th, 2007 at 9:11 pm
You’re right, however, I could always change it to ArrayList and get it over with – receive the log(n) efficiency on one hand but might stumble upon bad efficiency during add() methods that exceed the size.
For that case, I could probably use the capacity to create the list at the right size right from the start (unless it’s
Integer.MAX_VALUE, of course).October 5th, 2007 at 10:41 am
Using an ArrayList would give you O(log(n)) complexity for add, but means O(n) complexity for removing the head of the queue (at least I think so – again, I have not looked at how ArrayList is implemented, exactly).
So, assuming an equal total number of add and remove/poll operations, the options appear to be: Use a LinkedList, with O(n) for add and O(1) for remove, giving you an amortized complexity of O(n), or using an ArrayList with O(log(n)) for add and O(n) for remove/poll, again giving you an amortized complexity of O(n), but with more overhead in practice (because you need n+log(n) steps and, as you mentioned, possibly for growing the array).
It would be interesting to run a benchmark to see which one is actually better for a “practical” size of the queue and number of add/remove operations.
October 5th, 2007 at 11:15 am
What you said brought up a memory and after careful checking I remembered why I didn’t use ArrayList in the first place (as it’s obviously the more efficient one) – it doesn’t have
pollFirstandpollLastfunctionality at all, as it doesn’t implement theDequeinterface, unlikeLinkedList.However, a Deque implementation using a ring-array is definitely possible, and I’m sure there’s a ring-array implementation somewhere out there to be used instead of re-writing it.
However, as to what you said, take a look at the
Collections.sortdocumentation:If I understand this correctly, this verifies what you said.
October 5th, 2007 at 12:48 pm
Hah, no it doesn’t confirm what I said. I should have read the docs carefully. Collections.sort is smarter than i thought – while a naive binary search on a LinkedList would be O(n * log(n)), Collections.sort does it in n steps with only log(n) comparisons, as opposed to n steps and n comparisons for the linear scan i suggested. I guess this is made possible by the fact that ListIterator can move both ways.
Another mistake I made is: ListIterator does haven an insert method (add). Sorry.
So, as it turns out, your LinkedList/Collections.sort based implementation seems to be optimal (or at least, slightly better than what I suggested), and I should read the documentation more closely
Thanks for this great blog, btw.
October 5th, 2007 at 12:58 pm
Heh, and I read them carefully but misunderstand what they mean. Well, anyway, that’s sorted out. Thanks for the input!