Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

LinkedHashSet#remove has O(n) time complexity #5767

Closed
scabug opened this issue May 7, 2012 · 12 comments
Closed

LinkedHashSet#remove has O(n) time complexity #5767

scabug opened this issue May 7, 2012 · 12 comments

Comments

@scabug
Copy link

scabug commented May 7, 2012

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>
@scabug
Copy link
Author

scabug commented May 7, 2012

Imported From: https://issues.scala-lang.org/browse/SI-5767?orig=1
Reporter: @pavelpavlov
Assignee: @pavelpavlov
Affected Versions: 2.10.0-M3

@scabug
Copy link
Author

scabug commented May 7, 2012

@pavelpavlov said (edited on May 7, 2012 10:56:04 AM UTC):
Also, on 2.9.2 mutable.HashSet behaves awfully slow compared to immutable.Set:
(and its time grows even faster than n^2 on the set-diff test!)

scala> test(mutable.HashSet(), 10)
size: 10000; time: 0.203

scala> test(mutable.HashSet(), 100)
size: 100000; time: 36.0

scala> math.log10 (36.0/0.203)
res1: Double = 2.2488064628540743

I wonder if this can be caused by SI-5293?

@scabug
Copy link
Author

scabug commented May 24, 2012

@axel22 said:
I can't see observe this behaviour on 2.10. My guess is that this is caused by #5293 on 2.9.2.

This is a backport candidate.

@scabug
Copy link
Author

scabug commented Aug 27, 2012

@pavelpavlov said:
The bug is not fixed.

See discussion there:
https://groups.google.com/forum/?pli=1#!topic/scala-internals/1yABM30POS0

@scabug
Copy link
Author

scabug commented Aug 27, 2012

@axel22 said:
If you already have a bugfix, feel free to reassign.
Thanks! :)

@scabug
Copy link
Author

scabug commented Aug 27, 2012

@pavelpavlov said:
Just tried to re-assign to me and got no such user message from JIRA

@scabug
Copy link
Author

scabug commented Aug 27, 2012

@axel22 said:
You should get an account soon, I've just sent an email to ask for it.

@scabug
Copy link
Author

scabug commented Aug 27, 2012

@paulp said:
Welcome to the monkey house.

@scabug
Copy link
Author

scabug commented Aug 31, 2012

Julien Vion (scand1sk) said:
I already filled this bug under #4639 and proposed a tentative correction.

@scabug
Copy link
Author

scabug commented Jan 23, 2013

@adriaanm said:
fix for 2.10 in 3cd8eb053a -- backport to 2.9.3-rc2 pending

@scabug
Copy link
Author

scabug commented Jan 31, 2013

@adriaanm said:
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.

@scabug
Copy link
Author

scabug commented Feb 7, 2013

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

@scabug scabug closed this as completed Feb 7, 2013
@scabug scabug added this to the 2.10.0-M7 milestone Apr 7, 2017
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant