4 ms·
I think this is an interesting idea. It might have some of the same problems as the dense bitset designs I've tried so far though but I'd like to try it out. Is
by grovesNL 2y ago
I think this is an interesting idea. It might have some of the same problems as the dense bitset designs I've tried so far though but I'd like to try it out. Is there a detailed description of this anywhere?
- kfrzcode 2y agoCould you separate out the data structure, i.e. keep your BTreeMap<u32, u32> for intervals, but add a Vec<u32> for available slots. Update both on insert/remove, then for range queries use the Vec<u32>? Sorry if this is dumb I'm a> not a rustian and b> not really a computer scientist lol
- grovesNL 2y agoDefinitely possible! I tried doing something similar which stored the ranges in a single `Vec<(u32, u32)>` but found the performance a bit worse than just using the ordered map.
- namibj 2y agoNot yet; I haven't gotten around to doing any of the implementing yet. The main difference is that this is trying to lock it's big-O's to the number of ranges, assuming that the data will not benefit (much) from dumb dense bitset representation.