PriorityQueue

[Vitaly Davidovich]

Constructor has advantage in knowing it's working with a clean slate;
addAll could check for that too, I suppose, and at least skip things like
modCount increments.  As a general rule of thumb, I always prefer to have
dedicated methods for batch/bulk operations since you have more context to
potentially optimize.

sent from my phone
On May 15, 2015 10:04 AM, "Chris Hegarty" <chris.hegarty at oracle.com> wrote:

> And/Or should PriorityQueue override addAll and provide a more performant
> implementation for common Collection types ( just like the constructor )?
>
> -Chris.
>
> On 15/05/15 14:20, Vitaly Davidovich wrote:
>
>> Paul,
>>
>> I don't think you're missing anything obvious (unless I am as well :)).
>> What you wrote is basically what I meant by creating static helper method
>> in Brett's own code that does exactly what you wrote.  The asymptotic
>> complexity will be nlogn in both cases, but the constant factor will be
>> different since addAll() makes iterative add() calls with some overhead
>> (branches, modCount bump, etc).  The only O(n) constructors there are one
>> taking SortedSet and copy constructor.
>>
>> Brett did mention he wanted the bulk add functionality (i.e. remove
>> constant factor), and given the class already supports that internally,
>> seems like a harmless change.
>>
>> sent from my phone
>> On May 15, 2015 8:45 AM, "Paul Sandoz" <paul.sandoz at oracle.com> wrote:
>>
>>
>>> On May 14, 2015, at 8:17 AM, Brett Bernstein <brett.bernstein at gmail.com>
>>> wrote:
>>>
>>>  I believe the linked sequence of messages refer to the addition of a
>>>> PriorityQueue constructor only taking a Comparator which was does appear
>>>>
>>> in
>>>
>>>> Java 1.8.  Did you have a link to something regarding the a constructor
>>>> taking a Collection and a Comparator (2 arguments)?
>>>>
>>>>
>>> There is an old issue already logged for this:
>>>
>>>    https://bugs.openjdk.java.net/browse/JDK-6356745
>>>
>>> Give that one can already do:
>>>
>>>    Collection c = ...
>>>    Comparator cmp = ...
>>>    PriorityQueue p =new PriorityQueue(c.size(), cmp);
>>>    p.addAll(c);
>>>
>>> Is there a huge need for a new constructor that accepts a collection and
>>> a
>>> comparator?
>>>
>>> It seems a nice to have and may be marginally more efficient but AFAICT
>>> O-wise addAll and establishing the heap invariant for the entire tree
>>> that
>>> is initially unordered is the same (unless i am missing something obvious
>>> here).
>>>
>>> Paul.
>>>
>>>