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

Skip List insertion is slow #2

Closed
sushrut141 opened this issue Feb 2, 2021 · 1 comment
Closed

Skip List insertion is slow #2

sushrut141 opened this issue Feb 2, 2021 · 1 comment
Assignees
@sushrut141
Labels
bug Something isn't working

Comments

@sushrut141
Copy link
Owner

Description

The current insert implementation inserts into each level of the skip list.
Using the bisect method it is possible to obtain insertion points across all levels
in logarithmic time and insert new nodes after each of those points if required.
@sushrut141 sushrut141 added the bug Something isn't working label Feb 2, 2021
@sushrut141 sushrut141 self-assigned this Feb 2, 2021
sushrut141 pushed a commit that referenced this issue Feb 3, 2021
Resolves issue #2
4c9a4d8 
List insertion uses bisect to identify insertion position
This should improve insertion time since it's no longer linear time.
@sushrut141
Copy link
Owner Author

Changed insert method to avoid linear pass insert.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@sushrut141 sushrut141

Labels
bug Something isn't working
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@sushrut141