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.

Improve this question
$\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$
    – AspiringMat
    Commented Aug 5, 2022 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. ♦
    Commented Aug 5, 2022 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. ♦
    Commented Aug 5, 2022 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
    Commented Aug 5, 2022 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$
    – user16034
    Commented Aug 5, 2022 at 14:40

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ How do you conclude 1.5N slots ? I believe in 3N instead. $\endgroup$
    – user16034
    Commented Aug 5, 2022 at 14:44
  • $\begingroup$ There are N/2 sequencies each consuming 3 slots. $\endgroup$
    – Andrey Godyaev
    Commented Aug 5, 2022 at 14:45
  • $\begingroup$ Ok, I got it... $\endgroup$
    – user16034
    Commented Aug 5, 2022 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
    Commented Aug 5, 2022 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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