[GROOVY-5337] Collection.unique() is O(n^2) time -- suggestion for improvement

• Type: Bug
• Status: Closed
• Priority: Major
• Resolution: Duplicate
• Affects Version/s: 1.8.5
• Component/s: groovy-jdk
• Labels: unique
• Environment: ubuntu 10
• Assignee: Unassigned
• Reporter: eike
• Created: 28/Feb/12 17:21
• Updated: 21/Jul/13 08:24
• Resolved: 21/Jul/13 08:24

Description

I tried Collection.unique

{closure}

and it was getting very slow when the dataset grew.
I believe it to be O(n^2)

I have not yet looked it up in the groovy sources,
but I believe that it must be implemented,
like calling that closure over and over again.

I'd like to suggest an alternative implementation,
which actually made things toward O in my case.

like:
Map unique
unique.put(closure(it), it)
return unique.values()

While this might use some more memory,
it really beats the current implementation hands of.

Please note that in this type of implementation,
the closure is only called once per element,
and all the burden of uniquing is placed on the map.

It should be consistent with the contract of the current api.
But it's much faster!

Issue Links

• duplicates: GROOVY-4606 Exteremely bad performance of .unique() and .unique {closure}