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.

Sign up for GitHub

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

Possible improvements for RBTree #492

Open
luc-blaeser opened this issue Jan 5, 2023 · 5 comments
Open

Possible improvements for RBTree #492

luc-blaeser opened this issue Jan 5, 2023 · 5 comments

Comments

@luc-blaeser
Copy link
Contributor

Possible improvements for RBTree:

  • Reduce garbage creation, especially during reading functions, such as get() and iteration.
  • More efficient size() function.
@luc-blaeser luc-blaeser mentioned this issue Jan 5, 2023
Merged
luc-blaeser added a commit that referenced this issue Jan 5, 2023
@luc-blaeser
RBTree documentation and unit tests (#472)
a682631 
Improve `RBTree.mo`:
* Documentation
* Unit tests

Possible improvements for `RBTree` (#492):
* Reduce garbage creation, especially during reading functions, such as `get()` and iteration.
* More efficient `size()` function.
ggreif pushed a commit that referenced this issue Jan 5, 2023
@luc-blaeser @ggreif
RBTree documentation and unit tests (#472)
f0cf4da 
Improve `RBTree.mo`:
* Documentation
* Unit tests

Possible improvements for `RBTree` (#492):
* Reduce garbage creation, especially during reading functions, such as `get()` and iteration.
* More efficient `size()` function.
crusso added a commit that referenced this issue Jan 9, 2023
@crusso
fix for issue #492 (coin always 0 on first 8 tries)
cb010ed
@crusso crusso mentioned this issue Jan 9, 2023
Merged
2 tasks
@matthewhammer
Copy link
Contributor

matthewhammer commented Jan 11, 2023 •
edited
Loading

Another long-standing issue with RBTree is that it does not fully support delete.

Separately but also related, RBTree is purely functional. So maybe some users would consider an additional imperative version to be another dimension of improvement?

@crusso
Copy link
Contributor

crusso commented Jan 11, 2023

We should probably round out the functional one before adding an imperative one. Ie implement purely functional delete. Is it hard? Genuine question.

crusso added a commit that referenced this issue Jan 13, 2023
@crusso @rvanasa
bugfix: fix issue #492 plus some testing of Random.mo (#500)
22152e9 
Fixes issue #492 and adds some  basic tests.

- [x] test binomial consumes input

- [x] test the static functions.

Co-authored-by: Ryan Vandersmith <ryan.vandersmith@dfinity.org>
@crusso
Copy link
Contributor

crusso commented Jan 13, 2023

(Sorry, didn't mean to reference this issue from irrelevant PR #500 - meant #499)

@timohanke
Copy link

Reduce garbage creation, especially during reading functions, such as get() and iteration

General question: How can get() produce garbage? It's only reading. Recursion builds up the stack but that isn't garbage. What am I missing?

@timohanke
Copy link

Separately but also related, RBTree is purely functional. So maybe some users would consider an additional imperative version to be another dimension of improvement?

I wonder what kind of improvement we can expect from an imperative one. Wouldn't it end up looking very similar and have the same representation? What would get improved?

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

No branches or pull requests
4 participants
@crusso @matthewhammer @timohanke @luc-blaeser