4 ms·
Moral of the story: First, use an array. If an array doesn't work, try something else.
by icsa 2y ago
Moral of the story:
First, use an array.
If an array doesn't work, try something else.
- kevingadd 2y agoIt's definitely the case that in many scenarios, the right data structure is an array, since you'll have work dominated by gets and sets. However, the OP has one scenario where the opposite was true - they were using a dense bitset that needed to be obscenely huge because of degenerate code in the wasm module, so swapping to a sparse container was a win. In the end you just have to profile and understand your data.
- icsa 2y agoTo your point, profile your data as you would your code. A sorted array of bit locations would represent a sparse bit set well enough to start, with O(N) storage and O(log N) access. Once the sets became large and/or dense, another data structure could be considered.
- deleted 2y ago[deleted]