Details
-
Type:
Bug
-
Status:
Closed
-
Priority:
Major
-
Resolution: Won't Fix
-
Affects Version/s: 1.7.0, 1.7.3
-
Fix Version/s: 1.7.5, 1.8-beta-2
-
Component/s: groovy-jdk
-
Labels:None
-
Number of attachments :
Description
DefaultGroovyMethods#unique has a
O(nē)
performance which I noticed when I looked at why an application would consume all the CPU over a long period. This particular application moves a lot of stuff around and then calls #unique at the end of each cycle.
Anyway, here's how I would rewrite the method to get
O(n)
time complexity:
public static <T> Collection<T> unique(Collection<T> self) {
if (self instanceof Set)
return self;
Set<T> tempSet = new TreeSet<T>(new NumberAwareComparator<T>());
tempSet.addAll(self);
try {
self.retainAll(tempSet);
}
catch (UnsupportedOperationException ex) {
self.clear();
self.addAll(tempSet);
// Note that, as per Javadoc, both clear and addAll may throw an UnsupportedOperationException, too. :-(
}
return self;
}
Issue Links
- relates to
-
GROOVY-4606
Exteremely bad performance of .unique() and .unique {closure}
-
I just tried your suggestion.
It's indeed very fast... but running the full Groovy test suites with that change yields about 11 test failures!
Do you think you could have a closer look at it and correct the patch accordingly so we don't break our tests?
Thanks in advance.