search

ryanq / ranged_set

A set that stores contiguous values as a range. Designed to be used with numeric types.
3 stars 2 forks source link

alternative storage backends #2

Open danieleades opened 3 years ago

danieleades commented 3 years ago

hi there! i wrote a similar crate to explore using a BTreeMap as an alternative backend for storing ranges to a Vec. A very quick and dirty set of benchmarks shows that for smaller sets the vector is more efficient, but for larger sets the map is more efficient. makes sense. lookup times scale linearly with the vector, but are close to constant with the map.

I've not done enough investigation to know when the two regimes cross over (there's a couple of variables, how many values are inserted and how contiguous they are). I wanted to gauge if there was an interest in making the storage swappable?

danieleades commented 3 years ago

you can check the bench here, if you're interested - https://github.com/danieleades/range-set/blob/bench-test/benches/comparison.rs

ryanq commented 3 years ago

Thanks for the PRs! And I’ll take a look at your repo. I really made this for my project looking at the Collatz conjecture and haven’t looked back. 😂