# Are there adaptive algorithms/data structures for sparse and non sparse vectors?

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.

• “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 Aug 5 at 3:58
• 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?
– D.W.
Aug 5 at 7:10
• Are you familiar with page tables? binary search trees? B-trees? Do any of those meet your requirements?
– D.W.
Aug 5 at 7:11
• @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. Aug 5 at 7:12
• 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. Aug 5 at 14:40