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

Store digits using more efficient container #133

Open
Tracked by #147
saxbophone opened this issue Feb 18, 2023 · 1 comment
Open
Tracked by #147

Store digits using more efficient container #133

saxbophone opened this issue Feb 18, 2023 · 1 comment
Labels
blocked This cannot be started until prerequisite(s) are completed good first issue Good for newcomers optimisation
Milestone

Comments

@saxbophone
Copy link
Owner

saxbophone commented Feb 18, 2023

We should stop using our custom-built storage type a linked list for the digits, vector is constexpr on many platforms now and it's probably faster than the hand-built structure we have been using let's use a constexpr deque implementation instead.

@saxbophone saxbophone added this to the v0.6 milestone Feb 19, 2023
@saxbophone saxbophone added the blocked This cannot be started until prerequisite(s) are completed label Feb 28, 2023
@saxbophone
Copy link
Owner Author

I recently rewrote my "shifted array (sharray)" implementation to be fully working. It's inspired by the standard library's deque but implemented in a simpler way. It gives $\mathcal{O}(1)$ random access and amortised $\mathcal{O}(1)$ push and pop at front and back. It's convenient for arby if we can retain the ability to quickly push and pop digits at either end, perhaps we should perfect that container we've built, rather than use vector.

@saxbophone saxbophone changed the title Store digits as std::vector Store digits using more efficient container Feb 28, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
blocked This cannot be started until prerequisite(s) are completed good first issue Good for newcomers optimisation
Projects
None yet
Development

No branches or pull requests

1 participant