Am 23.12.2010 23:59, schrieb Paul Benedict:
Ulf, a previous email by Remi said only to invoke size() if the collection is a
Set.
Thanks I missed that.
My guess was, that size() should be always faster than instantiating an iterator for the final
for-loop, and then seeing, that there is no element.
But:
Given Set c1 with 100 elements and Set c2 with 0 elements.
Then we iterate and compare over 100 elements for nothing.
Result map for method disjoint():
c1 | Set | mere
c2 | elements | 0 | 3 | 50 | 0 | 3 | 50
---------------------------------------------------------------------
| 0 |true |true|true |true |true|true
Set | 3 |true |t/f |t/f |true|t/f |t/f
| 50 |true |t/f |t/f |true|t/f |t/f
---------------------------------------------------------------------
| 0 |true |true|true |true |true|true
mere | 3 |true |t/f |t/f |true|t/f |t/f
| 50 |true |t/f |t/f |true|t/f |t/f
---------------------------------------------------------------------
(1) Iteration over in current webrev.3:
c1 | Set | mere
c2 | elements | 0 | 3 | 50 | 0 | 3 | 50
---------------------------------------------------------------------
| 0 | c2 |c2 |c2 | c1 |c1 |c1
Set | 3 | c2 |c2 |c2 |c1 |c1 |c1
| 50 | c2 |c2 |c2 |c1 |c1 |c1
---------------------------------------------------------------------
| 0 | c2 |c2 |c2 |none |none|none
mere | 3 | c2 |c2 |c2 |none| c1|c2
| 50 | c2 |c2 |c2 |none| c1|c1
---------------------------------------------------------------------
(2) Ideal iteration over:
c1 | Set | mere
c2 | elements | 0 | 3 | 50 | 0 | 3 | 50
---------------------------------------------------------------------
| 0 |none |none|none|none|none|none
Set | 3 |none|c1/2*|c2*|none|c1 |c1
| 50 |none|c1*|c1/2*|none|c1 |c1
---------------------------------------------------------------------
| 0 |none |none|none|none |none|none
mere | 3 |none|c2 |c2 |none|c1/2|c2
| 50 |none|c2 |c2 |none| c1|c1/2
---------------------------------------------------------------------
* Optimum could differ depending on types of Sets e.g. HashSet, TreeSet,
so further optimization is thinkable.
(3) Ideal iteration over, according "Set.size() can be expensive":
(I only found ConcurrentSkipListSet, are there others? Anyway, isn't size() anyhow cheaper than
superfluously looping contains() ?)
c1 | Set | mere
c2 | elements | 0 | 3 | 50 | 0 | 3 | 50
---------------------------------------------------------------------
| 0 |c1/2|c1/2|c1/2|c1 |c1 |c1
Set | 3 |c1/2|c1/2|c1/2|c1 |c1 |c1
| 50 |c1/2|c1/2|c1/2|c1 |c1 |c1
---------------------------------------------------------------------
| 0 |c2 |c2 |c2 |none |none|none
mere | 3 | c2 |c2 |c2 |none|c1/2|c2
| 50 |c2 |c2 |c2|none| c1|c1/2
---------------------------------------------------------------------
Why you introduce variables iterate and contains?
You could simply swap c1 with c2...
Shortest code for (2) with minimal swapping:
int c1size, c2size;
if ((c1size= c1.size())== 0 || (c2size= c2.size())== 0) {
// At least one collection is empty. Nothing will match.
return true;
}
if (!(c2 instanceof Set)) Optimize:{
// AsSet'scontains() impl predictably performs better(< O(N/2))
// thanmere Collection's, iterate over latter c2, except ...
if (!(c1 instanceof Set)) {
// 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 (N+1)/2comparisons thenchecking
// for all c1 elements in c2 would require 76.5 comparisons
// vs. all c2 elements in c1 would require 100.
if (c1size <= c2size) {
break Optimize;
}
}
Collection<?> temp = c1;
c1 = c2;
c2 = temp;
}
Shortest code for (3), on a par with (1) with minimal swapping:
if (!(c2 instanceof Set)) Optimize:{
// AsSet'scontains() impl predictably performs better(< O(N/2))
// thanmere Collection's, iterate over latter c2, except ...
if (!(c1 instanceof Set)) {
// Both are mere collections.
int c1size, c2size;
if ((c1size= c1.size())== 0 || (c2size= c2.size())== 0) {
// At least one collection is empty. Nothing will match.
return true;
}
// Iterate over smaller collection.
// E.g. if c1 contains 3 elements and c2 contains 50 elements
and
// assuming contains() requires (N+1)/2comparisons thenchecking
// for all c1 elements in c2 would require 76.5 comparisons
// vs. all c2 elements in c1 would require 100.
if (c1size <= c2size) {
break Optimize;
}
}
Collection<?> temp = c1;
c1 = c2;
c2 = temp;
}
-Ulf
