groovy
  1. groovy
  2. GROOVY-5337

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

    Details

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

      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

          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 ]

            People

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

              Dates

              • Created:
                Updated:
                Resolved:

                Time Tracking

                Estimated:
                Original Estimate - 1 day
                1d
                Remaining:
                Remaining Estimate - 1 day
                1d
                Logged:
                Time Spent - Not Specified
                Not Specified