On Friday, 22 April 2016 at 22:37:49 UTC, David Nadlinger wrote:
On Friday, 22 April 2016 at 21:38:41 UTC, Johan Engelen wrote:
I don't understand exactly what you mean; do you propose to
[…] do a linear search when the shadow data structure says the
item is present?
That's the idea. As long as you can reduce the need to do a
full linear search by, say, 1 : 1000, it would be enough to
make the quadratic behaviour disappear into the noise.
Well, this 140k list has a removal very early on, so the linear
search is going to happen >100k times from then on ;)
That being said, I did some estimates, and since the keys are
only 8 bytes in size, Bloom filters in particular might not be
worth it in this case, unfortunately. Quite sad, actually. I
like Bloom filters.
I figured :-)
