1
$\begingroup$

A sparse 1D array of integers is commonly encoded as pairs of [index, value], which consumes 2 memory spots per value.

A dense 1D array is commonly encoded as a linear array of values [value1, value2, ..., valueN], consecutive in memory.

If an array is encoded as a sparse array, but grows in density, until it becomes dense, then it uses 2X the memory of the array encoded as a dense array.

The question is, is there an encoding that gradually changes from sparse to dense, without wasting memory, and being fast to randomly read and write?

For example, to manage arrays which may be sparse or dense, anything in the middle, and change sparsity as they get manipulated.

$\endgroup$
8
  • 1
    $\begingroup$ “Fast” from a coding point of view or theoretical pov? There are many theoretically fast but practically useless algorithms. Stack overflow might be a better place for this $\endgroup$ Aug 5 at 3:58
  • $\begingroup$ Can you define what counts as "wasting memory"? What criteria will you use to determine whether a proposed solution does or doesn't waste memory? $\endgroup$
    – D.W.
    Aug 5 at 7:10
  • $\begingroup$ Are you familiar with page tables? binary search trees? B-trees? Do any of those meet your requirements? $\endgroup$
    – D.W.
    Aug 5 at 7:11
  • $\begingroup$ @D.W. If you use sparse encoding for a dense array, you spend 2X the memory needed for the dense array. It wastes memory. If you use dense encoding for a sparse array, you waste most of the memory. $\endgroup$
    – Colim
    Aug 5 at 7:12
  • 1
    $\begingroup$ Your arrays must be real huge for the sparse representation to be problematic in case of high density... By the way, the sparse representation does not allow random accesses. $\endgroup$ Aug 5 at 14:40

1 Answer 1

3
$\begingroup$

Consume M + 2 slots per each continuous sequence of M values in sparse array: [index, length, value1, value2, .., valueM]. When you append a new value to a sequence check if it is possible to join the next sequence to this one.

If N is the high index of the array it will consume N + 2 slots when fully filled. In the worst case [value, NULL, value, NULL, value, ...] the array consumes 1,5N memory slots.

$\endgroup$
4
  • $\begingroup$ How do you conclude 1.5N slots ? I believe in 3N instead. $\endgroup$ Aug 5 at 14:44
  • $\begingroup$ There are N/2 sequencies each consuming 3 slots. $\endgroup$ Aug 5 at 14:45
  • $\begingroup$ Ok, I got it... $\endgroup$ Aug 5 at 14:49
  • $\begingroup$ Best answer to this point. I thought, instead of length, storing a "pattern" unsigned integer, where each bit represents the presence or absence of a zero, like [index, 0b00001,value] means there is only 1 value, and [index, 0b1111, value, value, value, value] is a dense array. But [Idx, 0b100,v] would mean the same as [Idx, 0b010,v] and that wastes encoding. $\endgroup$
    – Colim
    Aug 5 at 15:25

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.