groovy

Exteremely bad performance of .unique() and .unique {closure}

Details

  • Type: Bug Bug
  • Status: Open Open
  • Priority: Major Major
  • Resolution: Unresolved
  • Affects Version/s: 1.7.5
  • Fix Version/s: None
  • Component/s: groovy-jdk
  • Labels:
    None
  • Number of attachments :
    1

Description

DefaultGroovyMethods.unique has two inner loops, so its complexity is O(n^2)
Practically it means that it starts taking ages on collections with 1000 or more elements.

Simply adding elements to a linked hash set would get O(n*log n) performance.
Will develop my own unique implementation after New Year, and will attach it here

Issue Links

is related to

Bug - A problem which impairs or prevents the functions of the product. GROOVY-4341 DefaultGroovyMethods#unique O(nē) performance

  • Major - Major loss of function.
  • Closed - The issue is considered finished, the resolution is correct. Issues which are not closed can be reopened.

Activity

Ascending order - Click to sort in descending order
Hide
Permalink
Paul King added a comment -

Worth also looking at the comments on GROOVY-4341 - not trying to put you off but just noting the desired functionality for that method from the respective comments.

Show
Paul King added a comment - Worth also looking at the comments on GROOVY-4341 - not trying to put you off but just noting the desired functionality for that method from the respective comments.
Hide
Permalink
Maxym Mykhalchuk added a comment -

linear .unique {} implementation

Show
Maxym Mykhalchuk added a comment - linear .unique {} implementation
Hide
Permalink
Maxym Mykhalchuk added a comment -

@Paul King - thank for pointing there, however there's one use case left that is not covered:
.unique {} with a closure taking a single parameter

I can prepare a proper patch if an approach using LinkedHashMap instead of comparator is approved.

Show
Maxym Mykhalchuk added a comment - @Paul King - thank for pointing there, however there's one use case left that is not covered: .unique {} with a closure taking a single parameter I can prepare a proper patch if an approach using LinkedHashMap instead of comparator is approved.
Hide
Permalink
blackdrag blackdrag added a comment -

But that is a different unique than the one we have. For example now I have:

assert [1, 1G].unique().size() == 1

Which means that it not only supports different objects inside, it also does compares as if they are done in Groovy code. Since your unique does not compare it is not possible to simulate that easily. The approach you have is more of like groupBy works, but without keeping the lists. If we add that then it should have a different name I think.

Show
blackdrag blackdrag added a comment - But that is a different unique than the one we have. For example now I have: assert [1, 1G].unique().size() == 1 Which means that it not only supports different objects inside, it also does compares as if they are done in Groovy code. Since your unique does not compare it is not possible to simulate that easily. The approach you have is more of like groupBy works, but without keeping the lists. If we add that then it should have a different name I think.
Hide
Permalink
Maxym Mykhalchuk added a comment -

@Jochen Theodorou:
I've got an idea how to make the current unique be O(n*log n) instead of n^2, will test and submit a patch on Monday, Jan 10

Show
Maxym Mykhalchuk added a comment - @Jochen Theodorou: I've got an idea how to make the current unique be O(n*log n) instead of n^2, will test and submit a patch on Monday, Jan 10
Hide
Permalink
Maxym Mykhalchuk added a comment - 
    /**
     * replacement of default groovy's .unique for a closure with a single parameter
     * with the same behavior, but with O(n * log n) complexity
     */
    public static <T> Collection<T> uniqueForClosureWithOneParameter(Collection<T> self, Closure closure) {
        if (self instanceof Set)
            return self;
        Set<Object> tempSet = new TreeSet<Object>(new NumberAwareComparator<Object>());
        List<T> answer = new ArrayList<T>(self.size());
        for(T t : self) {
            Object compareByValue = closure.call(t);
            if (!tempSet.contains(compareByValue)) {
                tempSet.add(compareByValue);
                answer.add(t);
            }
        }
        self.clear();
        self.addAll(answer);
        return self;
    }
Show
Maxym Mykhalchuk added a comment - /** * replacement of default groovy's .unique for a closure with a single parameter * with the same behavior, but with O(n * log n) complexity */ public static <T> Collection<T> uniqueForClosureWithOneParameter(Collection<T> self, Closure closure) { if (self instanceof Set) return self; Set< Object > tempSet = new TreeSet< Object >( new NumberAwareComparator< Object >()); List<T> answer = new ArrayList<T>(self.size()); for (T t : self) { Object compareByValue = closure.call(t); if (!tempSet.contains(compareByValue)) { tempSet.add(compareByValue); answer.add(t); } } self.clear(); self.addAll(answer); return self; }
Hide
Permalink
Maxym Mykhalchuk added a comment -

same idea (iterate all elements and add to both the treeset and a list) can be used for DefaultGroovyMethods#unique()
If this idea is OK, I can prepare a proper patch against groovy trunk

Show
Maxym Mykhalchuk added a comment - same idea (iterate all elements and add to both the treeset and a list) can be used for DefaultGroovyMethods#unique() If this idea is OK, I can prepare a proper patch against groovy trunk
Hide
Permalink
blackdrag blackdrag added a comment -

so you use a Treeset instead... that should work for the 1.0 and 1 issue. And the contents of the resulting Collection will be as before now. The only part left is order of the result. But if we add that, then we are at quadratic performance again I tihnk

Show
blackdrag blackdrag added a comment - so you use a Treeset instead... that should work for the 1.0 and 1 issue. And the contents of the resulting Collection will be as before now. The only part left is order of the result. But if we add that, then we are at quadratic performance again I tihnk
Hide
Permalink
Maxym Mykhalchuk added a comment -

hm... the order should be the same as it is in current implementation, only the check (whether the element is already collected) is different

Show
Maxym Mykhalchuk added a comment - hm... the order should be the same as it is in current implementation, only the check (whether the element is already collected) is different
Hide
Permalink
blackdrag blackdrag added a comment -

But TreeSet does not keep order it is possible that [1,2].unique() would turn out as [2,1] and [2,1].unique() would do the same.

Show
blackdrag blackdrag added a comment - But TreeSet does not keep order it is possible that [1,2] .unique() would turn out as [2,1] and [2,1] .unique() would do the same.
Hide
Permalink
Maxym Mykhalchuk added a comment -

look at the last method again
I do not use TreeSet for order, I add items to ArrayList other explicitly

Show
Maxym Mykhalchuk added a comment - look at the last method again I do not use TreeSet for order, I add items to ArrayList other explicitly
Hide
Permalink
blackdrag blackdrag added a comment -

oh, you are right. Nice

Show
blackdrag blackdrag added a comment - oh, you are right. Nice

People

  • Assignee:
    Unassigned
    Reporter:
    Maxym Mykhalchuk
Vote (2)
Watch (0)

Dates

  • Created:
    Updated: