Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Question 1

What's the computational complexity of the Groovy unique() method?

Question 2

How could I have figured it out by myself? The unique() method is defined in the class DefaultGroovyMethods. The source code can be found here: org.codehaus.groovy.runtime.DefaultGroovyMethods. Can you point me to the piece of code which illustrates the answer to question 1?

share|improve this question
    
line 1031 seems to be where you need to look –  jk. Jun 20 '13 at 8:35
1  
@jk.: Two nested for-loops iterating over n, so O(n^2)? –  Lernkurve Jun 20 '13 at 8:40
    
@Lernkurve Generally I'd expect you'd want to loop over the collection once, and register each in a hash table to note that it's already included. Slightly more memory intensive, but only O(n) to traverse the list a single time. Dunno if that's actually how Groovy handles it though. –  KChaloux Jun 20 '13 at 13:00
    
@Lernkurve Upon actually looking at the code though, it looks like you're right... nested for-loops. :( –  KChaloux Jun 20 '13 at 13:03
    
@KChaloux: Ok, from your comments I understand that the best implementation of unique() would have a complexity of O(n), but this particular Groovy implementation of unique() in revision 728bb83ec has a complexity of O(n^2). Thank you. –  Lernkurve Jun 20 '13 at 13:54
show 2 more comments

1 Answer

up vote 4 down vote accepted

As Lernkurve pointed out in the comments, the implementation given in Groovy's source code appears to be O(n^2).

public static <T> Collection<T> unique(Collection<T> self, boolean mutate) {
    List<T> answer = new ArrayList<T>();
    for (T t : self) {                    // << Outer loop over each item
        boolean duplicated = false;
        for (T t2 : answer) {             // << Inner loop over each found item
            if (coercedEquals(t, t2)) {
                duplicated = true;
                break;
            }
        }
        if (!duplicated)
            answer.add(t);
    }
    if (mutate) {
        self.clear();
        self.addAll(answer);
    }
    return mutate ? self : answer ;
}

The outer loop ensures that the time complexity is at least O(n), because it will grow linearly as the input list grows. Likewise, the inner loop taken by itself is O(n). For each item in the input list, it then loops over each item that it's registered into the "answer" list to see if that item is already contained. Put them together and you've got an O(n^2) function.

As I pointed out in the comments, there are a few ways you might get better performance out of this, for large sets. If you're willing to spend a bit more memory, you can use a Hash set of some kind to register whether or not an element has already been included. These generally have an O(1) lookup time to check if the current item is unique to the list.

Alternatively, sorting the input list (if it is sortable) with a good sort function (most of those included in a language's standard library will be O(n log n)) can help, assuming you don't care about the order of the "unique" output list. This way you can be sure that duplicate elements will always appear in sequence with each other, and it becomes trivial to reject them from the output.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.