4 ms·
This is slightly probabilistic. Say you're checking whether a byte is in a sparse set, then there's a 1/256 chance of a false positive. (That is, if you're not
by arjvik 3y ago
This is slightly probabilistic. Say you're checking whether a byte is in a sparse set, then there's a 1/256 chance of a false positive.
(That is, if you're not zeroing memory. If you are, you don't even need the dense array at all, can just store a sparse array of booleans.)
- bumbledraven 3y agoNo. In order for the algorithm to report that a set with N elements contains an item x, it must find that both sparse[x] < N and dense[sparse[x]] = x; this cannot happen unless x is actually in the set, because dense[0...N-1] has been initialized during the insertion of the first N elements.
- arjvik 3y agoI see, N is not capacity but number of elements inserted.