5 ms·
Took me a few reads, but it's actually quite simple. You want a structure that can tell you something has been seen, but sometimes forgets, but will never inco
by MichaelGG 14y ago
Took me a few reads, but it's actually quite simple.
You want a structure that can tell you something has been seen, but sometimes forgets, but will never incorrectly tell you something has been seen.
Solution: an array. Hash the item to find its index, swap out what's there, and see if it is your item. If so, you know for sure it was previously placed. If not, then it might not have (it may have been forgotten).
let arr = Array of key
let contains_key key =
let index = hash key % arr.length
let prev_key = arr.swap[index, key]
return prev_key = key
The hash algorithm is crucial. Reducing forgetfulness is as simple as making the array longer. And he points out that if you can compress the keys, you can reduce storage size.
- jderick 14y agoSo it's just a cache?
- JonnieCache 14y agoA lot of things turn out to be "just" caches. Relatedly, the majority(?) of audio processing is just creative use of buffers.
- Dylan16807 14y agoSure, but this is a rather simple cache. Hash into bucket, LRU per bucket, stores the entire object. Nothing like the magic of a bloom filter that represents an object with 3-5 bits.
- deleted 14y ago[deleted]
- ajross 14y agoPretty much. There's a reason that there's no wikipedia page for this algorithm (where there is for Bloom Filter, of course) -- it's just a hash table without chaining (i.e. it simply drops collisions).
- NovaX 14y agoIts called a direct mapped cache: http://en.wikipedia.org/wiki/CPU_cache#Direct-mapped_cache http://en.wikipedia.org/wiki/CPU_cache#Direct-mapped_cache
- xianshou 14y ago@jderick: Specifically, it functions the same as a cache with a random removal policy, assuming a good hash function. So a cache and a Bloom filter are opposites: the first knows when something hasn't been seen, and might know when it has; the second knows when something hasn't been seen, and might know when it hasn't. The only difference between this and a normal cache is that we're dropping the values. On that subject, you might as well have an LRU valueless cache if locality is going to play a role.
- Ralith 14y ago> the second knows when something hasn't been seen, and might know when it hasn't. Don't think you meant that.
- IvarTJ 14y agoSo combining the two will not give you something that will make up for each of the ones weaknesses and always give a definite answer, but will give one of three answers – definite positive, maybe, and definitive negative. | P | M | N Bloom | X | X | Oppos | X | |
- dnc 14y ago> So combining the two will not give you something that will make up for each of the ones weaknesses and always give a definite answer True, although the probability of a false answer given that we combine them can be smaller from the probability of the same false answer in the case when we use each of them separately. This may be important in cases when the aversion to false answers is extremely high.