1
$\begingroup$

I have a "standard" problem, but I can't remember its "official" name: I have to keep track of the presence of the absence of value in an array.

Currently I use an each bits of an other array to track it. Let's say I have a byte array of 8k elements if I want to know if a place is taken (without accessing to the array), I need a 1k byte array (8 bits per byte) to track it. So I have more or less these complexities:

  • Check: $O(1)$
  • Change: $O(1)$
  • Memory: $O(n/8)$

I wanted to know if there's a more memory optimized data structure keep the constant check factor because I have the following properties:

  • The targetted array has a fixed size known at compile-time
  • Most of the actions performed are Check (maybe 10k-1k checks for one change)
  • The array is mostly sparsed (5-25% used)
  • There are only few space freeing
  • Sometimes a value take more than one byte but I only need to keep track of the first one.

I'm looking for data-structures name or samples. Thanks.

$\endgroup$
  • 2
    $\begingroup$ Why not use a hash table instead? $\endgroup$ – Andrew Au Feb 18 '16 at 2:31
  • $\begingroup$ Points I wish were more explicit: 1) this is about compact (and low/constant time check) representation of a mapping "index" (in "the array") to (first byte of?) value. (Consider defining names, I prefer descriptive ones if there are no equations/expressions with many names) 2) it doesn't suggest itself to "set aside" one value to mean unoccupied 3) from a comment to an answer: 5% memory gain will be [welcome] is this 50 "data" bytes (5% of the 1KB "occupied array"), with "code size" of subordinate concern? (This question might be more appropriate in a microcomputer forum.) $\endgroup$ – greybeard Feb 18 '16 at 10:22
3
$\begingroup$

Let's suppose that there the occupancy rate is 25%. Then given an array of $n$ elements, there are ${ n \choose 0.25n}$ possible bitmaps. The theoretical minimum number of bits per entry that you need is, then:

$$\lim_{n \rightarrow \infty}\frac{1}{n} \log_2 { n \choose 0.25n } \approx 0.81$$

At 5%, the minimum number is:

$$\lim_{n \rightarrow \infty}\frac{1}{n} \log_2 { n \choose 0.05n } \approx 0.29$$

Note that I didn't actually calculate it this way. I used the binomial entropy function:

$$B(p) = -\left(p \log_2 p + (1-p) \log_2 (1-p)\right)$$

Then $B(0.05) \approx 0.29$.

So given a 25% occupancy rate, there is no data structure which compresses better than 80% of the size of the uncompressed bitmap.

Given that it sounds like you have a real problem to solve, does shaving 20% off the size of the bitmap seem like a reasonable benefit, given that the cost is likely to be a much higher-constant-factor data structure?

Besides, 1kB just isn't that big. It's a fraction of a page in size, and likely to be in cache most of the time if this is really your inner loop.

EDIT

OK, if you really need this, I suspect that succinct hashing might be your best bet. There are dynamic bitmap data structures which support the rank operation, but none of them have constant time queries to my knowledge.

$\endgroup$
  • $\begingroup$ It's important since we have a very limited amount of memory, even a 5% memory gain will be noticeable. If I keep a constant checking factor, changing factor doesn't matter. $\endgroup$ – GlinesMome Feb 18 '16 at 7:09
1
$\begingroup$

https://en.wikipedia.org/wiki/Bloom_filter is an interesting approach with O(1) memory use that might not fit your case if you can handle the occasional false positive - i.e., the system sometimes falsely saying that a particular location is not available; if the array is mostly sparse and/or you can double-check somewhere.

$\endgroup$
  • $\begingroup$ Bloom filters also can't handle the "Change" operation very well. They're a better for for a static set that won't change, rather than a dynamic one that you want to be able to update. $\endgroup$ – D.W. Feb 18 '16 at 2:58
  • $\begingroup$ This bitmap should be precise. $\endgroup$ – GlinesMome Feb 18 '16 at 7:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.