Groovy
  1. Groovy
  2. GROOVY-5337

Collection.unique() is O(n^2) time -- suggestion for improvement

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Major Major
    • Resolution: Duplicate
    • Affects Version/s: 1.8.5
    • Fix Version/s: None
    • Component/s: groovy-jdk
    • Labels:
    • Environment:
      ubuntu 10

      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

          Activity

          eike created issue -
          Pascal Schumacher made changes -
          Field Original Value New Value
          Link This issue duplicates GROOVY-4606 [ GROOVY-4606 ]
          Pascal Schumacher made changes -
          Status Open [ 1 ] Closed [ 6 ]
          Resolution Duplicate [ 3 ]
          Mark Thomas made changes -
          Project Import Sun Apr 05 13:32:57 UTC 2015 [ 1428240777691 ]
          Mark Thomas made changes -
          Workflow jira [ 12734260 ] Default workflow, editable Closed status [ 12746055 ]
          Mark Thomas made changes -
          Project Import Mon Apr 06 02:11:23 UTC 2015 [ 1428286283443 ]
          Mark Thomas made changes -
          Workflow jira [ 12971770 ] Default workflow, editable Closed status [ 12979580 ]

            People

            • Assignee:
              Unassigned
              Reporter:
              eike
            • Votes:
              0 Vote for this issue
              Watchers:
              1 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Time Tracking

                Estimated:
                Original Estimate - 24h
                24h
                Remaining:
                Remaining Estimate - 24h
                24h
                Logged:
                Time Spent - Not Specified
                Not Specified

                  Development