3 ms·
The 4k items are only 512 bytes though, so expensive yes but not overly so.
by foota 4y ago
The 4k items are only 512 bytes though, so expensive yes but not overly so.
- skitter 4y agoThey are two byte per item; it's the bitmaps (>4k entries) that use 1 bit per item.
- Veserv 4y agoNo. The person you are replying to is talking about the sparse leaf case where the contained integers are actually being stored (to be more precise the low bits are being stored) in a sorted structure. The switch to the bitmap occurs when the sparse structure takes the same number of bits to directly encode the sparsely contained items. In this case they use a 2^16 bitmap and encode sparse elements using 16-bits, so it occurs at ((2^16 / 16) == 2^12) elements.