[erlang-questions] Needed: Great big ordered int set.

[Jesper Louis Andersen]

On Mon, Jul 8, 2013 at 7:11 PM, Alex Arnon <alex.arnon@REDACTED> wrote:

> Hi All,
>
> I need to implement a very large set of data, with the following
> requirements:
> - It will be populated EXCLUSIVELY by 64-bit integers.
> - The only operations will be:
>   - add element,
>   - get number of elements, and
>   - fold/foreach over the SORTED dataset.
>
>
Unless I am totally wrong here about what you want to get, why don't you
use a digital representation? A 64 bit integer is a stream of bits. You can
then share the common parts of the bit pattern in a tree-like structure.
This in turn means that compression is "automatic" since the common bit
patterns acts like the compression pattern. Add something like "everything
below this node is present" and you can compress common parts of the tree.

In general, the solution is RADIX-trees, or something along that pattern.
They have, incidentally, also been used for quick Integer-key-based maps
and so on.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20130709/268b47c1/attachment.htm>