-
Notifications
You must be signed in to change notification settings - Fork 13
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
SkipList doesn't have the same semantics as a Vec #5
Comments
In [dependencies]
skiplist = "0.2.10" |
This was an interesting one. It took a while because for the first while, I thought of it as a data structures problem: if you have a structure for which inserting at an arbitrary index is O(log n) and retrieval is also O(log n), you can actually just run the entire simulation. After some searching, I discovered that skip lists actually do work that way. Unfortunately, the standard Rust implementation of skip lists are broken in some way, and I didn't have time to figure out exactly what was wrong with them. I filed an issue, but that's as far as I got with that: JP-Ellis/rust-skiplist#5 I actually considered giving up and looking at some other peoples' solutions, but decided not to. I did look up a generalized hint, which simply said that the twist in part 2 actually made it easier to abstract without simulation than part 1's problem; from there, I figured it out on my own. Resultant performance isn't great, but isn't terrible either: $ cargo build --release && time target/release/day17 Finished release [optimized] target(s) in 0.0 secs Item after 2017 inserts: 640 Item after 0 after 50 million inserts: 47949463 real 0m0.631s user 0m0.578s sys 0m0.000s
The cause is that the signature of |
Thanks for solving this! It's been a long while since I encountered this problem. Given that this is user error, one could plausibly just close this issue. On the other hand, there's no obvious reason why this library shouldn't use the same |
Given the following library code:
then running the following produces a value of
640
:However, if you replace
type List<T> = Vec<T>;
withtype List<T> = SkipList<T>;
in the library code, running the same code produces a value of494
. (No playground link because skiplist is not available in the playground; sorry.) In other words, though we haven't changed the algorithm at all, we get different results.This is obviously not a minimal example, and for that I apologize. However, this case seems to prove that something is broken in the
SkipList
implementation.The text was updated successfully, but these errors were encountered: