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

Jump to bottom

Suggestion: Improvements to the RedBlackTree implementation #4082

Closed
scabug opened this issue Dec 14, 2010 · 4 comments
Closed

Suggestion: Improvements to the RedBlackTree implementation #4082

scabug opened this issue Dec 14, 2010 · 4 comments
Labels
enhancement library

Comments

@scabug
Copy link

scabug commented Dec 14, 2010

= problem =
This article seems to suggest that the Scala implementation is unnecessary complex:

[http://matt.might.net/articles/red-black-delete/]

= analysis =
It might be wise to test if his proposed implementation is not only simpler but also faster.

= enhancement recommendation =
If a better implementation is found, based on these ideas, which is both faster and easier to understand it should be implemented.
@scabug
Copy link
Author

scabug commented Dec 14, 2010

Imported From: https://issues.scala-lang.org/browse/SI-4082?orig=1
Reporter: @soc
See #5331

@scabug
Copy link
Author

scabug commented Dec 20, 2010

@hubertp said:
Assigning to the meeting, but I doubt this will get high attention since:
a) no direct patch is provided
b) no current scala reference/performance analysis is provided in the link/bug description
but hey, its Christmas close so maybe someone will want to play with this.

@scabug
Copy link
Author

scabug commented Dec 21, 2010

@hubertp said:
As I suspected, we have no resources for that kind of work. Please reopen if you have more precise info (preferably some benchmarks and patch).

@scabug scabug closed this as completed May 18, 2011
@scabug
Copy link
Author

scabug commented Nov 6, 2012

@soc said:
To keep this updated: The new implementation, RedBlackTree, seems to use the same code: https://github.com/scala/scala/blob/master/src/library/scala/collection/immutable/RedBlackTree.scala#L151

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
enhancement library
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@scabug