3 ms·
This was discussed a bit in the Hacker News thread after last blog post but I continue to feel that bloom filters aren't particularly useful here. Since any sol
by jeresig 16y ago
This was discussed a bit in the Hacker News thread after last blog post but I continue to feel that bloom filters aren't particularly useful here. Since any solution I use would require no errors it would mean that I'd have to place the bloom filter in front of another solution (likely the succinct trie structure that I described).
Let's assume that the bloom filter is as fast as a hash lookup (unlikely, but anyway) - at most it'll be saving me about 5-46ms of lookup time, with some non-trivial additional memory usage and data transfer. I'm 100% OK with having 5-46ms of lookup time if it means that I can have such an incredibly low memory profile. If lookups took somewhere around 200ms then yeah, I'd definitely look at layering a bloom filter on top of this. As it stands though using a bloom filter will only add additional code and memory usage for a negligible amount of benefit.
- rorrr 16y agoWhy do you require 0% error?
- jeresig 16y agoI would prefer that people spell words in my game that are actually words and not abuses of the system. I expect users to be challenging one another so I'd imagine that they wouldn't take too kindly towards one person getting an unnecessary (and unexpected) advantage.
- rorrr 16y agoIf the error rate is 0.1% it would take a user 1000 tries (on average) to enter a word that's not in the dictionary. That's a lot of attempts.
- pbrumm 16y agoguaranteeing zero errors is a problem. but if the loaded bloom filter size is small you could expand to get a very low false positive. the first link would do the lookup in javascript so it would run in the client. and the storage is just a string so wouldn't have the javascript parsing on load.