Review for CR 6728865 : Improved heuristics for Collections.disjoint() [updated]

[Paul Benedict]

Ulf, a previous email by Remi said only to invoke size() if the collection
is a Set.

Paul

On Thu, Dec 23, 2010 at 4:24 PM, Ulf Zibis <Ulf.Zibis at gmx.de> wrote:

> Am 23.12.2010 22:24, schrieb Ulf Zibis:
>
>> Aren't the explanation comments from my last example clear enough and more
>> fluently readable?
>>
>
> Shouldn't we examine the size at first? :
>
>
>        // collections to iterate and examine containment on
>        Collection<?> iterate = c1;
>        Collection<?> contains = c2;
>
>        // performance optimization cases
>        int c1size = c1.size();
>        int c2size = c2.size();
>        if (c1size == 0 || c2size == 0) {
>            // At least one collection is empty. Nothing will match.
>            return true;
>        if (c1 instanceof Set || (!(c2 instanceof Set) && c1size > c2size) {
>
>            // As mere Collection's contains() impl predictably performs
> worse
>            // than Set's (< O(N/2)), iterate on c2.
>            // Or if both are mere collections, iterate over smaller
> collection.
>
>            // E.g. if c1 contains 3 elements and c2 contains 50 elements
> and
>            // assuming contains() requires ceiling O(N/2) comparisons then
>            // checking for all c1 elements in c2 would require 75
> comparisons
>            // vs. all c2 elements in c1 would require 100.
>            iterate = c2;
>            contains = c1;
>        }
>
> -Ulf
>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.openjdk.java.net/pipermail/core-libs-dev/attachments/20101223/3065e9e7/attachment.html>