Uploaded image for project: 'Groovy'
  1. Groovy
  2. GROOVY-4606

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

    XMLWordPrintableJSON

Details

    • Bug
    • Status: Open
    • Major
    • Resolution: Unresolved
    • 1.7.5
    • None
    • groovy-jdk
    • None

    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

      Attachments

        1. UniqueMath.java
          2 kB
          Maxym Mykhalchuk

        Issue Links

          is duplicated by

          Bug - A problem which impairs or prevents the functions of the product. GROOVY-5337 Collection.unique() is O(n^2) time -- suggestion for improvement

          • Major - Major loss of function.
          • Closed
          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

          Activity

            People

              Unassigned Unassigned
              mihmax Maxym Mykhalchuk
              Votes:
              2 Vote for this issue
              Watchers:
              4 Start watching this issue

              Dates

                Created:
                Updated: