Сжатые Bitmap. Могут быть в сотни раз быстрее
RoaringBitmap
13
0х0000 0х0001 0х0001
0
62
124
186
248
310
…
61 938
[0,99]
[101,99]
[300,99]
1
0
1
0
1
0
…
0
16-bit values + pointers to container
1000 sorted 16-bit values (2000 B)
216 bits (8kB)
3 х 2 B = 6 B
Three pairs of 16-bit
values, indicating
intervals [0,99], [101,
200], [300,399]; pairs
are sorted for fast
random access
array container
(1000 values)
run container
(3 runs)
bitset container
(215 values)