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
Comments
Imported From: https://issues.scala-lang.org/browse/SI-5767?orig=1 |
@pavelpavlov said (edited on May 7, 2012 10:56:04 AM UTC):
I wonder if this can be caused by SI-5293? |
@pavelpavlov said: See discussion there: |
@axel22 said: |
@pavelpavlov said: |
@axel22 said: |
@paulp said: |
Julien Vion (scand1sk) said: |
@adriaanm said: |
@adriaanm said: |
@pavelpavlov said: |
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:
The text was updated successfully, but these errors were encountered: