I’ve run into a similar problem in collaborative text editing. I assign an integer to each edit (which is a single character insert or delete). But obviously, humans usually type characters and delete characters in runs. I needed a fast associative map from edit id (integer) to some associated data. But the associated data is internally run length encoded so that I can assign a single value to an entire sequential run of edit operations. For example, set(10..20, X), set(12..15, Y) gives a map with 3 values: {10..12: X, 12..15: Y, 15..20: X}. I can do lookups by querying individual values, and the query returns the maximum run containing a consistent value.
I’m not sure how applicable my solution is to your problem, but it might work well. I implemented a custom btree with the semantics I needed, since btrees are fast and have great cache locality. The trick is making one that understands ranges, not just singular keys like std BtreeMap.
The code is here if you’re curious. It’s implemented on top of a pair of vecs - which makes it 100% safe rust, and curiously faster than the equivalent tree-of-raw-allocations approach. Please forgive the poor documentation - it’s an internal only type and the code is new enough that the paint hasn’t dried yet.
Comments
I’ve run into a similar problem in collaborative text editing. I assign an integer to each edit (which is a single character insert or delete). But obviously, humans usually type characters and delete characters in runs. I needed a fast associative map from edit id (integer) to some associated data. But the associated data is internally run length encoded so that I can assign a single value to an entire sequential run of edit operations. For example, set(10..20, X), set(12..15, Y) gives a map with 3 values: {10..12: X, 12..15: Y, 15..20: X}. I can do lookups by querying individual values, and the query returns the maximum run containing a consistent value.
I’m not sure how applicable my solution is to your problem, but it might work well. I implemented a custom btree with the semantics I needed, since btrees are fast and have great cache locality. The trick is making one that understands ranges, not just singular keys like std BtreeMap.
The code is here if you’re curious. It’s implemented on top of a pair of vecs - which makes it 100% safe rust, and curiously faster than the equivalent tree-of-raw-allocations approach. Please forgive the poor documentation - it’s an internal only type and the code is new enough that the paint hasn’t dried yet.
https://github.com/josephg/diamond-types/blob/master/src/ost...
Thanks, I'll take a look! It sounds like they're similar problems.