Re: [Caml-list] intersecting huge integer sets

[Diego Olivier Fernandez Pons <Diego-Olivier.FERNANDEZ-PONS@cicrp.jussieu.fr>]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1098 bytes --]

    Bonjour,

I made a small module with tries in base n where n is inferior to the
native integer size. I supports big-endian tries and little-endian
tries (in fact, user defined decomposition)

avaible functions :
- insert (log n)
- delete (log n)
- from_list (n log n)
- to_list (unknown)
- union (shoud be n)
- intersection (should be n)

I do not know if they are faster or not than bit-vectors or patricia
trees, but they save a lot of space

A set of integers from 0 to 9999 (I tried with 1 000 000 items as you
suggested but my function never ended. I remember a computation by
Xavier Leroy showing that a counter could hardly overflow)

(results given by JC Fillâtre's module Size)

avl set : 200 000 bytes
red-black set : 160 012 bytes
30 bit trie big-endian : 5 524 bytes
31 bit trie big-endian : 5 312 bytes
30 bit trie little-endian : 15 020 bytes
31 bit trie little-endian : 16 016 bytes

The implementation is not speed optimized. In fact one could also save
some more space compacting bits for bases inferior to int_size / 2

        Diego Olivier

[-- Attachment #2: bitSet --]
[-- Type: APPLICATION/octet-stream, Size: 1178 bytes --]