3 ms·

If you are storing 16-bit integers, wouldn't an 8kB bitmap be even faster?

• Findecanor 6mo ago
  The range is 1..4096, so 4096 bits = 512 byte bitmap would suffice. That is, if you're only ever going to test for membership in the set. If you need metadata then ... You could store that in a packed array and use a population count of the bit-vector before the lookup bit as index into it. For each word of bits, store the accumulated population count of the words before it to speed up lookup. Modern CPU's are memory-bound so I don't think SIMD would help much over using 64-bit words. For 4096 bits / 64, that would be 64 additional bytes.
  • aidenn0 6mo ago
    The size is 1..4096, the range is implied to be the full 16-bit integer range.
• loeg 6mo ago
  The library the author is talking about selects between bitmap and array dynamically depending on density. https://roaringbitmap.org/ https://roaringbitmap.org/
  • aidenn0 6mo ago
    That explains the maximum size of 4096 elements (exactly where a bitmap would be smaller).