3 ms·
Probably not related. Sounds like it's just doing something like replacing `counter++` with `if(rand() % counter == 0) counter++`, so that the counter will inc
by DagAgren 7y ago
Probably not related.
Sounds like it's just doing something like replacing `counter++` with `if(rand() % counter == 0) counter++`, so that the counter will increase slower and slower the larger it gets.
- morelisp 7y agoAbsolutely related! This is essentially the same observation that makes Flajolet-Martin and HyperLogLog work - that when comparing counts, the exact low bits of large numbers "matter less" than the low bits of small numbers, so you can store the logarithm of the count. They differ in how they calculate the "incremental log" without storing the real values, based on what they are counting (high-dimensional events vs. high-cardinality sets).