4 ms·
It'd be interesting to see it compared to https://doc.rust-lang.org/std/collections/struct.BTreeSet.html https://doc.rust-lang.org/std/collections/struct.BTreeS
by ntonozzi 6y ago
It'd be interesting to see it compared to https://doc.rust-lang.org/std/collections/struct.BTreeSet.html https://doc.rust-lang.org/std/collections/struct.BTreeSet.ht....
Their skiplist description is a little funny — typically a skiplist has one element per leaf node, and you should never need to move items between buckets. Also skiplists have logarithmic layers in the number of elements, so inserting and searching are always bounded by O(log n).
- jhgg 6y agoWe needed to support arbitrary index access into the sorted set - which is why stdlib btree map doesn't work.
- c0deb0t 6y agoFor binary trees, indexing can be done by saving the subtree size of each node and doing a sort of binary search. Not sure if this is fast for B-trees that have more than 2 children nodes, though.
- Lichtso 6y agoDo you mean OSTs? https://en.wikipedia.org/wiki/Order_statistic_tree https://en.wikipedia.org/wiki/Order_statistic_tree
- ntonozzi 6y agoOh, that makes sense. I like the solution you arrived at!
- infradig 6y agoI've been using a bucketized version of skiplist for years now, I thought I invented it! Using most recently in https://github.com/infradig/trealla https://github.com/infradig/trealla (a Prolog interpreter).