|
|
|
|
|
|
by grovesNL
700 days ago
|
|
|
This sounds interesting! From my understanding it’s similar to an inversion list but storing explicit in/out instead of deriving it from the element’s rank (i.e., index if it’s stored as an ordered `Vec`) mod 2. I’m not too worried about storage requirements though so I wonder if having to search the adjacent node to determine the duration vs. The current representation. I could see how this could improve update performance though. Augmenting tree nodes and/or keeping track of min/max duration across coarser regions seems like a good approach. I could see each layer being represented in-tree like you described, or as separate layers each with their own granularity, where they could help to tighten bounds during range queries. Do you know of any libraries implementing this? |
|
|
If you write your own btree, you can drop storing the explicit in/out and get it from the element's rank. I was suggesting the explicit value mostly to be able to re-use Rust's existing standard library BTreeMap, where you don't have access to the rank (as far as I can tell).
You could also use something like a 'log structured merge tree' to store inversion lists as (a collection of) Rust vectors.
> I could see each layer being represented in-tree like you described, or as separate layers each with their own granularity, where they could help to tighten bounds during range queries.
I would suggest keeping them in-tree, so you only need to chase pointers once. And your invariants are much simpler, because whenever you make any changes to the btree you are already touching exactly the same nodes you might need to update for the cache.
> Do you know of any libraries implementing this?
I've looked around a bit, but didn't find much for Rust. There's https://codeforces.com/blog/entry/68419 which comes close.
For Haskell, https://hackage.haskell.org/package/dual-tree should do pretty much exactly what we talked about.
I've only looked very briefly. So I'm sure there's lot I missed that you can maybe find with different keywords or so.
I briefly considered implementing my own version for Rust by hacking up the standard library's BTreeMap. I got as far as extracting the BTreeMap code from the standard library and making it compile and pass tests in its own crate, but then got distracted by actual work. :)
> I’m not too worried about storage requirements though so I wonder if having to search the adjacent node to determine the duration vs. The current representation. I could see how this could improve update performance though.
Well, going to the next node (or previous node) should be cheap on average.
You could cache the duration in the nodes, if you wanted to, at the cost of making your invariants a bit more annoying (and slightly more expensive to update).
Because getting to the next node should be so cheap on average, I can't really predict whether storing your durations also with your nodes would actually improve performance.