From: Ryan Davis <ryand-ruby@...>
Date: 2012-05-24T09:27:31+09:00
Subject: Re: Memory-efficient set of Fixnums


On May 23, 2012, at 4:09 PM, Admin Tensor wrote:

> Ryan Davis wrote in post #1061877:
>> Also... smells like homework.
>> 
>> But if not, it reminds me of this article:
>> 
>> 
> http://highscalability.com/blog/2012/4/5/big-data-counting-how-to-count-a-billion-distinct-objects-us.html
> 
> Hi,
> 
> Whether it is a homework or not, it is a very realistic problem that we
> may encounter in our daily programming.

Absolutely! I know all my databases store off tens of millions of unique integers that I iterate over and search against all the time. That's pretty much all I've been doing over my last 22 years of professional development.

> The article is about using probabilistic algorithms with some level of
> error.

Some level of _precalculated_ error, which is what makes this an interesting solution.

> I think we all assumed that the original poster wants an error
> of zero.  (If the problem could not be solved using several gigabytes of
> RAM, or if the computation time took too long, then probabilistic
> algorithms ought to be considered.)

Making the assumption that requirements as stated are correct is what dooms software to be bad. Using a 512 megabyte in-memory bitmap is NOT a _good_ solution, it's just that it is one of the simplest solutions that meets all the (ridiculous) requirements.