4 ms·
This may be naive of me, but wouldn't it be better to leverage your language's existing tools? For instance, in Python you would use a dict... >>> my_dict =
by pdeuchler 14y ago
This may be naive of me, but wouldn't it be better to leverage your language's existing tools? For instance, in Python you would use a dict...
>>> my_dict = {}
>>> my_dict[item] = True #Insert an item
>>> try:
... tmp = my_dict[item]
... print "Found"
... except KeyError:
... print "Not found"
I can't imagine a custom implementation would be more efficient, though there may be other reasons to roll your own.
- deleted 14y ago[deleted]
- deleted 14y ago[deleted]
- sbov 14y agoThe problem is your solution (as shown) will grow in memory forever. You can add code to get around that (e.g. expiration times), but it also might be easier (and have less memory usage) to write your own dict class that overwrites values when a collision occurs. Also, since the OP seems to be using java: if you can get away with storing a primitive data type in an array (e.g. array of int or long) you can save a lot of memory vs using a Set or Map.
- philsnow 14y agoPython dicts will grow and grow as you add more keys to them, but one of the constraints mentioned in the article (and implicitly included, because he's talking about a variation on a bloom filter) is that the data structure should not grow without bound. They wanted to use a fixed-size array. Also, in your example you're storing True as the value, but if you do that, you can't tell the difference between rbloom_array[hashfunc(item1)] and rbloom_array[hashfunc(item2)], if hashfunc(item1) == hashfunc(item2) (that is, they collide). You'd need to store the actual item in the data structure, not just a bit, and then you compare what you get out of the data structure to what you're trying to put in it. If the _items_ are equal then it's a duplicate and you can skip the write (to the database, from the example). If the items are not equal, you need to do the write.