Sparse array

In computer science, a sparse array is an array in which most of the elements have the same value (known as the default value—usually 0 or null). The occurrence of zero elements in a large array is both computational and storage inconvenient. An array in which there is large number of zero elements is referred to as being sparse.

In case of sparse arrays, we can ask for a value from an "empty" array position. If we do this, then for array of numbers, it should return zero and for array of objects, it should return null.

A naive implementation of an array may allocate space for the entire array, but in the case where there are few non-default values, this implementation is inefficient. Typically the algorithm used instead of an ordinary array is determined by other known features (or statistical features) of the array, for instance if the sparsity is known in advance, or if the elements are arranged according to some function (e.g. occur in blocks).

As an example, a spreadsheet containing 100×100 mostly empty cells might be more efficiently stored as a linked list rather than an array containing ten thousand array elements.

A heap memory allocator inside a program might choose to store regions of blank space inside a linked list rather than storing all of the allocated regions in, say a bit array.

Representation

Sparse Array can be represented as

     Sparse_Array[{pos1 -> val1, pos2 -> val2,...}]      or
     Sparse_Array[{pos1, pos2,...} -> {val1, val2,...}]  

which yields a sparse array in which values vali appear at positions posi.

See also

• Sparse matrix

External links

• Boost sparse vector class
• Rodolphe Buda, "Two Dimensional Aggregation Procedure: An Alternative to the Matrix Algebraic Algorithm", Computational Economics, 31(4), May, pp.397–408, 2008.