21 ms·

Thanks for posting this article. Would this be a good use case for a bloom filter?

• fleitz 11y ago
  Maybe, probably not thought as a completely naive solution to this problem an array of 400M elements which is sorted, only takes 2.4 GB of RAM, or about $50 worth of RAM. Basically you'd waste more time (and money) than it could possibly be worth.
  • bpicolo 11y ago
    I mean, a bloom filter isn't super difficult, but it's also probabilistic instead of deterministic.
    • fleitz 11y ago
      Exactly, so you'd need the array anyway... Also, typically bloom filters don't come out of the box with the language you're using, so it's just more potential for bugs. A lookup on a sorted array should take 8.6 comparisons anyway, I bet the hashing takes longer...
  • d_e_solomon 11y ago
    That's true, good call.
  • mamp 11y ago
    You could get away with much less memory using Redis hashes with a few more lines of code: http://redis.io/topics/memory-optimization http://redis.io/topics/memory-optimization.