3 ms·
Another way would be to simply calculate hash(prefix + obj) and then choose the object with lowest hash value. You can use a GPU-fast hash like sha2, and you ca
by tomp 13y ago
Another way would be to simply calculate hash(prefix + obj) and then choose the object with lowest hash value. You can use a GPU-fast hash like sha2, and you can even paralelize it. It's not guaranteed to be evenly distributed, but I think it would be close enough for most purposes.
- noelwelsh 13y agoIngenious! This should work -- the uniform distribution property of hash functions is relied upon very heavily by other streaming algorithms such as HyperLogLog, and there has been sound empirical evaluation by the guys at Aggregate Knowledge of the properties of various hash functions: http://blog.aggregateknowledge.com/2012/02/02/choosing-a-good-hash-function-part-3/ http://blog.aggregateknowledge.com/2012/02/02/choosing-a-goo... (Dunno why you include a prefix in the calculation above. hash(obj) should be sufficient.)
- joosters 13y agoYou need the prefix because without it, you will end up picking the same object every time you run the algorithm (e.g. On the next day's stream of data) Depends, of course, upon the size of the stream and the range in variety of the objects in the stream.A stream of bytes would not be a good use case, for example.