Scala Programming Language
  1. Scala Programming Language
  2. SI-5767

LinkedHashSet#remove has O(n) time complexity

    Details

      Description

      LinkedHashSet uses ListBuffer to store the elements in the right order.
      This leads to linear time complexity for removing an element from the set.

      What's even worse, it can lead to quadratic time complexity for set difference operation.

      Example:

      Welcome to Scala version 2.10.0-M3 (Java HotSpot(TM) Client VM, Java 1.6.0_16).
      Type in expressions to have them evaluated.
      Type :help for more information.
      
      scala> :paste
      // Entering paste mode (ctrl-D to finish)
      
      def test(set: collection.Set[Int], n: Int) {
        val seq = 1 to 1000*n
        val x = set ++ seq
        val y = set ++ seq.reverse
        val start = System.currentTimeMillis
        val z = x &~ y
        val end = System.currentTimeMillis
        assert(z.isEmpty)
        println("size: " + seq.size + "; time: " + (end - start) / 1000.0)
      }
      
      // Exiting paste mode, now interpreting.
      
      test: (set: scala.collection.Set[Int], n: Int)Unit
      
      scala> import collection.{mutable, immutable}
      import collection.{mutable, immutable}
      
      scala> test(immutable.Set(), 10)
      size: 10000; time: 0.015
      
      scala> test(mutable.HashSet(), 10)
      size: 10000; time: 0.032
      
      scala> test(mutable.LinkedHashSet(), 10)
      size: 10000; time: 3.719
      
      scala> test(immutable.Set(), 100)
      size: 100000; time: 0.375
      
      scala> test(mutable.HashSet(), 100)
      size: 100000; time: 0.281
      
      scala> test(mutable.LinkedHashSet(), 100)
      size: 100000; time: 418.64
      
      scala>
      

        Activity

        Hide
        Paul Phillips added a comment -

        Welcome to the monkey house.

        Show
        Paul Phillips added a comment - Welcome to the monkey house.
        Hide
        Julien Vion added a comment -

        I already filled this bug under SI-4639 and proposed a tentative correction.

        Show
        Julien Vion added a comment - I already filled this bug under SI-4639 and proposed a tentative correction.
        Hide
        Adriaan Moors added a comment -

        fix for 2.10 in 3cd8eb053a – backport to 2.9.3-rc2 pending

        Show
        Adriaan Moors added a comment - fix for 2.10 in 3cd8eb053a – backport to 2.9.3-rc2 pending
        Hide
        Adriaan Moors added a comment -

        I don't want to risk regressing in RC2. Should have been fixed in RC1 if we were going to do it in 2.9.3, now assigned to 2.9.4-RC1.

        Show
        Adriaan Moors added a comment - I don't want to risk regressing in RC2. Should have been fixed in RC1 if we were going to do it in 2.9.3, now assigned to 2.9.4-RC1.
        Hide
        Pavel Pavlov added a comment -

        Can we skip porting this one into 2.9? I doubt this can be done w/o breaking binary compatibility.

        Show
        Pavel Pavlov added a comment - Can we skip porting this one into 2.9? I doubt this can be done w/o breaking binary compatibility.

          People

          • Assignee:
            Pavel Pavlov
            Reporter:
            Pavel Pavlov
          • Votes:
            0 Vote for this issue
            Watchers:
            6 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development